Нахождение максимального маршрута в данном входе [закрыто]

У меня есть это как домашнее задание, и мне нужно сделать это на Python.

<code>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. 
</code>

Не уверен, как это сделать ....

 Kendall Frey07 апр. 2012 г., 16:03
Я узнаю это ...projecteuler.net/problem=18
 Kendall Frey07 апр. 2012 г., 17:48
@Abhijit: Что заставляет тебя так говорить? Пример треугольника такой же. Я не вижу ничего, что предполагало бы, что это отличается.
 Abhijit07 апр. 2012 г., 17:40
@KendallFrey: это отличается от Эйлера 18
 jamylak07 апр. 2012 г., 12:29
Нвм хорошо ....
 jamylak07 апр. 2012 г., 12:32
нет, я подумал, что это должно быть в радиусе одного номера от примера, я должен был сначала прочитать его, но забыл прокрутить в сторону -_-

Ответы на вопрос(4)

Решение Вопроса

Мы можем решить эту проблему с помощью возврата. Чтобы сделать это для каждого элемента треугольника в любой данной строке, мы должны определить максимум суммы текущего элемента и трех соединенных соседей в следующей строке, или

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

для элемента в позиции (строка, столбец) подключенный сосед в строке = следующий будет[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]):

а затем мы используем перечисление для создания кортежа индекса и самого элемента

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

Читая комментарий Джеймилака, я понял, что эта проблема похожа на Эйлера 18, но разница в представлении. Задача в Эйлере 18 рассматривает пирамиду, где проблема в этом вопросе имеет прямоугольный треугольник. Как вы можете прочитать мой ответ на его комментарий, я объяснил причину, почему результаты будут другими. Тем не менее, эту проблему легко перенести на работу с Euler 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])
>>>
 07 апр. 2012 г., 17:01
Примечание: в настоящее время ваш код работает только на меньших треугольниках. Проверьте это на задаче Эйлера 18 треугольника. У меня была такая же проблема, но я исправил возможные пути. Производит1116 вместо1074
 07 апр. 2012 г., 17:40
Это работает на его вопрос, хотя, и я уже добавил комментарий: D
 07 апр. 2012 г., 17:39
@jamylak: см. мое обновление в ответ. Это также будет работать для пирамиды с небольшой настройкой. Также я добавлю комментарий к вашему ответу, чтобы люди, читающие его, могли понять, что это не будет работать для вопроса ОП.
 07 апр. 2012 г., 17:35
У меня сложилось впечатление, что это было то же самое, что и точно такой же пример ... Я просто собираюсь покинуть свою "пирамиду". код тогда ...
 07 апр. 2012 г., 17:28
@jamylak: И вы можете видеть, почему существует несоответствие. Проблема в этом примере для прямоугольного треугольника, а проблема Эйлера 18 - это пирамида. У пирамиды есть два соседа, где в качестве прямоугольного треугольника - 3. Для Треугольника - сосед для «75». который находится в строке 6, индекс 4 имеет три соседа {77,73,7}, где, как и в пирамиде, он имеет два {73,07}. Этот ответ можно легко перенести на Euler 18, изменив функциюneigh

Я дам вам несколько советов по этому конкретному делу. Попробуйте создать обобщенную функцию для 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)])

[EDIT] Так как каждый разместил свои ответы здесь, это мое.

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]

Хотя это домашнее задание, @abhijit дал ответ, и я тоже!

Чтобы понять это, вам нужно прочитать о генераторах Python, возможно, придется погуглить его;)

>>> 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 принимает генераторы, так как они являются итеративными, поэтому нам не нужно преобразовывать его в список.

>>> max(routes(triangle),key=sum)
[3, 7, 4, 9]
 07 апр. 2012 г., 16:10
Мне нравится, как вы использовали генератор для этой цели. Но разве это не имеет сложности O (n ^ 2)?
 07 апр. 2012 г., 17:44
Н-м-м, я отменил это, теперь он просто работает, как и раньше, поэтому он работает для вопроса ОП, лучше оставить так;)
 07 апр. 2012 г., 16:12
Возможно, но мое решение было больше для простоты, чтобы помочь ему понять, как это сделать, я не имел в виду скорость. Я сейчас посмотрю ваш, чтобы узнать, как это сделать быстрее: D
 07 апр. 2012 г., 17:40
Это не будет работать для ОП вопрос. Смотрите обсуждение ниже мой ответ

Мой ответ

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)

выход

l5=[
      [3],
      [7, 4],
      [2, 4, 6],
      [8, 5, 9, 3],
      [15,10,2, 7, 8]
     ]
print(maxpath(l5)
>>>[35]
 24 мая 2013 г., 19:26
это неправильно только потому, что у меня был другой уровень [15,10,2, 7, 8], если вы используете правильный ввод
 lakesh14 сент. 2012 г., 03:30
Ваш ответ кажется неправильным ... Значение max path должно быть 33 верно?

Ваш ответ на вопрос