algorithm - 特定のポイントを回避する長方形グリッド内の単調パスの数

Question

サイズが m*n の長方形グリッドでは、(0,0) から (m,n) まで (バックトラックなし) のパスの数は (m+n)!/(m!*n!) です。グリッド内に回避したい特定のポイントがある場合、それらのポイントを回避するパスの数をどのように計算できますか?

Answer 1

解を定義する (再帰的な) 方程式は次のとおりです。

• (m,n) から (m,n) への単調パスの数は 1
• 任意の禁止ポイントから (m,n) への単調パスの数は 0 です。これは、最初の座標が m より大きいか、2 番目の座標が n より大きいポイントでも同じです。
• 他の任意のポイント (x,y) から (m,n) への単調パスの数は、次の合計です。
  • (x+1,y) から (m,n) へのパスの数
  • (x,y+1) から (m,n) までのパスの数 (グリッドの外に移動するインクリメントの処理については上記を参照)

明らかに、Qnan が述べたように、これらを (0,0) について解くには、動的計画法 (つまり、指数時間を避けるために部分解を記憶する) を使用する必要があります。

Answer 2

正確に点がブロックされたグリッドの合理的な分析ソリューションはないと思いますがk、動的計画法アルゴリズムを使用してパスを数えることはできます。

ブロックされたパスの数は、ブロックされたノードの数と各ノードの位置だけでなく、それらの相対的な位置にも依存するため、分析ソリューションは面倒です。たとえば、4x4 グリッドでは、これら 2 つの構成は非常に異なる結果をもたらします。

....      ....
..x.      .xx.
.x..      ....
....      ....

前者では 2 つの単調なパスのみが許可されるのに対し、後者では少なくとも 5 つの単調なパスが許可されることが簡単にわかります。