динамический алгоритм для поиска оптимального решения

Question

с учетом игры, наскучившей белыми и красными квадратами, упорядоченными следующим образом:

(начало окончено)

ш = белый. r = красный.

есть 3 кнопки. зеленая кнопка: переместить 5 шагов. желтая кнопка: переместить 3 шага. синяя кнопка: переместить 3 шага.

правила игры: - если игроки приземляются на красный квадрат, проигрывают. - первый игрок заканчивает игру победой. - допускается земля на белом квадрате.

жадный алгоритм:

x = 0 
steps = 0
stop = false
while (....)
if a[x+5] is white then
 push the green buttton and x= x+5, steps++
if a[x+3] is white then
 push the yellow buttton and x= x+3, steps++
if a[x+2] is white then
 push the blue buttton and x= x+2, steps++
else stop = true

требуется: минимальные шаги, чтобы выиграть игру.

следуя жадному алгоритму, приведенному выше, решение будет 552225, тогда как оптимальное решение - 33555.

У меня вопрос, как применить динамический алгоритм, чтобы найти оптимальное решение?

Answer 1

Идея: Думайте задом наперед. Предположим, вы в i. Какие есть варианты для достижения этой ячейки?

// Assume cell[i] = min number of moves to last cell starting from this cell

cell[n] = 0 //finish cell
cell[0..n-1] = ∞

for i = n to 1
  cell[i-1] = min(cell[i-1], cell[i]+1) //if cell[i-1] not red
  cell[i-3] = min(cell[i-1], cell[i]+1) //if cell[i-3] not red
  cell[i-5] = min(cell[i-1], cell[i]+1) //if cell[i-5] not red

В конце значение cell[0] показывает минимальные шаги, необходимые для завершения игры.

Answer 2

Чтобы добраться до финиша, вы должны сначала приземлиться на

finish - 5 или finish - 3 или finish - 2, а затем оттуда еще 1 нажатие кнопки, чтобы достичь finish.

Рекурсивная формула для этого:

minSteps(end) = 1 + Math.min( minSteps(end-5), Math.min(minSteps(end-2), minSteps(end-3)) )

Вы можете закодировать это как в (Java) с памяткой:

private static int minSteps( int start, int end, String s ) {
    if ( end < start ) return Integer.MAX_VALUE;
    if ( end == start ) return 0;
    if ( s.charAt(end) == 'r' ) {
      dp[end] = Integer.MAX_VALUE;
      return dp[end];
    }
    if ( dp[end] != -1 ) return dp[end];
    int stepTwo = minSteps( start, end - 2, s );
    int stepThree = minSteps( start, end - 3, s);
    int stepFive = minSteps( start, end - 5, s );
    int min = Math.min( Math.min( stepTwo, stepThree ), stepFive );
    if ( min != Integer.MAX_VALUE ) {
      dp[end] = 1 + min;
    } else {
      dp[end] = min;
    }
    return dp[end];
}

Для ввода: w w w w w w r r w w w w r w r w r w результирующий массив dp будет:

[-1, 2147483647, 1, 1, 2, 1, 2147483647, 2147483647, 2, 3, 2, 3, 2147483647, 3, 2147483647, 3, -1, 4] и ответ 4: 18 -> 16 -> 11 -> 6 -> 1

тогда вы можете строить свои прыжки с конца, следуя массиву dp.

Answer 3

То, что вы хотите сделать, это создать массив, содержащий минимальную стоимость и лучший предыдущий ход. Вы заполняете его от начала до конца, а затем читаете оптимальное решение от конца до начала. Так вот так:

min_cost = [infinite for all steps]
arriving_move = [none for all steps]
For each i in 0 to steps-1:
    if square[i] = 'r':
        pass
    else:
       for j in 2, 3, 5:
           if i <= j:
               if min_cost[i-j] + 1 < min_cost[i]:
                   min_cost[i] = min_cost[i-j] + 1
                   arriving_move[i] = j
reversed_answer = []
i = steps-1
while arriving_move[i] is not none:
    reversed_answer.append(arriving_move[i])
    i = i - arriving_move[i]
answer = reversed(reversed_answer)

Обратите внимание, это поможет найти оптимальную игру, в которой вы окажетесь прямо на финише. Поэтому в вашем примере ходы получатся 33553.

Если у вас все в порядке с "превышением метки", вам придется добавить специальный конечный узел со своими собственными специальными правилами в конце.