パスの数以下の問題が (x+y)!/x!y! であることがわかりません。.. X+Y アイテムのパスから X アイテムを選択することに由来することは理解していますが、x+y よりも x アイテムを選択し、x+y よりも y アイテムを選択しないのはなぜですか? なぜ x だけでなければならないのですか?
ロボットは、amxn グリッドの左上隅にあります (下の図では「開始」とマークされています)。ロボットは常に下または右にしか移動できません。ロボットは、グリッドの右下隅に到達しようとしています (下の図で「終了」とマークされています)。可能なパスはいくつありますか?
これはMukul Joshi's answerに多少基づいていますが、もう少し明確になることを願っています。
から0,0に移動するには、正確に回右に移動し、正確に回下x,yに移動する必要があります。xy
それぞれの右の動きを で表し0、下の動きをで表し1ます。
0との文字列がからへ1のパスを示すとします。このパスには と が含まれます。0,0x,yx 0y 1
ここで、そのような文字列をすべて数えたいと思います。x 0これは、とを含む文字列の順列の数を数えることと同じy 1です。この文字列はマルチセット (各要素は複数回出現する可能性がある) であるため、次のように計算できるマルチセット順列が必要です。は文字の総数、は一意の文字の数、 は一意の文字が繰り返されます。合計で文字があり、が繰り返され、が繰り返されるので、 になります。n!/(m1!m2!...mk!)nkmiix+y0x1y(x+y)!/x!y!
時間の複雑さ:
バックトラック/ブルートフォースの時間の複雑さには、これらすべてのパスを探索する必要があります。(x+y)!/x!y!葉がある木と考えてください。私は間違っているかもしれませんが、分岐因子を持つツリーのノード> 1の数は、葉の数の Big-O として表すことができると思います。したがって、最終的にO((x+y)!/x!y!)ノードになり、同じ時間の複雑さになります。
わかりました、その問題を解決するための解決策を提供します。
まず、解法アルゴリズムを決めましょう。すべてのセルがそこから最後に到達するまでのすべての可能なパスをカウントします。アルゴリズムはセルをチェックし、右と下のセルの合計をそこに書き込みます。これは、ロボットが下に移動して下のパスのいずれかをたどるか、右に移動して右側のパスのいずれかをたどることができるため、さまざまなパスの総数を追加するためです。これらの経路の多様性を証明することは、私にとって非常に明白です。ご希望があればコメントにて承ります。
セルの初期値は、一番下のセル (終了) では 1 になります。これは、このセルからそこに到達する (まったく移動しない) 方法が 1 つしかないためです。セルが存在しない場合 (たとえば、一番下のセルに一番下のセルを使用する場合)、値は 0 になります。
セル値を 1 つずつ作成すると、値が(x, y) セルにあるパスカルの三角形が生成されます。ここで、x はゴールからの Ox 距離、y は Oy 1 です。(x + y)! / x! / y!
複雑さについて言えばx * y、グリッド セルを反復します。各反復は一定時間です。バックトラッキングアルゴリズムを使用したくない場合は、上記の式を使用して、O(x * y) の代わりに O(x + y) を使用できます。
「X の動きを分散する方法はいくつありますか?」は追加しません。「Y ムーブを分散する方法はいくつありますか?」理由は 2 つあります。
＃1については、Xについて特別なことは何もないことに注意してください-私は簡単にYを選択して、「Yの動きとXの動きの分布は独立していません。Yの動きの構成ごとに、Xの可能な構成は1つだけです。動きます。」他の人が指摘したように、Y の動きを分配する方法の数を数えると、X の動きを分配する方法の数を数えたのと同じ結果が得られるのはそのためです。
さて、ここで説明です。
どのように進んでも目的地にたどり着くには、m 行 n 列のパスが必要です。
行を 1、列を 0 で表すとします。パスは m+n 文字の文字列です。ただし、m 1 と n 0 しか持てません。
m+n 個の異なる文字がある場合、順列の数は (m+n) になります! ただし、繰り返し文字がある場合は (m+n)!/m!n! になります。これを参照してください
もちろんこれは唯一無二でしょう。4*3 グリッドでテストすると、それが表示されます。