2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Эвристика для пятнашек.
Сообщение06.01.2018, 02:07 
Аватара пользователя
Прочитал, алгоритм для решения пятнашек 3х3. Использовался алгоритм A* эвристика там была = Количество ходов + Неправильно расположенные элементы. Так вот меняется ли она при переходе с 3х3 на 4х4 пятнашки. Ну или вообще какую эвристику выбрать для 4х4 пятнашек.

 
 
 
 Re: Эвристика для пятнашек.
Сообщение06.01.2018, 04:05 
Корректная эвристика не зависит от размера доски. Но вам надо убедиться, что она корректна.

Для 4x4 понадобится достаточно памяти для хранения priority queue. Если исходное состояние случайно и терминальное состояние недостижимо, то а-стар попытается посетить все возможные ветки поиска. А для такой доски это много.

 
 
 
 Re: Эвристика для пятнашек.
Сообщение07.01.2018, 10:52 
https://resetius.ru/programs/15.html

Правда скопировать оттуда работающий код у меня не получилось. Пришлось писать свою, но с использованием наработок - в частности сдёрнул оттуда алгоритм Манхеттена и тест на собираемость случайной позиции.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group