А что насчет памяти?
Может сразу есть смысл делать не А* а какой-то более экономичный алгоритм типа IDA*, MA*, SMA*, RBFS?
Какой из эвристических алгоритмов поиска самый лучший?
Да, это вы хорошо придумали с количеством ходов до места. Я сначала хотел брать просто расстояние по прямой без учета стен… хотя конкретно для этого уровня эти числа будут примерно равны, но для других могут значительно отличаться.
>Вопрос в том, влезет ли реализация в память.
А разве это так критично? Виртуальной-то памяти много, пусть свопается если не влазит.
Или даже лучше перенести списки вариантов из массива памяти в nosql key-value хранилище типа Redis'а, которое также добавит персистентность между запусками бота. А то сейчас при каждом запуске перебор начинается заново.
Прочитал википедию, но с первого раза не все понял, буду перечитывать. Там метрику определяют как f(x) = g(x) + h(x). Правильно я понимаю что вы предлагаете сделать g(x)=0, а h(x)=сумма_минимальных_расстояний(х)?
И почему-то в википедии на 2й анимации точки открываются по всему фронту а не только ближайшие к цели.
Тогда даже не рамка а «недо-рамка» — минимальным шаблоном будет рамка без 2х ящиков:
И ее можно увеличивать по длине, т.е. недо-рамки 3*N будут не сдвигаемы.
>рамка 3*3 не сдвигаема, 4*4 вполне
Я также не нашел способа раздвинуть рамку 4*4, можете показать решение?
Дело в том, что сейчас бот работает в терминах «сдвинуть 1й ящик влево». Как от этого алгоритма перейти к терминам «передвинуть 1й ящик в правый нижний угол карты за 20 движений» мне пока непонятно… тем более что возможно придется передвинуть ящик с конечной позиции дальше в противоположном направлении от стены чтобы освободить место для маневра.
>Далеко не факт, что 100 ходов хватит (у вас написано, что рекорд = 444).
Срываю покровы — на каком-то сайте находил таблицу всех уровней с указанием самого короткого решения. И почти все уровни уложились в 100 ходов, исключений было 2 или 3, и данный уровень один из этих исключений. Можно конечно эту границу поднимать, но проблема в том, что даже при 100 ходах оценка вариантов уже получается недостижимой.
>Какие эвристики у вас уже реализованы?
Добавил в статью «Дополнение об эвристиках».
Напомнило песню про тесто Елизарова https://ru-elizarov.livejournal.com/360200.html
github.com/ericmoritz/wsdemo/blob/results-v1/results.md
Может сразу есть смысл делать не А* а какой-то более экономичный алгоритм типа IDA*, MA*, SMA*, RBFS?
Какой из эвристических алгоритмов поиска самый лучший?
>Вопрос в том, влезет ли реализация в память.
А разве это так критично? Виртуальной-то памяти много, пусть свопается если не влазит.
Или даже лучше перенести списки вариантов из массива памяти в nosql key-value хранилище типа Redis'а, которое также добавит персистентность между запусками бота. А то сейчас при каждом запуске перебор начинается заново.
Прочитал википедию, но с первого раза не все понял, буду перечитывать. Там метрику определяют как f(x) = g(x) + h(x). Правильно я понимаю что вы предлагаете сделать g(x)=0, а h(x)=сумма_минимальных_расстояний(х)?
И почему-то в википедии на 2й анимации точки открываются по всему фронту а не только ближайшие к цели.
Но графы это далекая от меня область, что посоветуете почитать по реализации этого алгоритма?
И ее можно увеличивать по длине, т.е. недо-рамки 3*N будут не сдвигаемы.
>рамка 3*3 не сдвигаема, 4*4 вполне
Я также не нашел способа раздвинуть рамку 4*4, можете показать решение?
Добавил в статью «Дополнение об эвристиках».
Не могу придумать ничего кроме суммы расстояний от ящиков до ближайших мест назначения.
Срываю покровы — на каком-то сайте находил таблицу всех уровней с указанием самого короткого решения. И почти все уровни уложились в 100 ходов, исключений было 2 или 3, и данный уровень один из этих исключений. Можно конечно эту границу поднимать, но проблема в том, что даже при 100 ходах оценка вариантов уже получается недостижимой.
>Какие эвристики у вас уже реализованы?
Добавил в статью «Дополнение об эвристиках».