PiJohn & PrintTinker
PiJohn
Я тут покопался с группой перестановок для пятнашки, и думаю, можно вывести алгоритм, который будет находить минимальное решение быстрее, чем обычный A*. Как ты думаешь, стоит ли превратить это в быстрый решатель, который можно интегрировать в твой рабочий процесс?
PrintTinker
Интересная мысль, но обычно быстрый решатель в итоге скатывается к перебору, который оказывается медленнее, чем хорошо настроенный A* с базами паттернов. Если уж хочешь что-то добавлять в скрипт, подумай об IDA* реализации с предварительно рассчитанной эвристикой Манхэттена и конфликтов на линиях, да ещё и добавь небольшой кэш для уже виденных состояний. Помни, компактное представление состояний — массив 4x4, упакованный в биты, работает быстрее, чем список кортежей. И вынеси решатель в командную строку, чтобы можно было передавать его в другие процессы; не надо городить полноценный графический интерфейс. Если переживаешь из-за оптимальности, помни, что доказывание оптимальности в реальном времени — дорогое удовольствие. Просто возвращай лучшее найденное решение в пределах заданного времени и пусть пользователь сам решает, достаточно ли оно хорошее.
PiJohn
Отличный план, я согласен, кэш сильно сократит время поиска. Набросаю минимальный прототип: массив из 4 байта для доски, быстрое хеширование посещенных состояний и цикл IDA*, который остановится, когда стоимость превысит заданный предел. Еще добавлю быструю проверку на сумму Манхэттена и конфликтов по линиям, чтобы не тратить время на заведомо тупиковые пути. Выдам это в виде маленькой командной строки, которая будет читать строку из 16 символов со стандартного ввода и выводить ходы, чтобы ты мог подключить её к любой нужной тебе цепочке команд. Если хочешь, чтобы решатель был более "научным", можно добавить флаг для запуска полного A* с базой шаблонов – просто для проверки оптимальности. Как тебе?
PrintTinker
Звучит неплохо, но небольшое уточнение: в массиве из 4 байта не поместится 16 тайлов, если не упаковывать по 4 бита на тайл – это возможно, но увеличит накладные расходы. Лучше и быстрее использовать массив из 16 байт или бит-упаковку в 64-битном целом числе для хеширования. И ещё, убедись, что твоя хеш-таблица использует открытую адресацию – это повысит локальность кэша. Проверка на Manhattan + линейный конфликт – отличная идея, она отсекает много лишних ветвей. И хук для CLI – идеально для скриптов. Если будешь добавлять опциональный флаг A* с pattern-DB, помни о том, чтобы хранить базы данных на диске и подгружать их лениво – полная подгрузка базы данных при каждом запуске сильно снизит производительность. В целом, хороший план.
PiJohn
Спасибо за замечания. Ты прав насчёт упаковки данных и структуры хеш-таблицы. Перейду на 64-битное упакованное состояние для хеша, использую линейную адресацию в таблице, и сделаю загрузчик pattern-DB ленивым – чтобы первый запуск оплатил стоимость, а последующие использовали уже выделенную память. Добавлю ещё флаг для детализации, чтобы ты мог наблюдать за статистикой обрезки, если захочешь подкрутить эвристики. Это должно сделать конвейер быстрым и код – чистым.
PrintTinker
Круто. 64-битная упаковка делает состояние компактным, линейная проверка – обеспечивает попадания в кэш, ленивая загрузка базы данных избавляет от задержки при запуске. Флаг подробности – отличный способ убедиться, что всё в порядке: ты увидишь процент попаданий в соответствии с твоим эвристическим методом и поймёшь, стоит ли база данных с паттернами дополнительной памяти. Пиши код модульным, чтобы потом можно было подставить другую эвристику, не трогая интерфейс командной строки. Если кто-то будет жаловаться на “слишком много флагов”, просто отправь их к README; хорошо документированный инструмент – лучший пропагандист open source.
PiJohn
Отлично, договорились. Передам тебе чистый, модульный код, как только доделаю тесты. Дай знать, если хочешь, чтобы я быстро рассказал про архитектуру перед тем, как выложу.
PrintTinker
Конечно, короткая инструкция будет отличная идея.
PiJohn
Конечно, вот краткий обзор: CLI разбирает строку или файл из 16 символов, формирует 64-битное упакованное состояние и передает его в модуль решателя. В модуле решателя находится основной цикл IDA*, вспомогательный алгоритм для линейных конфликтов и манхэттенской метрики, а также хеш-таблица с открытой адресацией для обрезки. Если включить флаг pattern-DB, то загрузчик DB читает файл в память с отображением в файл, поэтому при первом поиске строится кэш, и последующие поиски используют его мгновенно. Все это соединено тонким драйвером, который просто перенаправляет параметры; ты можешь заменить эвристическую функцию или заменить хеш-таблицу, не трогая код командной строки. В README объяснены все флаги и приведен пример пайплайна.