0

アルゴリズムの最適化に行き詰まっています。

目標は、チェス盤の点 A から点 B に移動するために使用できる方法の数を見つけることです。

  • A は左下の正方形です。
  • B は右上の正方形です。
  • ピースは、各ターンに 1 つだけ上または 1 つの右に移動できます。

ここにダミーの解決策があります：

# -*- conding: utf-8 -*-
import time

def solution(n, m, x, y):
   ret = 0
   if x < n-1:
      ret += solution(n, m, x+1, y)
   if y < m-1:
      ret += solution(n, m, x, y+1)
   if x == n-1 and  y == m-1:
     ret = 1
   return ret

def wrapper(n, m):
    start = time.time()
    reponse = solution(n, m, 0, 0)
    stop = time.time()
    print "Response: %dx%d = %d\nTime : %f\n" % (n, m, reponse, stop-start)



if __name__ == "__main__":
    for i in range(10):
        wrapper(i+1,i+1)
    #wrapper(7,7)
    #wrapper(10,10)
    #wrapper(100,100)
    #wrapper(1000,1000)
    #wrapper(10000,10000) <- way too slow

私は小さなチェス盤を使用していますが、問題なく動作し、結果は適切です。しかし、私の目標は、10000x10000 ボードのソリューションを見つけることです。

アイデアはありますか？

4

4 に答える 4

4

このように考えてください。ポイントAとBは同じ場所にあるため、同じ量のUPとRIGHTを移動する必要がありますが、順序は異なります。したがって、さまざまな組み合わせの量を見つける必要があります。

于 2013-03-16T16:10:07.800 に答える
2

動的計画法：O（N）

パスカルの三角形とその二項係数との関係を使用することで問題が解決することはすでに述べました。また、カタラン数のエントリには、n × nの場合のわかりやすい図があります。

n × nの場合

前述のリソースを利用することにより、サイズn × nのグリッドの場合、C（2n-2、n-1）を計算する必要があると結論付けることができます。グリッドを45度回転し、パスカルの三角形をマッピングすることで、再確認できます。

実際には、この数を直接計算するには、単純な方法で最大3つの異なる階乗を計算する必要があり、これは非常にコストのかかる作業です。それらすべてを事前に計算できる場合、ここでの議論はなく、この問題には複雑さO（1）があると主張できます。事前に計算された方法に興味がない場合は、読み続けることができます。

動的計画法（DP）を使用して、このような不吉な数を計算できます。ここでの秘訣は、大きな階乗数を計算する必要がまったくない、より小さなステップで操作を実行することです。

つまり、C（n、k）を計算するには、まずC（n、1）に移動し、C（n、k）まで歩きます。C（n、k-1）の観点からC（n、k）を定義することから始めましょう。

C(n, k) = n! / k! * ( n - k )!                            ; k! = (k - 1)! * k
        = n! / (k - 1)! * k * (n - k)!                    ; (n - k)! = (n - k + 1)! / (n - k + 1)
        = n! * (n - k + 1) / (k - 1)! * k * (n - k + 1)!  ; C(n, k - 1) = n! / (k - 1)! * ( n - k + 1 )!
        = C(n, k - 1) * (n - k + 1) / k

これに基づいて、Pythonで次のようにC（n、k）を計算する関数を定義できます。

def C(n, k):
    """
    Calculate C(n, k) using Dynamic Programming.
    C(n, k) = C(n, k - 1) * (n - k + 1) / k
    """
    C = 1
    for ki in range(1, k + 1):
        C = C * (n - ki + 1) / ki
    return C

線形時間O（N）で実行されます。

n × nの場合、C（2n-2、n-1）を計算する必要があります。

>> print "Response: %dx%d = %d" % (n, n, C(2 * n - 2, n - 1),)
Response: 10000x10000 = 5...

n × mの場合

一般的なn × mの場合、C（n + m-2、m-1）を計算する必要があります。

>> print "Response: %dx%d = %d" % (n, m, C(n + m - 2, m - 1),)
Response: 10000x10000 = 5...

最後になりましたが、ここでIdeoneの実例を見ることができます。

タイミング

次のグリッドサイズのアルゴリズムを実行しました。

      N x N      | Response's Length |   Time
-----------------+-------------------+-----------
      1 x 1      |           1 chars |  0.000001
     10 x 10     |           5 chars |  0.000004
    100 x 100    |          59 chars |  0.000068
   1000 x 1000   |         600 chars |  0.002207
  10000 x 10000  |        6018 chars |  0.163647
 100000 x 100000 |       60203 chars | 40.853971

グリッドサイズが100000x 100 000を超える操作は、非常に多くの数が関係するため、途方もなく高価になるようです。しかし、驚くことは何もありません。

于 2013-03-16T23:36:48.103 に答える
1

このためのアルゴリズムは必要ありません。ただ数学。考えるべきことがあります。右上の正方形にいるときは、別の選択肢はありません。それをゼロとして数えましょう。右上隅のすぐ右側にいる場合、バックトラックすることは許可されていないため、右に進むしかありません（1つのオプション）。右上隅のすぐ下にいるときは、上に行くしかありません。それをマッピングしましょう

... 1 0
..... 1

ターゲットコーナーから左/下のコーナーはどうですか。そこから、角への2つのパスがあります（隣人に到達するためのオプションの合計）：右に上がることができます：

... 1 0
....2 1

エッジを拡張する場合は常にエッジを拡張します。上部に移動したら、右上に移動する方法は1つだけです。

...1 1 1 0
...... 2 1
........ 1
........=1

しかし、エッジ以外の各選択肢は、北と東の隣人の数の合計です。

...1 1 1 0
.....3 2 1
.......3 1
........ 1

等々。うまくいけば、これで解決策を始めることができます。

これについては別の考え方もあります。NxNボードを考えると、一方のコーナーからもう一方のコーナーに移動するには、2Nの移動を行う必要があります。これらの動きのNは北の動きであり、Nは東の動きです。問題は、2Nの長さのストリングに、N個の東の動きとN個の北の動きのさまざまな組み合わせがいくつあるかということです。

于 2013-03-16T16:11:42.723 に答える
0

パスカルの三角形を探しています。ウィキペディアのリンクには、あなたの正確な問題についても言及されています

于 2013-03-16T16:52:49.703 に答える