Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Прочитал, алгоритм для решения пятнашек 3х3. Использовался алгоритм A* эвристика там была = Количество ходов + Неправильно расположенные элементы. Так вот меняется ли она при переходе с 3х3 на 4х4 пятнашки. Ну или вообще какую эвристику выбрать для 4х4 пятнашек.
Paragraph
Re: Эвристика для пятнашек.
06.01.2018, 04:05
Последний раз редактировалось Paragraph 06.01.2018, 04:07, всего редактировалось 1 раз.
Корректная эвристика не зависит от размера доски. Но вам надо убедиться, что она корректна.
Для 4x4 понадобится достаточно памяти для хранения priority queue. Если исходное состояние случайно и терминальное состояние недостижимо, то а-стар попытается посетить все возможные ветки поиска. А для такой доски это много.
FomaNeverov
Re: Эвристика для пятнашек.
07.01.2018, 10:52
Последний раз редактировалось FomaNeverov 07.01.2018, 10:53, всего редактировалось 1 раз.
Правда скопировать оттуда работающий код у меня не получилось. Пришлось писать свою, но с использованием наработок - в частности сдёрнул оттуда алгоритм Манхеттена и тест на собираемость случайной позиции.