ペトリネットの発火系列問題に対する近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本論文はペトリネットの発火系列問題(LFSと略記)に対する性能の良い近似アルゴリズムYWLFSを提案する.ペトリネットの発火系列問題とは,ペトリネットPN,初期マーキングMと発火回数ベクトルX(その要素X(t)が各トランジションtの発火回数を表す)が与えられたとき,各トランジションtがその中に合計で丁度X(t)回現れ,且つMから順に発火可能であるトランジションの系列が存在するか否か判定し,存在するならばその様な一つの系列δを求める問題である.この問題は非常に簡単な構造を持つペトリネットに対してさえNP-完全であることが知られている.実験では,これまでの当研究室での関連研究において既にδの存在が既知である2181個の入力例に対してYWLFSを適用した.その結果,YWLFSは2050個(94%)の入力例について実際にδを見つけ,δの発見に不成功であった131個の入力例については既知のδの長さの平均72%までの長さの発火可能な系列を求めている.このことからYWLFSは高い能力を持つものと思われる.
- 一般社団法人情報処理学会の論文
- 1993-05-28
著者
関連論文
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- A-12-4 トランジション改良選択法に基づくペトリネット最小初期マーキングの効率的構成法(A-12.コンカレント工学,一般講演)
- ペトリネットの最小初期マーキング探索におけるトランジションの効果的選択法(コンカレントシステム, 一般)
- ペトリネットの最小初期マーキングのための動作的デッドロック回避に基づく高速な発見的解法(コンカレントシステム, 離散事象システム, ハイブリッドシステム, 及び一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法(グラフ,ペトリ,ニューラルネット,及び一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法(グラフ,ペトリ,ニューラルネット,及び一般)
- ペトリネットのサイフォン・トラップ抽出効率化のためのサブネット縮約法
- グラフの3-辺連結化について(計算アルゴリズムと計算量の基礎理論)
- グラフの局所辺連結度増加問題に対する近似解法
- グラフのk辺連結化問題に対する新しい近似解法
- 領域分割に基づく並列配線手法
- アナログ回路用多層プリント基板の分離型設計
- 多層プリント基板設計における回路分割の一手法
- 広島大学工学部第二類(電気系)回路システム工学大講座情報回路網工学研究室
- グラフの辺付加問題による耐故障ネットワ-クの構成
- 耐故障ネットワークと辺付加問題(計算アルゴリズムと計算量の基礎理論)
- マ-クグラフの初等P-インバリアントとP-基底
- 予測・修正混雑コスト方式によるスイッチボックス配線手法 (最適化)
- 固定ルーティングネットワークにおける無故障な経由ルート数の評価
- 辺の付加によるグラフの拡大構成問題(グラフ理論とその応用)
- 辺付加によるグラフの拡大構成問題(計算機科学の基礎理論)
- 3-連結グラフの連結点被覆問題 (形式言語理論とオートマトン理論)
- 辺短絡除去問題のNP-困難性について(技術談話室)
- 辺開放除去問題のNP-困難性について
- 平面グラフの点除去による2端子直並列グラフの構成問題(技術談話室)
- 辺の短絡除去による平面グラフ化問題について
- 辺の短絡除去による平面グラフ化問題--最大節点次数がたかだか3の場合(技術談話室)
- 辺の短絡除去による2端子直並列グラフの構成問題(技術談話室)
- 辺の開放除去による2端子直並列グラフの構成問題(技術談話室)
- ステートマシンの接続構造を持つペトリネットの発火系列問題
- ペトリネットの最小初期部分マーキング問題について(グラフ,ネットワークとアルゴリズムおよび一般)
- 階層型グラフに対応したグラフアルゴリズムの視覚的トレースツールの開発(グラフ,ペトリ,ニューラルネット及び一般)
- 階層型グラフに対応したグラフアルゴリズムの視覚的トレースツールの開発(グラフ,ペトリ,ニューラルネット及び一般)
- ペトリネットの最小初期マーキング問題に対する発見的解法
- ペトリネットの最大発火系列問題に対する発見的アルゴリズムFSDB
- ペトリネットインバリアント算出のためのFourier-Motzkin法の改良実装
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- A-12-5 時間付ペトリネットによるスケジューリングに対する発見的解法SDS
- A-12-4 指定プレース集合を含むサポートを持つペトリネットインバリアントの算出法
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- グラフの最小コスト3-点連結化問題に対する近似アルゴリズム
- ペトリネット発火系列問題の概説
- ペトリネット発火系列問題の概説
- 複数の求解戦略を持つリアルタイムスケジューリング法
- A-12-4 サイフォン・トラップ台に基づくインバリアント算出法
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズム FMSN
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- A-12-3 ペトリネットの最適発火系列問題に対する発見的解法OFSD
- On Forming a Series-Parallel Graph by Removing Nodes of a Planar Graph (Studies on Computational Complexities and Related Topics)
- 一般ペトリネットにおける単一指定プレースを含む極小サイフォン抽出法
- 一般ペトリネットにおける極小デッドロック抽出法
- ペトリネットの発火系列問題に対する近似アルゴリズム
- グラフの多重辺付加を許さない4辺連結化問題
- グラフの指定点集合に対するk辺連結化問題
- グラフの多重辺付加を許さない辺連結化問題
- グラフの多重辺付加を許さない4辺連結化問題
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネットの発火系列問題に対する新しい発見的解法FSD
- ペトリネットの指定プレース集合を含むサイフォン抽出法
- ペトリネットの発火系列問題に対する発見的解法FSD
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム