A-007
分岐・共通部優先ヒューリスティック探索によるサイフォン・トラップ構造検出の効率化

◎南　史弥・張江洋次朗・和崎克己（信州大）

一般ペトリネットを対象とし，ネットのサイフォン・トラップ構造解析時にヒューリスティック手法を導入して，構造検知の探索コストを効率化する方法を提案する．具体的には，探索の優先度として，先ずネット内に複数存在する閉路の共通部分路（共通部）を抽出し，部分路を拠点として枝分かれしている部分（分岐）を発見する．次に，分岐点にあるプレースから逐次深さ優先探索を開始して探査を行う．探索途中で共通部に再び戻ってきた場合に，サイフォン（あるいはトラップ）構造候補としてリストに保存する．共通部分から分岐する全ての路を探索後，未探査の共通部分があれば改めて探査を再開する．以上の優先ヒューリスティック探索により，複数の構造に共通するプレースを早期に発見し，かつ構造解析に要するプレース数を候補リストという形で大幅に減らすことで処理の効率化を図る．計算時間の評価として，従来法である充足可能性判定アルゴリズムと性能比較する．