10:40 〜 11:00
[4F1-OS-8a-02] 最短路遷移問題のZDDを用いた解法と評価
キーワード：組合せ遷移、グラフアルゴリズム、零抑制型二分決定グラフ
最短路遷移問題は入力が重みなし単純グラフ G(V,E) と V 上の頂点 s,t および G 上の s-t 最短路 P,Q であり，1つの頂点を変更して最短路を得ることを繰り返してPからQを得ることが可能かを出力する問題である．この問題はPSPACE完全であることが知られている．本研究ではZDD演算を工夫して定数回の演算による高速な手法を提案する．計算機実験によって，8100頂点16020辺の90×90のグリッドグラフにおける最短操作列長が7921のインスタンスを約114.5分で解け， また，288頂点781辺で最短操作列長が46137333のインスタンスを約349.6分で解けることを示す．
講演PDFパスワード認証
論文PDFの閲覧にはログインが必要です。参加登録者の方は「参加者用ログイン」画面からログインしてください。あるいは論文PDF閲覧用のパスワードを以下にご入力ください。