Heuristi c для поиска A *, чтобы собрать максимальное количество монет в 2D сетке? - PullRequest
Новая
       85

Heuristi c для поиска A *, чтобы собрать максимальное количество монет в 2D сетке?

0 голосов
/ 25 апреля 2020

Принимая во внимание описание сетки NxM (начальная ячейка, ячейка назначения, недоступные ячейки, ячейки с монетами), используйте алгоритм поиска пути A * для прохождения сетки от начальной ячейки до ячейки назначения, пока сбор максимально возможного количества монет с учетом следующих ограничений: 

1- Use only horizontal and vertical movement, diagonal movement is not allowed.
2- Each cell can be visited at most once.
3- Each cell can have at most 1 coin.

Вот пример (0 обозначает пустую ячейку, 1 обозначает ячейку с монетой, X обозначает недоступную) ячейка, S - начальная ячейка, D - ячейка назначения):

S , X, X, X, X, X, X, X

1 , Х, Х, Х, Х, Х, Х, Х, Х

0 , Х, Х, Х, Х, Х, Х, Х

1 , 1 , 1 , X, X, 0 , 1 , 0

0, X, 0 , X, X, 0 , X, 0

0, X, 0 , 1 , 1 , 1 , X, 1

0 , 1, 0, 0, 0, 0, 0, D

Оптимальные ячейки пути: полужирный .

Обратите внимание, что меня не интересует фактическая реализация решения, Мне нужна только помощь в поиске подходящей функции heuristi c для правильного моделирования этой проблемы.

1 Ответ

1 голос
/ 26 апреля 2020

tldr; A * и максимальное количество единиц: возможно, но не хорошо

Первая проблема заключается в определении правильного расстояния.

Пусть состояние будет позицией в сетке + количество выбранных единиц.

Соседи - это тривиально соседние квадраты, не являющиеся X

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

d(a,b) = -(b.ones - a.ones)
  • , поэтому для соседа b, если мы выберем 1, расстояние равно -1
  • , если нет выбора, то 0

При минимизации d будет максимальное число 1.

Относительно heuristi c, чтобы обеспечить оптимальное решение, нам нужно h допустимое и мы можем определить h как h(s) = -56 (ваша сетка 7x8), h(s) = 56 - s.ones или даже h(s) = numberOfOnesInTheGrid - s.ones (хотя из последующего подразумевается, что мы заранее знаем, сколько 1s есть)

ОДНАКО это не подходит для A *, потому что:

  • мы хотим исследовать все пути / заявляет, когда цель A * состоит в том, чтобы избежать того, что ...
  • мы подвергаем себя циклам (где мы жадно ели до ...длинный). Это симптом c и не возникает при проблемах кратчайшего пути (с положительными взвешенными краями), поскольку езда на велосипеде всегда приводит к выбрасыванию более длинного пути
  • , то, что мы хотим, по своей природе является самым длинным проблема пути, а не самая короткая (например, евклидово расстояние до D против максимального числа 1 (или числа посещенных состояний с условием, имеющим 1)).

Боюсь, что A * не даст удовлетворительного результата Результаты. Более простая сетка (извлеченная из вашего примера), демонстрирующая проблему: 

0 , 1 , 0
0 , X , 0
S , X , 1
0 , 0 , D

верхний путь длиннее (с точки зрения посещаемых квадратов), но является оптимальным

. Вы всегда можете применить A * сохраняя посещенные пути / состояния в каждом состоянии (чтобы избежать циклов), но вы также можете просто использовать dfs с heuristi c для взятия соседей с 1 первым

...