私はこれを宿題として持っており、Pythonで行う必要があります。
Problem:
The Maximum Route is defined as the maximum total by traversing from the tip of the triangle to its base. Here the maximum route is (3+7+4+9) 23.
3
7 4
2 4 6
8 5 9 3
Now, given a certain triangle, my task is to find the Maximum Route for it.
それを行う方法がわからない....
この問題は、バックトラッキングを使用して解決できます。任意の行の三角形の各要素に対してこれを行うには、現在の要素と次の行の3つの接続された隣接要素の合計の最大値を決定する必要があります。
if elem = triangle[row][col] and the next row is triangle[row+1] then backtrack_elem = max([elem + i for i in connected_neighbors of col in row])
まず、決定する方法を見つけてくださいconnected_neighbors of col in row
位置（row、col）の要素の場合、row=nextの接続されたネイバーが[next[col-1],next[col],next[col+1]]提供さcol - 1 >=0れcol+1 < len(next)ます。これがサンプル実装です
>>> def neigh(n,sz):
return [i for i in (n-1,n,n+1) if 0<=i<sz]
これにより、接続されているネイバーのインデックスが返されます。
今、私たちは次のように書くことができbacktrack_elem = max([elem + i for i in connected_neighbors of col in row])ます
triangle[row][i] = max([elem + next[n] for n in neigh(i,len(next))])
三角形を行方向に反復し、currが任意の行であり、iが行のi番目の列インデックスである場合、次のように記述できます。
curr[i]=max(next[n]+e for n in neigh(i,len(next)))
ここで、現在の行と次の行を一緒に読み取って三角形を繰り返す必要があります。これは次のように行うことができます
for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):
次に、enumerateを使用して、インデックスのタプルと要素自体を生成します
for (i,e) in enumerate(curr):
それから一緒にクラブをします
>>> for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):
for (i,e) in enumerate(curr):
curr[i]=max(next[n]+e for n in neigh(i,len(next)))
ただし、上記の操作は破壊的であり、元の三角形のコピーを作成して作業する必要があります
route = triangle # This will not work, because in python copy is done by reference
route = triangle[:] #This will also not work, because triangle is a list of list
#and individual list would be copied with reference
したがって、deepcopyモジュールを使用する必要があります
import copy
route = copy.deepcopy(triangle) #This will work
トラバースを次のように書き直します
>>> for (curr,next) in zip(route[-2::-1],route[::-1]):
for (i,e) in enumerate(curr):
curr[i]=max(next[n]+e for n in neigh(i,len(next)))
最終的に、すべての要素が可能な限り最高のルートコストを提供する別の三角形になります。実際のルートを取得するには、元の三角形を使用して逆算する必要があります
したがって、インデックスの要素の[row,col]場合、最も高いルートコストはroute[row][col]です。最大ルートに従う場合、次の要素は接続されたネイバーであり、ルートコストはroute [row] [col]-orig[row][col]である必要があります。行ごとに繰り返すと、次のように書くことができます。
i=[x for x in neigh(next,i) if x == curr[i]-orig[i]][0]
orig[i]
そして、ピーク要素から始めて下向きにループする必要があります。したがって、
>>> for (curr,next,orig) in zip(route,route[1:],triangle):
print orig[i],
i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]
あなたの例は簡単すぎて解決できないので、少し複雑な例を見てみましょう
>>> triangle=[
[3],
[7, 4],
[2, 4, 6],
[8, 5, 9, 3],
[15,10,2, 7, 8]
]
>>> route=copy.deepcopy(triangle) # Create a Copy
ルートの生成
>>> for (curr,next) in zip(route[-2::-1],route[::-1]):
for (i,e) in enumerate(curr):
curr[i]=max(next[n]+e for n in neigh(i,len(next)))
>>> route
[[37], [34, 31], [25, 27, 26], [23, 20, 19, 11], [15, 10, 2, 7, 8]]
最後にルートを計算します
>>> def enroute(triangle):
route=copy.deepcopy(triangle) # Create a Copy
# Generating the Route
for (curr,next) in zip(route[-2::-1],route[::-1]): #Read the curr and next row
for (i,e) in enumerate(curr):
#Backtrack calculation
curr[i]=max(next[n]+e for n in neigh(i,len(next)))
path=[] #Start with the peak elem
for (curr,next,orig) in zip(route,route[1:],triangle): #Read the curr, next and orig row
path.append(orig[i])
i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]
path.append(triangle[-1][i]) #Don't forget the last row which
return (route[0],path)
三角形をテストするには、
>>> enroute(triangle)
([37], [3, 7, 4, 8, 15])
jamylakのコメントを読んで、この問題はオイラー18に似ていることに気付きましたが、違いは表現です。オイラー18の問題はピラミッドを考慮していますが、この質問の問題は直角三角形です。彼のコメントに対する私の返事を読むことができるので、私は結果が異なる理由を説明しました。それでも、この問題はオイラー18で動作するように簡単に移植できます。これが移植です
>>> def enroute(triangle,neigh=lambda n,sz:[i for i in (n-1,n,n+1) if 0<=i<sz]):
route=copy.deepcopy(triangle) # Create a Copy
# Generating the Route
for (curr,next) in zip(route[-2::-1],route[::-1]): #Read the curr and next row
for (i,e) in enumerate(curr):
#Backtrack calculation
curr[i]=max(next[n]+e for n in neigh(i,len(next)))
path=[] #Start with the peak elem
for (curr,next,orig) in zip(route,route[1:],triangle): #Read the curr, next and orig row
path.append(orig[i])
i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]
path.append(triangle[-1][i]) #Don't forget the last row which
return (route[0],path)
>>> enroute(t1) # For Right angle triangle
([1116], [75, 64, 82, 87, 82, 75, 77, 65, 41, 72, 71, 70, 91, 66, 98])
>>> enroute(t1,neigh=lambda n,sz:[i for i in (n,n+1) if i<sz]) # For a Pyramid
([1074], [75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93])
>>>
これは宿題ですが、@abhijit が答えてくれたので、私も答えます!
これを理解するには、Python ジェネレーターについて調べる必要があります。Google で検索する必要があるかもしれません ;)
>>> triangle=[
[3],
[7, 4],
[2, 4, 6],
[8, 5, 9, 3]
]
最初のステップは、すべての可能なルートを見つけることです
>>> def routes(rows,current_row=0,start=0):
for i,num in enumerate(rows[current_row]): #gets the index and number of each number in the row
if abs(i-start) > 1: # Checks if it is within 1 number radius, if not it skips this one. Use if not (0 <= (i-start) < 2) to check in pyramid
continue
if current_row == len(rows) - 1: # We are iterating through the last row so simply yield the number as it has no children
yield [num]
else:
for child in routes(rows,current_row+1,i): #This is not the last row so get all children of this number and yield them
yield [num] + child
これは与える
>>> list(routes(triangle))
[[3, 7, 2, 8], [3, 7, 2, 5], [3, 7, 4, 8], [3, 7, 4, 5], [3, 7, 4, 9], [3, 4, 2, 8], [3, 4, 2, 5], [3, 4, 4, 8], [3, 4, 4, 5], [3, 4, 4, 9], [3, 4, 6, 5], [3, 4, 6, 9], [3, 4, 6, 3]]
max を取得するのは簡単です。max はジェネレーターを iterable として受け入れるので、それをリストに変換する必要はありません。
>>> max(routes(triangle),key=sum)
[3, 7, 4, 9]
この特定のケースについて、いくつかのヒントを提供します。n 階の三角形の一般化された関数を自分で作成してみてください。
triangle=[
[3],
[7, 4],
[2, 4, 6],
[8, 5, 9, 3]
]
possible_roads={}
for i1 in range(1):
for i2 in range(max(i1-1,0),i1+2):
for i3 in range(max(i2-1,0),i2+2):
for i4 in range(max(i3-1,0),i3+2):
road=(triangle[0][i1],triangle[1][i2],triangle[2][i3],triangle[3][i4])
possible_roads[road]=sum(road)
print "Best road: %s (sum: %s)" % (max(possible_roads), possible_roads[max(possible_roads)])
[編集]誰もがここに回答を投稿したので、私のものです。
triangle=[
[3],
[7, 4],
[2, 4, 6],
[8, 5, 9, 3]
]
def generate_backtrack(triangle):
n=len(triangle)
routes=[[{'pos':i,'val':triangle[n-1][i]}] for i in range(n)]
while n!=1:
base_routes=[]
for idx in range(len(routes)):
i=routes[idx][-1]['pos'] #last node
movements=range(
max(0,i-1),
min(i+2,n-1)
)
for movement in movements:
base_routes.append(routes[idx]+[{'pos':movement,'val':triangle[n-2][movement]}])
n-=1
routes=base_routes
return [[k['val'] for k in j] for j in routes]
print sorted(generate_backtrack(triangle),key=sum,reverse=True)[0][::-1]