発火系列探索法の改良に基づいて性能強化されたペトリネットマーキング構成問題解法(一般,コンカレントシステム及び一般)

概要

論文の詳細を見る
ペトリネットに対するマーキング構成問題(MCP: Marking Construction Problem)とは,「ペトリネットN,初期マーキングM_i,目標マーキングM_tが与えられた時,M_iからトランジションの発火により遷移可能なマーキングM_cのうちでM_tとの差Δ(M_c)=Σ_<p∈P>|M_t(p)-M_c(p)|が最小となるマーキングを求めよ」と定義される.MCPは一般にNP-困難であり,発見的解法に対する2種類の枠組み:(i)MAX-LFS解法を利用した解法,(ii)MAX-LFS解法を利用しない解法が提案されている.また,(i)におけるMC_feideq_aが最も高精度であることが示されている.ただし,MC_feideq_aは(ii)におけるMCAを後処理として使っている.本稿では,発火系列探索を改良することでMCAを性能強化したMCA+とMCA+_k,そしてMCA+を高速化したMCA+_speedyを提案し,計算機実験によりその性能比較をする.
2011-01-13