私は騎士のツアーアルゴリズムについて学んでいます。再帰的な罰金を使用して実装しましたが、時間がかかり、クローズドツアーではありません。
今、私は現在、閉じたツアーを見つけるための高速なアルゴリズムを見つけています。誰かが私にいくつかのアルゴリズムを勧めることができますか?
更新:次のようなクローズド ナイト ツアーを見つけるためのヒューリスティックをどこかで読みました:Min[F(x, y)]どこでF(x,y) is a set of f(x,y)=Min(x-1, n-x) + Min(y-1, n-y)と(x, y)は次のステップの位置、nはチェス盤のサイズです。しかし、そのヒューリスティックをどのように使用すればよいでしょうか?
今日、Knight Graph (Knight の可能な動きをモデル化したグラフ) に Depth First Search を実装して、この問題を解決しました。
なぜワーンスドルフのヒューリスティックでは不十分なのかを考えながら午後を過ごしましたが、この問題が私の出発点でした。
(0,0) の位置から DFS を開始していました。(3,3) のように途中から始めると、DFS は大幅に改善されるようです。これを変更した後、アルゴリズムの速度は (1 時間以内に解がない) から (1 秒以内に 1 つの解) になりました。
あなたの Min[F(x,y)] ヒューリスティックもテストしましたが、ワーンスドルフのルール (8x8 テーブルの場合) と同じパフォーマンスで動作したようです。