情報処理学会 第82回全国大会 会期:2020年3月5日~7日 会場:金沢工業大学 扇が丘キャンパス 情報処理学会 第82回全国大会 会期:2020年3月5日~7日 会場:金沢工業大学 扇が丘キャンパス

2M-04
ペトリネット構造解析の効率化を目的としたヒューリスティック探査手法の実装
○南 史弥,張江洋次朗,和﨑克己(信州大)
深さ優先探索を用いた強連結成分分解時の情報を用いて,極小サイフォン・トラップ構造を,充足可能性判定,接続行列を用いたインバリアント解析よりも効率良く検出するようなヒューリスティックアルゴリズムを提案する.まず,ネットに対して強連結成分分解を行う.強連結ごとにネット内に複数存在する構造の共通部分が含まれている場合,フローが分岐する特徴点から深さ優先探索を用いて,性質を満足するプレースの探査を開始する.共通部分に戻ってきた場合,探索したプレース列をサイフォン・トラップ候補リストに保存する.共通部分から分岐する全ての路を探査し,かつ全ての強連結成分に対し探査が終了した後,サイフォン・トラップ構造を成しているかどうかの真偽判定を候補リストに対して行う.