Кто-нибудь реализовал алгоритм поиска SMA*?

Я использовал 3 списка - границу (открытый список), список листьев и список "ветвей дерева".

• Граница - это очередь, упомянутая в PDF, это очередь с общим приоритетом, отсортированная от лучшего к худшему.

• Список листьев содержит только листья, отсортированные от худшего к лучшему, он нам понадобится, когда мы будем решать, какой лист забыть. SMA забывает только листья, а не целые ветки.

• Список ветвей дерева содержит полностью развернутые узлы, все дочерние элементы которых находятся в памяти. Он понадобится нам для проверки пересечения штатов.

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

Узлы должны хранить следующую дополнительную информацию:

• Итератор преемников с позицией (позиция нужна для указания в списке преемников). Мы абсолютно не должны сбрасывать наше перечисление преемников на ноль, если мы забудем по ходу дела, потому что возможно, что мы забудем только что добавленный узел. Я использую IEnumerator, int для позиции и bool для "завершенного" флага.

• Список преемников. Нам неизбежно нужно это для распространения f-стоимости вверх. Также я сохраняю простой список состояний-преемников, например [заблокировано, забыто, существует]. Это необходимо для отслеживания забытых и заблокированных узлов. (заблокировано - в графе - каким-то узлом, который расширялся быстрее)

• Две F, упомянутые в PDF, наша текущая F и лучший забытый преемник F.

• Глубина узла

Сортировка узлов как в граничном, так и в листовом списке должна выполняться следующим образом: «если у нас есть «законченный» флаг перечисления, выберите лучший забытый преемник F, иначе выберите текущий F, если равны, выберите самый глубокий». Листовой список сортируется в обратном порядке с использованием точно такого же условия.

Базовая схема алгоритма выглядит следующим образом (аналогично PDF-файлам):

• Мы выбираем лучший узел из границы, если он имеет флаг «завершение» - мы знаем, что будем помнить, сбрасываем итератор, и в этом случае мы должны сбросить лучший забытый преемник F (по сложным причинам).

• Если у нас еще нет этого преемника в списке (может быть, когда мы вспоминаем) - мы генерируем его и устанавливаем его F, как описано в PDF.

• Далее следует самое сложное — мы проверяем, существует ли узел с таким же состоянием в списке границ или ветвей дерева. Если получится - опишу что делать дальше. Если нет, мы просто добавляем дочерний элемент на границу (и удаляем родительский элемент из листового списка).

• Во всех случаях, когда заканчивается перечисление преемников - делаем так называемый бэкап f-стоимости, и если у нас нет забытых узлов (и есть преемники), мы убираем текущий узел с границы и добавляем его в дерево список филиалов.

Как забыть: мы выбираем первый лист из списка листьев (худший лист), удаляем его из границы, удаляем его из списка преемников родителя, обновляем (уменьшаем) лучший забытый преемник F родителя, если это необходимо, и если родитель не находится на границе - мы удаляем его из списка ветвей дерева и добавляем к границе, а также добавляем в список листьев, если он теперь лист (у него больше нет преемников).

Что делать, если мы сгенерировали преемника, который уже находится в списке границ или веток дерева. Во-первых, нам нужно проверить, что лучше — мы сравниваем PathCost + H («исходное» F) двух узлов. Обратите внимание, что мы вообще не можем сравнивать резервные копии F — это не сработает. Если не лучше - просто устанавливаем преемнику состояние заблокировано. Если это так - может случиться так, что худший узел является корнем огромного поддерева (слишком сложно, чтобы объяснять еще раз). Только в этом случае мы полностью вырезаем поддерево, и SMA сразу забывает кучу узлов. После замены худшего узла на лучший, мы удаляем худший узел из его родительского списка преемников, из границы, листового списка или даже списка ветвей дерева (он может быть даже там!), устанавливаем состояние преемника на заблокированное для его родителя и не не забудьте проверить, заблокированы ли сейчас все узлы у родителя худшего узла - нам нужно установить его F на бесконечность, потому что он стал конечным узлом.

Может у меня не самая простая реализация, но она единственная, которая у меня работает. Я использовал 8-головоломки для тестов - решение n-шагов с минимумом (n+1)-памяти (подсчет начального узла) и проверка оптимальности решения с помощью обычной а-звезды. Я потратил около 20-30 часов, пытаясь выяснить все детали - основная проблема была в сложности фейл-тестов - у меня есть логические ошибки "замена на лучший узел" только на 20+ шагах с обширное тестирование тысяч случайных семян. Также следите за очередями с приоритетом - мне приходилось повторно вставлять элемент в очень многих случаях, вызывая любое изменение в F, лучшем забытом F или флаге «завершено» - изменяет порядок сортировки. В итоге я проверял согласованность бинарных куч при каждом удалении из очереди. И основная идея избавления от сложнейшего для понимания бага бесконечного зацикливания состоит в том, чтобы проверить, что вы не уменьшаете F во всех случаях. Таким образом, F будет продолжать расти.

Я собираюсь поделиться рабочим исходным кодом реализации через пару недель.