Encontrar la ruta máxima en una entrada dada

Tengo esto como una tarea y necesito hacerlo en 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. 

No estas seguro de cómo hacerlo….

Podemos resolver este problema utilizando el backtracking. Para hacer eso para cada elemento del triángulo en cualquier fila dada, debemos determinar el máximo de la sum del elemento actual y los tres vecinos conectados en la siguiente fila, o

 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]) 

Primero trata de encontrar una manera de determinar los connected_neighbors of col in row

para un elem en posición (fila, columna), el vecino conectado en la fila = siguiente sería [next[col-1],next[col],next[col+1]] siempre col - 1 >=0 y col+1 < len(next) . Aquí está una implementación de ejemplo

 >>> def neigh(n,sz): return [i for i in (n-1,n,n+1) if 0<=i 

Esto devolverá el índice de los vecinos conectados.

ahora podemos escribir backtrack_elem = max([elem + i for i in connected_neighbors of col in row]) como

 triangle[row][i] = max([elem + next[n] for n in neigh(i,len(next))]) 

y si iteramos el triángulo en el sentido de las filas y curr es cualquier fila dada, entonces i es el índice de la columna i de la fila, entonces podemos escribir

 curr[i]=max(next[n]+e for n in neigh(i,len(next))) 

ahora tenemos que iterar el triángulo leyendo la fila actual y la siguiente juntos. Esto se puede hacer como

 for (curr,next) in zip(triangle[-2::-1],triangle[::-1]): 

y luego usamos enumerar para generar una tupla de índice y el propio elem

 for (i,e) in enumerate(curr): 

Clubbing entonces juntos tenemos

 >>> 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))) 

Pero la operación anterior es destructiva y tenemos que crear una copia del triángulo original y trabajar en ello.

 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 

Así que tenemos que usar el módulo de deepcopy

 import copy route = copy.deepcopy(triangle) #This will work 

y reescribir la transversal como

 >>> 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))) 

Terminamos con otro triángulo donde cada elemento da el mayor costo de ruta posible. Para obtener la ruta real, tenemos que usar el triángulo original y calcular hacia atrás

así que para un elemento en el índice [row,col] , el costo de ruta más alto es la ruta [fila] [columna]. Si sigue la ruta máxima, entonces el siguiente elemento debe ser un vecino conectado y el costo de la ruta debe ser ruta [fila] [col] - orig [fila] [col]. Si iteramos fila sabiamente podemos escribir como

 i=[x for x in neigh(next,i) if x == curr[i]-orig[i]][0] orig[i] 

y deberíamos hacer un bucle hacia abajo comenzando desde el elemento pico. Asi tenemos

 >>> 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] 

Tomemos un poco complejo ejemplo, ya que el tuyo es demasiado trivial para resolver

 >>> triangle=[ [3], [7, 4], [2, 4, 6], [8, 5, 9, 3], [15,10,2, 7, 8] ] >>> route=copy.deepcopy(triangle) # Create a Copy 

Generando la ruta

 >>> 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]] 

y finalmente calculamos la ruta.

 >>> 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) 

Para probar nuestro triángulo tenemos

 >>> enroute(triangle) ([37], [3, 7, 4, 8, 15]) 

Al leer un comentario de jamylak, me di cuenta de que este problema es similar al de Euler 18, pero la diferencia es la representación. El problema en Euler 18 considera una pirámide donde, como el problema en esta pregunta es un triángulo rectángulo. Como puede leer mi respuesta a su comentario, expliqué la razón por la cual los resultados serían diferentes. Sin embargo, este problema puede ser fácilmente portado para trabajar con Euler 18. Aquí está el puerto

 >>> def enroute(triangle,neigh=lambda n,sz:[i for i in (n-1,n,n+1) if 0<=i>> 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>> 

A pesar de que esto es tarea, @abhijit dio una respuesta, ¡yo también lo haré!

Para comprender esto, necesitará leer sobre los generadores de Python, puede que tenga que buscarlo en Google;)

 >>> triangle=[ [3], [7, 4], [2, 4, 6], [8, 5, 9, 3] ] 

El primer paso es encontrar todas las rutas posibles.

 >>> 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 

Esto da

 >>> 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]] 

Para obtener el máximo es simple ahora, max acepta generadores ya que son iterables, por lo que no necesitamos convertirlos en una lista.

 >>> max(routes(triangle),key=sum) [3, 7, 4, 9] 

Te daré algunos consejos sobre este caso específico. Intenta crear una función generalizada para un triángulo de n pisos.

 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)]) 

[EDITAR] Ya que todos publicaron sus respuestas aquí es mía.

 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] 

Mi respuesta

 def maxpath(listN): liv = len(listN) -1 return calcl(listN,liv) def calcl(listN,liv): if liv == 0: return listN[0] listN[liv-1] = [(listN[liv-1][i]+listN[liv][i+1],listN[liv-1][i]+listN[liv][i]) \ [ listN[liv][i] > listN[liv][i+1] ] for i in range(0,liv)] return calcl(listN,liv-1) 

salida

 l5=[ [3], [7, 4], [2, 4, 6], [8, 5, 9, 3], [15,10,2, 7, 8] ] print(maxpath(l5) >>>[35]