双方向の N*M グリッドで可能な限りランダムなハミルトニアン パスを見つけることができる効率的なアルゴリズムを探しています。
どこで見つけられるか、またはそのようなアルゴリズムを構築する方法を知っている人はいますか?
私はすでに効率的なアプローチを見つけました（下の画像を参照）。ここでの最終結果はハミルトニアン サイクルです。ランダム エッジを削除すると、ハミルトニアン パスになります。このアルゴリズムは効率的ですが、ランダム性が十分ではありません。このアプローチでは、パスの始点と終点が常に隣り合っていますが、それらをランダムな場所に配置したいと考えています。 空間充填曲線 http://img593.imageshack.us/img593/8060/sfc.png http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type= から取得した画像pdf
十分なランダム性は非常に一般的です。いくつかのベンチマークが必要です。ユークレアディアン TSP の最も有名なアルゴリズムには 3/2 近似 (クリストフィデス アルゴリズム) があり、 MSTを使用します (前述の 2 近似アルゴリズムと同様)。現在見つかった最良の PTAS は、c > 0 (サンプルのような 2 次元空間) の (n log n)^f(c,2) に依存する実行時間があり、(1+1/c) の近似値と TSP の最良の近似値があります。一定の係数を持つのは3/2 - 1/500アルゴリズム（最近発見された）ですが、それらはすべて論理的な方法を使用しており、いくつかのランダムな使用法がありますが、すべてをランダムな選択に任せるわけではありません。ランダムを使用したい場合は、Random Walkを使用できます。よりランダムですが、 Markove Chainを参照してください。より良いパフォーマンスとランダム性のために。
あなたが言及したアプローチから始めて、ハミルトニアンパスを見つけることができます。ソリューションをさらにランダム化するには、wikiに記載されているようにエッジの回転を開始できます。これをより頻繁に行うと、ソリューションがよりランダムになります。ランダム エッジを N*M 回回転させると、アルゴリズムが効率的な領域に維持され、見つかったハミルトニアン パスがよりランダムになります。
