4

次の問題を解決しようとしていました。

mn 迷路は、左上の正方形から他の正方形へのパスが 1 つだけ存在するように、グリッド セルの間に壁が配置された mn の長方形のグリッドです。以下は、912 迷路と 1520 迷路の例です。

ここに画像の説明を入力

C(m,n) を個別の mn 迷路の数とします。別の迷路からの回転と反射によって形成される迷路は、別個のものと見なされます。

C(1,1) = 1、C(2,2) = 4、C(3,4) = 2415、および C(9,12) = 2.5720e46 (科学表記法では 5 桁に丸められる) であることが確認できます。数字）。
C(100,500) を求める

現在、正しい結果を与える明示的な式があり、完全に計算可能です。ただし、私が理解しているように、Project Euler の問題の解決策は、明示的な数式計算ではなく、より巧妙なアルゴリズムに似ている必要があります。解決策を再帰として定式化しようとすると、迷路のサイズに応じて変数の数が指数関数的に増加する線形システムにしか到達できませんでした (より正確には、m を固定して mxn 迷路の数の再帰を記述しようとすると、変数の数が m とともに指数関数的に増加するような線形システムに到達します。変数の 1 つは、問題 380 の宣言で指定されたプロパティを持つ mxn 迷路の数であり、他の変数は mxn 迷路の数です。特定の「迷路の境界に接する複数の連結成分」

問題をより簡単に解決できる部分問題に減らし、より大きな部分問題の解決策を構築するときに部分問題の解決策を再利用することも考えました (動的計画法のアプローチ) が、ここで、部分問題には不規則な迷路が含まれているように見えるという事実に出くわしました。このような迷路の数は m,n で指数関数的です。

誰かが明示的な式やアドホックな定理を使用する以外に実行可能なアプローチ (m=100、n=500) を知っていて、どこを見ればよいかを示唆できる場合、私にとっては非常に興味深いものです。

4

4 に答える 4

5

これは基本的にスパニング ツリーカウントの問題です。具体的には、グリッド グラフでスパニング ツリーの数をカウントしています。

グリッド グラフでのスパニング ツリーのカウント

ウィキペディアのエントリの「スパニングツリーのカウント」セクションから：

連結グラフのスパニング ツリーの数 t(G) は、よく研究されている不変量です。場合によっては、t(G) を直接計算するのが簡単です。たとえば、G 自体がツリーである場合、t(G)=1 であり、G が n 個の頂点を持つサイクル グラフ C_n である場合、t(G)=n です。任意のグラフ G について、数 t(G) はKirchhoff の行列木定理を使用して計算できます...

関連アルゴリズム

グリッド グラフのスパニング ツリーの数のカウントに関連するいくつかの論文または投稿を次に示します。

Ekhad と Zeilberger による後者は、当面の問題と一致する回答とともに、以下を提供しました。

マクローリン展開 (z に関する) における zn の係数が m x n グリッド グラフ ( m=2 から m=6 までの m 個の頂点のパスと長さ n) のパスのデカルト積、入力 は出力を与えます。

具体的には、出力を参照してください。

補足: 別の方法を示唆する提供された解の値がなければ、有効な解釈は、迷路の外部構造が重要であるということになる可能性があります。この場合、同じパスを持つ 2 つ以上の迷路は異なり、明確になります。コーナーで迷路に出入りするための 3 つのオプションがある可能性があるためです。または左側と上部の両方が開き、コーナーの出口も同様です。これらの迷路の可能性をツリーとして表現しようとすると、2 つのノードが最初から最後まで分岐するのではなく、入り口で収束する可能性があり、出口の可能性のために 1 つ以上の追加ノードが存在することになります。これにより、C(m,n) の値が増加します。

于 2013-02-28T15:15:04.933 に答える
4

ここでの洞察は質問から来ています（強調は私のものです）

.. 迷路は、左上の正方形から他の正方形へのパスが 1 つだけ存在するように、グリッド セルの間に壁が配置された長方形のグリッドです。

迷路の二重性、つまり人が占有できるスペースについて考えると、迷路がグラフを形成しなければならないことは明らかです。グラフだけでなく、特異なパスが存在するためには、グラフにツリーになるサイクルが含まれていてはなりません。組み合わせ問題へのこの縮小は、アルゴリズムを示唆しています。Project Euler の精神に則り、残りは読者への演習として残します。

于 2013-02-28T21:46:25.957 に答える
1

スポイラーアヘッド

私は間違っていました。コメントの 1 つで、「現在、グラフ内のツリーのスパンに関する一般的な定理はありますが、求められる数を計算するための計算的に実行可能な方法を提供しているようには見えません」と述べています。Kirchhoff に起因する Matrix-Tree 定理であり、ここでの回答の 1 つで参照されている「一般定理」は、グラフの次数で割ったグラフ ラプラシアンの非ゼロ固有値の積としてだけでなく、結果を与えます。だけでなく、ラプラシアンの補因子の絶対値としても使用できます。この場合、49999x49999 行列の行列式の絶対値です。しかし、マトリックスは非常にまばらですが、それでも私には手の届かないものに見えました。

ただし、参照

http://arxiv.org/pdf/0712.0681.pdf

(「ブロック三重対角行列の行列式」、Luca Guido Molinari 著) により、問題を非常に大きな整数をエントリとして持つ整数の 100x100 密行列の行列式の評価に減らすことができました。

さらに、リファレンス

http://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf

Erwin H. Bareiss (通常、「Bareiss アルゴリズム」について話すだけですが、参照で式 (8) と呼ばれる、私が使用した再帰は、ルイス キャロルとしても知られるチャールズ ドジソンによるものと思われます :) ) 、その後、この最後の決定要因を評価し、元の問題に対する答えを得ることができました。

于 2013-04-04T08:02:04.600 に答える
0

明示的な式を見つけることは、オイラー問題を解決する正しい方法であると言えます。高速で、スケーリングできます。ただそれのために行く:)

于 2013-02-25T11:38:27.490 に答える