グリッド内の 2 つのノード間のすべてのパスを見つけようとしていますが、パスは最初から最後まですべてのノードを通過する必要があります。例 (開始 = S、終了 = E)
0 0 0
0 S 0
0 0 エ
上記の答えは 2 つのパスです: (「.」は無視してください)
0-0-0
|.......|
0 S-0
|
0-0-E
0-0-0
|……|
0 S 0
|...|...|
0-0 日
再帰を使用することを考えましたが、各呼び出しのオーバーヘッドが高いためにそれをあきらめました...そして、スタックを使用した反復アプローチを採用することにしました。(再帰のようなものですが、そうではありません...固定メモリオーバーヘッド)。このソリューションは、サイズ (4x7) のグリッドでうまく機能しますが、8x8 グリッドで試してみました...そして 4 時間で終了しませんでした...可能性の合計数が約 3 ** であるため、これは理にかなっていますエッジ上にない各ノードには 3 つのトラバーサル方法があるため、そのソリューションは失敗します。
縦と横の分割を使用して 8x8 グリッドを 2 つに分割することを考えましたが、これは理想的とは言えないパスを見つけることにつながります。
私が見逃しているものはありますか???? それを速くするために何かできることはありますか?明日の解決策を投稿します(Cで行います)。