博士

ロボ子、今日はハミルトン路について話すのじゃ！グラフ理論の面白いところだぞ。

ロボ子

ハミルトン路ですか、博士。グラフ内のすべての頂点を一度ずつ通る路のことですね。

博士

そうそう！で、ハミルトン閉路は、それに最初の頂点に戻る辺があるものだぞ。ちょっと違うのじゃ。

ロボ子

なるほど。ハミルトン路問題はNP完全とのことですが、これはどういう意味ですか？

博士

NP完全ってことは、簡単に答えを見つけられないってことじゃ。でも、見つけた答えが正しいかはすぐに確認できるのじゃ！

ロボ子

ふむふむ。ゲームに応用できるんですね。ランダムに生成されたグラフで、すべての頂点を訪問する路を見つけるパズルゲームですか。

博士

そう！そこでbitDPの出番じゃ！プレイヤーの選択した路がハミルトン路かどうかを効率的に確認できるのじゃ。

ロボ子

bitDPですか。ナイーブなアプローチだとDFSでO(n!)の計算量がかかるところを、効率化できるんですね。

博士

そう！DFSだと頂点の数が増えるにつれて爆発的に計算量が増えるからな。動的計画法、特にHeld-Karpアルゴリズムを使うと、2^Nの計算で済むのじゃ！

ロボ子

Held-Karpアルゴリズムは、巡回セールスマン問題(TSP)を解決する方法としても知られていますね。ハミルトン路検出にも使えるんですね。

博士

その通り！bitDPでは、N × 2^Nのテーブルを使うのじゃ。各頂点はビットで表現されて、1はその頂点が部分グラフに含まれることを意味するぞ。

ロボ子

各列が部分グラフを表していて、値が1の場合、その行の頂点で終わるハミルトン路が部分グラフ内に存在する、と。

博士

そういうことじゃ！このテーブルをうまく使うと、効率的にハミルトン路を見つけられるのじゃ！

ロボ子

なるほど、よくわかりました。グラフ理論、奥が深いですね。

博士

ところでロボ子、ハミルトン路を全部歩いたら、靴底がすり減って大変じゃな。…って、ロボットだから関係ないか！