グラフでハミルトニャンの経路を見つける

Question

問題ステートメント

各青い正方形が4つの枢機卿方向全ての他の青い四角に接続されている次の画像のすべての青い四角のグラフを与えられます。

起動ノードを与えます。

最も長い（ish）経路を見つけることができるのはどのようなアルゴリズムを許可します。

各ノードが一度訪問できることを考慮してください。

道が終わる場所に気にしないことを考える。

速度が各ノードを必ず訪問するよりも重要であることを考える。

例

私は以下の画像に望ましい結果の例を辿った。ご覧のとおり、パスは各ノードを訪問していないため、大丈夫です。私はこのグラフ上の最長のパスのうちの1つを私に与える高速アルゴリズムを探しています。80％のカバレッジ以上が私が撮影しているものです。

href="htps://i.stack.imgur.com/yi4dt.png" rel="nofollow noreferrer">

Answer 1

uct（ucb1 with ucts）アルゴリズムを使用して終了しましたが、ねじれて。

通常、UCTでは、シミュレーションフェーズはランダムに選択された移動を持つゲームのシミュレーションプレイスルーです。シミュレートされたゲームが勝利で終わった場合、シミュレーションが再生された場所からのノードのスコア、そしてそれはすべての根元のスコアのスコアは1でインクリメントされます。

私の実装では、シミュレートされた「プレイスルー」は実際にはまだ訪れていない隣接タイルの木を歩くだけです。シミュレーションが端末ノードに達すると、S= D / Mのスコアが割り当てられ、ここでDはツリー内の端末ノードの深さ、Mは最大可能な深さです。

障害物なしの15 x 15グリッドでは、最長のパスがすべてのタイルを訪問するようにMから225を設定します。私は一般化されるアルゴリズムが必要なアルゴリズムを必要とし、通常は10~30タイルが存在するランダムに生成されたマップで作業するように私はわずかに低くなりました。

両親のスコアを増やす代わりに、バックトラック化アルゴリズムは、現在のスコアよりも高い場合、各親のスコアを新たに計算されたスコアに設定します。言い換えれば、ノードのスコアは常にこのノードからこれまでに到達した最長パスの長さを表します。

uctは、現在のノードの子が拡大された後にどのノードを展開または探索するかを選択するためにUCB1を使用して、それに大きく保持されています。私が行った唯一の修正は、活用用語です。 UCB1では、利用期間はW / Vであり、ここでWはノードの累積スコアであり、vはノードが訪問された時間数です。これはあなたが勝った可能性を最大にする移動を選択したいゲームでは素晴らしいことです。私の場合、スコアはwin= 1のバイナリ関数を反映していないため、0=スーパーショートパスVs 1=最長の経路である可能性があり、アルゴリズムによって見つけられた最長の経路を下りたいです。 、私は単にこのノードから到達可能なS= Score=最長パスに到達可能なパスを単に設定しました。

このアルゴリズムを使用しているコンテキストでは、移動を選択する前に、NodeJS環境で最大40ミリ秒の計算時間を可能にします。これは通常私のマシン上の785のツリートラバーサルの約785の走査をする可能性があります。平均して、その時、そしてマップ上でOPで示された、このアルゴリズムは70ノードの深さのパスを見つけるでしょう。私が再びアルゴリズムを再び実行することを目的とした私の目的のために十分な以上のものです。実際には、このアルゴリズムを使用して次の移動を選択すると、デッドエンドを叩く前に100~110ステップの経路を移動し、青いタイルの非常に大きな部分をカバーします。

楽しみのために私は、平均して、あまり30000トラバース（マシン上で30秒）のアルゴリズムを走らせました。このマップの最大深さに近い。

Answer 2

これは最長パスの問題です。一般的なグラフで最長パスを見つけるのはNPハードです。最長パスを見つけるための標準的なアルゴリズムを適用することができます。このサイトを検索して、「最長パス」と「ハミルトニアンのパス」を検索して、多くの参考文献を見つけてください。最適な解決策を受け入れることを望んでいるので、ヒューリスティックまたは近似アルゴリズム（例えば、ローカル検索アルゴリズムを使用して）を探すことができます。