再帰トラバーサルは

Question

はこの1つのように見えるでグラフを手に入れたポイントに道を数え、グラフの谷、0）となる。私は深さ優先検索でそれを行うことができると思います。どのように私は深さ優先検索を拡張する必要がありますので、いくつかの方法を2回カウントしないでください？ありがとう！

Answer 1

すべてのパスを実際にフォローしないでウェイの数を数えるのが最善の方法です。 F(x, y)を目的地に到着する方法の数にします。次に、グラフにはF(x, y) = F (x+1, y) + F (x, y+1) + F(x+1, y+1)が表示されます。あなたはF(0,0)が欲しいです。ベースケースはF(i, j) = 1（すでにそこにいる場合は1つの方法：どこにも行かないでください）とF(any number > i, any j) and F(i, any number > j) = 0になります。これを通過すると目的地に到達する方法がないためです。

詳細を更新：この式を評価する方法は？再帰的に行うことはできますが、素朴な実装は非常に非効率的です。素朴な実装では、単に緩くpythonのように見える擬似コードでこのようなものになるだろう。これに伴う問題は、あなたが（0,0）で開始した場合、再帰呼び出しのあなたの最初のレベルがなるということです

i = ... 
j = ... 
def paths (x, y): 
    if (x > i) or (y > j): 
     return 0   
    if (x == i) and (y == j): 
     return 1 
    else: 
     return paths (x+1, y) + paths (x, y+1) + paths (x+1, y+1) 
print F(0, 0) 

（0 、1）、（1,0）、（1,1）となる。これらの呼び出しが評価されると、（0、1）は（0、2）（1,1）、（1,2）を計算します。 （1、0）は（1,1）、（2,0）、（2,1）を計算し、（1,1）は（1,2）、（2,1）、 2、2）。これらの呼び出しのうち、同じ値を計算する点で、どれだけ多くの呼び出しが冗長であるかに注目してください。これを解決する手法は、Fの値を記憶している行列を保持することです。それではコードは次のようになります：

i = ... 
j = ... 
memorizedValues = ... #make an i by j grid filled with -1 
memorizedValues[i][j] = 1 #initial condition 

def paths (x, y): 
    if (x > i) or (y > j): 
     return 0 
    if (memorizedValues[x][y] != -1): #check for a memorized value before 
     return memorizedValues[x][y] # starting more recursion! 
    else: 
     memorizedValues[x][y] = paths (x+1, y) + paths (x, y+1) + paths (x+1, y+1) 
     return memorizedValues[x][y] 

print F(0, 0) 

これはまだ、最も効率的な実装ではありませんが、私はそれがポイントに伝わると思います。それはそれを追跡し、バックトラックすることによって各パスを数えるよりもかなり高速です！

Answer 2

BFSを使用してノードをマークするか、マップを使用してノードを追跡することができます。しかし、グラフが大きければ、BFSはそれをすべてメモリに保持する必要があります。 DFSはそれより優れています。ただし、DFSは深度制限をかけない限り大きなグラフで失われる可能性があります。

とにかく、あなたのプログラムをスピードアップするためにあなたが停止検討するかもしれないが、早期場合：

• ：
  • グラフは
  あなたはブリッジに到達

  その他のヒューリスティック切断されています次へ進む前に、まず学位1の隣人を訪ねてください。

私はそれを最適化することができますどのくらい参照するには、やや同様のプログラムを書いた： https://github.com/eamocanu/allPathsFinder