алгоритм поиска минимальных шагов для завершения пути

Question

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

• нажмите белую кнопку, чтобы перейти на 2 клетки вперед. Если осталось менее 2 квадратов, затем эта кнопка завершается игра и вы выиграете.

• нажмите красную кнопку, чтобы перейти на 3 клетки вперед. Если осталось менее 3 квадратов, затем эта кнопка завершается игра и вы выиграете.

• нажмите зеленую кнопку, чтобы переместиться на 5 клеток вперед. Если осталось менее 5 квадратов, затем эта кнопка завершается игра и вы выиграете.

правила: каждый квадрат окрашен в синий и зеленый цвета. если игрок остановится на зеленом квадрате. он проиграл.

как спроектировать алгоритм поиска:

1. минимальные шаги, необходимые для завершения игры

2. кнопки должны быть нажаты, чтобы выиграть.

Answer 1

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

Начните с последней записи в пути:

• Если это синий:
  • Если после этого места осталось менее 5: свяжите зеленый ход (5 шагов) с этой записью
  • В противном случае проверьте каждую из точек, которые находятся на 2, 3 и 5 впереди на пути (которые уже были обработаны): выберите ту, которая имеет наилучшее решение (наименьшее количество ходов), связанную с ней. Расширьте (добавьте) это решение соответствующим ходом (2 = белый, 3 = ... и т. Д.) И сохраните эту информацию в текущей записи.

Повторите это для каждой предыдущей записи в пути, каждый раз сохраняя информацию о кратчайшем пути оттуда до выигрыша (если он синий)

Решение - это то, что было сохранено в первой записи пути. Конечно, бывают ситуации, когда победа невозможна.