ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用

• 中井 貴浩

  広島大学大学院 工学研究科 情報工学専攻

• 山内 雅弘

  広島大学大学院 工学研究科 情報工学専攻

• 高藤 大介

  広島大学工学部 第二類 回路システム工学講座

• 渡邉 敏正

  広島大学工学部 第二類 回路システム工学講座

書誌事項

タイトル別名

• A New Heuristic Algorithm FSDT for the Legal Firing Sequence Problem of Petri Nets and Its Application to Solving MAX SAT

抄録

本論文はペトリネットの発火系列問題(LFSと略記)に対する性能の良い発見的アルゴリズムFSDTを提案し,その性能を実験的に評価すると共に,FSDTをMAX SATの解法として用いた場合の実験結果を示す.FSDTは既存解法FSDの改良版である.実験では,解δの存在が保証されている2230個の入力例に対してFSDTを適用した.その結果,FSDTは1725個(77.4%)の入力例について実際にδを見つけ,FSDと比べて,約6%改善された.また重みなしのMAX SAT, MAX 3SATの744個の充足可能な例題にFSDTを適用した結果,それぞれ98.2%, 99.9%の節を充足させることができた.
The paper proposes a new heuristic algorithm FSDT for the Legal Firing Sequence problem of Petri nets (LFS for short) and evaluates it experimentally. Also provided are experimental results when FSDT is used for solving MAX SAT. FSDT is an improved version of the exiting one FSD. FSDT is applied to 2230 test problems to each of which existence of an exact solution is guaranteed, and it finds an optimum solution to each of 1725 (77.4%) test problems, showing about 6% improvement from FSD. FSDT, applied to 744 satisfiable instances of unweighted MAX SAT or MAX 3SAT, succeeded to satisfy 98.2% or 99.9% of given clauses, respectively.

収録刊行物

• 電子情報通信学会技術研究報告. CAS, 回路とシステム

  電子情報通信学会技術研究報告. CAS, 回路とシステム 99 (416), 1-8, 1999-11-09

  一般社団法人電子情報通信学会

キーワード

• ペトリネット
• 発火系列
• サイフォン
• 発見的解法
• MAX SAT

詳細情報

• CRID: 1573387452131156224
• NII論文ID: 110003226726
• NII書誌ID: AN10013094
• 本文言語コード: en
• データソース種別:
  • CiNii Articles