このアルゴリズムは最適化されていますか？それ以外はどのように使用されますか？

Question

私はProject Eulerの問題（number 15, lattice paths）に取り組んでいます。私は別の方法で問題を解決しましたが、私は最初に問題を解決しようとしたアルゴリズムを最適化する方法について興味があります。なぜなら、非常に迅速に成長し、実際にどれくらい時間がかかるかに驚いているからです。だから私はアルゴリズムを分析し、アルゴリズムを最適化する方法を学びたいと思っています。

このアルゴリズムの手法は、左上に(0,0)、右下に(2,2)、角として2x2グリッドを使用します。上の点からは、パスはx+1またはy+1になります。だから私は、グリッド内の点のスペースに次の許容される移動が存在するかどうかをチェックすることによって、これらのパスをほぼ繰り返し作成します。

最初は左上(x+1, y+1)から始めましたが、下から後方に移動し、いくつかの冗長性を取り除き、貴重なデータだけをメモリに格納することが効率的であることがわかりました。それで私は今どこにいるのですか。これ以上最適化することはできますか？これにはどんな種類のアプリケーションがありますか？

givenPointsは、グリッド内のすべての点のリストであり、文字列として格納されます。つまり、'0202'です。アルゴリズムは、経路全体ではなく固有経路の最新の点を記憶し、最後にリスト内の項目の数は一意の経路の数に等しい。

def calcPaths4(givenPoints): 
    paths = [] 
    paths.append(givenPoints[-1]) 
    dims = int(math.sqrt(len(givenPoints))) - 1 
    numMoves = 2*dims 
    numPaths = 0 

    for x in range(0,numMoves): 
     t0= time.clock() 
     newPaths = [] 
     for i in paths: 
      origin = int(i) 
      dest1 = origin - 1 
      dest3 = origin - 100 
      if ('%04d' % dest1) in givenPoints: 
       newPaths.append(('%04d' % dest1)) 
       numPaths +=1 
      if ('%04d' % dest3) in givenPoints: 
       newPaths.append(('%04d' % dest3)) 
       numPaths +=1 
     t= time.clock() - t0 
     paths = newPaths 
     print(str(x)+": " +str(t)+": " +str(len(paths))) 
    return(paths) 

Answer 1

あなたは間違ったアプローチをしています。左上から右下に向かって右に20回、下に20回移動します。

だから、downあるrightと10要素です10個の要素を持つ長さ20のシーケンスとして任意のパスを考えることができます。どれくらいの強さがあるのか​​を数えるだけです。

rightの移動が完了したら、downのものは固定されているので、全体の問題は次のようになります。20個のセットから10個の位置を選択できますか？

これは単にbinomial coefficientによって解決されます。

従って溶液である：いずれかを意味するパスの数が急速に成長する

import operator as op 
from functools import reduce 

def number_of_paths(k): 
    """Number of paths from the top left and bottom right corner in a kxk grid.""" 
    return reduce(op.mul, range(2*k, k, -1), 1)//factorial(k) 

---

注：そのn!/(k!*k!) = (n·(n-1)···(k+1))/k!に注目することによって、より効率的にすることができる

from math import factorial 

def number_of_paths(k): 
    """Number of paths from the top left and bottom right corner in a kxk grid.""" 
    return factorial(2*k)//(factorial(k)**2) 

で動作するアルゴリズム異なるパスは遅くなるでしょう。これを真剣に「最適化」する唯一の方法は、アプローチを変更し、パスの作成を避けながら数えていくことです。 再帰とメモ化/動的プログラミング：

---

は異なる、より一般的なアプローチを指摘I''l。

パスが特定の位置にあるときは、(x,y)に移動します。これは、(x-1,y)に移動するか、(x, y-1)に移動します。だから、右下にそのポイントからのパスの数が(x-1,y)から右下に至るパスの数の和であると(x, y-1)から右下に達しているもの：あなたがエッジ上にある場合

ベースケースがありますすなわち、x==0またはy==0です。

def number_of_paths(x, y): 
    if not x or not y: 
     return 1 
    return number_of_paths(x-1, y) + number_of_paths(x, y-1) 

このソリューションは、あなたの推論に従うが、それだけでパスの数を追跡します。あなたは再びそれが非常に非効率的であることを見ることができます。

問題は、我々はnumber_of_paths(x, y) を計算しようとすると、私たちは、次の手順を実行してしまうということです。

• 計算number_of_paths(x-1, y)

  • これはnumber_of_paths(x-2, y)とnumber_of_paths(x-1, y-1)
を計算することによって行われます

• 計算number_of_paths(x, y-1)

  • これはnumber_of_paths(x-1, y-1)は二回計算方法number_of_paths(x-1, y-1)とnumber_of_paths(x, y-2)

注意を計算することによって行われます。しかし結果は明らかに同じです！

def number_of_paths(x, y, table=None): 
    table = table if table is not None else {(0,0):1} 
    try: 
     # first look if we already computed this: 
     return table[x,y] 
    except KeyError: 
     # okay we didn't compute it, so we do it now: 
     if not x or not y: 
      result = table[x,y] = 1 
     else: 
      result = table[x,y] = number_of_paths(x-1, y, table) + number_of_paths(x, y-1, table) 
     return result 

そして今、これはかなり速く実行されます：だから私たちはそれを我々はすでに知られている結果を返す呼び出して初めて、私たちが見る次の時間を計算することができます

>>> number_of_paths(20,20) 
137846528820 

あなたが実行する「と考えることができ2回の呼び出しは大したことではありませんが、(x-1,y-1)の呼び出しが2回計算されると、毎回(x-2, y-2)の呼び出しが2回行われるため、計算結果は(x-2, y-2)となり、回となります。そして、(x-3, y-3)8つの回、そして... (x-20, y-20)1048576回！我々はサイズの+1で終わるので、ここではテーブルが交差点を表し

def number_of_paths(x, y): 
    table = [[0]*(x+1) for _ in range(y+1)] 
    table[-1][-1] = 1 
    for i in reversed(range(x+1)): 
     for j in reversed(range(y+1)): 
      if i == x or j == y: 
       table[i][j] = 1 
      else: 
       table[i][j] = table[i+1][j] + table[i][j+1] 
    return table[0][0] 

注：

はまた、我々は右下からkxk行列とフィーユそれを構築している可能性があります。

これを後で再利用するために前回の呼び出しを記憶するというこの手法をメモ処理と呼びます。より一般的な原則は、動的なプログラミングです。ここでは、再帰とメモを使用して表形式のデータ構造を満たすことに問題を基本的に減らし、先に入力したポインタを使用してセルを「バックトラック」して、問題。