線形計画法を加味した動的計画法によるペトリネットの可到達性判定法

概要

論文の詳細を見る
ペトリネットは、並列・並行、非同期、非決定な、分散・離散事象システムのモデルとして有用なものの1つとして関心がもたれているが、その基本的性質の可到達性の判定法としては、一般には、列挙法である可到達木を用いる以外に有用な手法はなかった。しかし、既知発火回数ベクトルのもとでの本問題はLPを直接に用いた多項式時間アルゴリズムで解けることが、最近、報告されたが、発火ベクトル系列長dとともに問題の規模が膨大になることが問題点の1つである[4]。本論文では、上記問題点を緩和させるために、与えられた可到達問題をd個の部分過程からなるものとみなし、Bellmanの最適性の原理によって得られる動的計画法DPによる定式化を行って、各部分過程の問題の規模を約1/dに縮小するとともに、一般のDPで問題になるメモリー空間の爆発をペトリネットの逆ネットの性質を活用することにより回避できること、更には、各部分問題の最適化もLPを用いて多項式時間で解けることを示している。その結果、本手法は、直接にLPを用いる場合[4]よりも約d^<-3>倍改善された多項式時間アルゴリズムであることが示されている。
社団法人電子情報通信学会の論文
1995-05-19