Минимальное количество прыжков для достижения конечного динамического программирования - PullRequest
Новая
       54

Минимальное количество прыжков для достижения конечного динамического программирования

0 голосов
/ 21 октября 2019

Для данного массива проверьте, с первого элемента, сколько шагов необходимо для достижения конца.

Пример: arr = [1, 3, 5, 8, 4, 2, 6, 7, 0, 7, 9]

1 -> 3 -> 8 (это кратчайший путь)

3 шага.

Пока у меня есть этот код от гиков дляВундеркинды: 

def jumpCount(x, n): 
  jumps = [0 for i in range(n)] 

  if (n == 0) or (x[0] == 0): 
      return float('inf') 

  jumps[0] = 0


  for i in range(1, n): 
      jumps[i] = float('inf')   
      for j in range(i): 
          if (i <= j + x[j]) and (jumps[j] != float('inf')): 
              jumps[i] = min(jumps[i], jumps[j] + 1) 
              break                 
  return jumps[n-1]     

def jumps(x):
  n = len(x)
  return jumpCount(x,n) 

x = [1, 3, 5, 8, 4, 2, 6, 7, 0, 7, 9]

print(jumps(x))

Но я хочу распечатать, какие числа сделали кратчайший путь (1-3-8). Как я могу адаптировать код, чтобы сделать это?

Я попытался создать список j, но поскольку 5 проверяется в цикле, он тоже добавляется.

Ссылка на проблему: https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

1 Ответ

0 голосов
/ 21 октября 2019

Основная идея заключается в том, что вам нужна вспомогательная структура, которая поможет вам отслеживать минимальный путь. Структуры такого типа обычно называют «обратными указателями» (в нашем случае вы могли бы назвать их «указателями прямого хода», так как мы идем вперед, да). Мой код решает проблему рекурсивно, но то же самое можно сделать итеративно. Стратегия такова: 

jumps_vector = [ 1, 3, 5, 8, 4, 2, 6, 7, 0, 7, 9 ]

"""
fwdpointers holds the relative jump size to reach the minimum number of jumps
for every component of the original vector
"""
fwdpointers = {}

def jumps( start ):
    if start == len( jumps_vector ) - 1:
        # Reached the end
        return 0
    if start > len( jumps_vector ) - 1:
        # Cannot go through that path
        return math.inf
    if jumps_vector[ start ] == 0:
        # Cannot go through that path (infinite loop with itself)
        return math.inf

    # Get the minimum in a traditional way
    current_min = jumps( start + 1 )
    fwdpointers[ start ] = start + 1
    for i in range( 2, jumps_vector[ start ] + 1 ):
        aux_min = jumps( start + i )
        if current_min > aux_min:
            # Better path. Update minimum and fwdpointers
            current_min = aux_min
            # Store the (relative!) index of where I jump to
            fwdpointers[ start ] = i

    return 1 + current_min

В этом случае переменная fwdpointers хранит относительные индексы, к которым я перехожу. Например, fwdpointers[ 0 ] = 1, поскольку я прыгаю на соседнее число, а fwdpointers[ 1 ] = 2, поскольку я буду прыгать на два числа в следующем прыжке.

Сделав это, только немного постобрабатываетсяв функции main(): 

if __name__ == "__main__":
    min_jumps = jumps( 0 )
    print( min_jumps )

    # Holds the index of the jump given such that
    # the sequence of jumps are the minimum
    i = 0
    # Remember that the contents of fwdpointers[ i ] are the relative indexes
    # of the jump, not the absolute ones
    print( fwdpointers[ 0 ] )
    while i in fwdpointers and i + fwdpointers[ i ] < len( jumps_vector ):
        print( jumps_vector[ i + fwdpointers[ i ] ] )
        # Get the index of where I jump to
        i += fwdpointers[ i ]
        jumped_to = jumps_vector[ i ]

Я надеюсь, что это ответило на ваш вопрос.

РЕДАКТИРОВАТЬ: Я думаю, что итерационная версия более читабельна: 

results = {}
backpointers = {}
def jumps_iter():
    results[ 0 ] = 0
    backpointers[ 0 ] = -1
    for i in range( len( jumps_vector ) ):
        for j in range( 1, jumps_vector[ i ] + 1 ):
            if ( i + j ) in results:
                results[ i + j ] = min( results[ i ] + 1, results[ i + j ] )
                if results[ i + j ] == results[ i ] + 1:
                    # Update where I come from
                    backpointers[ i + j ] = i
            elif i + j < len( jumps_vector ):
                results[ i + j ] = results[ i ] + 1
                # Set where I come from
                backpointers[ i + j ] = i

    return results[ len( jumps_vector ) - 1 ]

И постобработка: 

i = len( jumps_vector ) - 1
print( jumps_vector[ len( jumps_vector ) - 1 ], end = " " )
while backpointers[ i ] >= 0:
    print( jumps_vector[ backpointers[ i ] ], end = " " )
    i = backpointers[ i ]
print()
...