だから、グリッドを通るパスの数を数えることに関する問題を解決しようとしています。問題は多かれ少なかれ次のとおりです。
x x y 次元の長方形のグリッドが与えられた場合、左上から左下まで、すべての頂点を 1 回だけ訪れるパスの数を計算します。
私は問題を力ずくで試してみましたが、O(n!) のようで、次元が大きいと非常に遅くなります。
私の現在の方法は、左上のノードから開始し、まだアクセスされていないすべての隣接ノードを再帰的にチェックし、backPath リストに保存します。関数がゴールに到達し、すべてのノードが訪問された場合、関数は backPath をソリューションのリストに追加して、パスの総数をカウントします。
ただし、これは非常に遅いです。アルゴリズムを改善する動的な方法があることは理解していますが (こちらの記事を含む)、動的プログラミングやメモ化にあまり詳しくないため、改善を実装する方法を理解するのに苦労しています。私がこれまでに行った唯一の改善点は、他のすべてのノードが訪問される前に関数が終了ノードをトラバースしないようにすることです。これにより、実行時間が約 40% 短縮されるだけです。私は DP の経験がなく、これまでチュートリアルを自分の問題に効果的に適用することができませんでした。
編集ここで同様の質問をしたところ、その回答により、実際に探していた情報についてより良い洞察が得られましたが、DP /その他の実行時間短縮方法をこの特定の問題に適用する方法にまだこだわっています。
助けてくれてありがとう。