3H-02
論理制約を伴う最短路問題を解く動的計画法の空間計算量の削減
○竹内文登（北大），安田宜仁，西野正彬（NTT），湊　真一（北大）
辺の取捨に関する論理制約を満たす最短経路の探索法を提案する．解に含まれるアイテムの組合せに制約があるナップサック問題などの，重要な問題は制約付き最短路問題に帰着して解ける．この問題を解く既存法として二分決定グラフを用いた動的計画法が知られている．しかし，既存法は探索履歴をすべて記憶するため，メモリ使用量が膨大になるという課題があった．提案法は探索空間を中間地点で再帰的に分割しながら部分問題を解くことで既存法を改良し，時間計算量を悪化させずに空間計算量を改善する．実験では提案法のメモリ使用量が既存法の1/100以下となる一方，速度低下は2倍以内抑えられることを確認した．
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会