Любой реализовал алгоритм поиска SMA *?

Question

Я считаю, что описание алгоритма в AIMA (Artificial Intelligence: A Modern Approach) неверно. Что означает «необходимо»? Каков предел памяти? Размер очереди или обработанные узлы? Что делать, если текущий узел не имеет детей вообще?

Мне интересно, правильно ли этот алгоритм или нет. Потому что я искал Интернет, и никто его еще не реализовал.

Спасибо.

Answer 1

Я считаю, что this PDF - это раздел SMA * от AIMA, для тех, у кого нет книги.

Я первый отметить псевдокод из Википедии есть довольно очевидная ошибка в строке: (Как может родитель быть своим собственным преемником)

parent.successors.remove(parent); 

Он должен быть

parent.successors.remove(badNode); 

Что значит «необходимо»?

Если его родитель еще не находится в очереди, мы должны добавить его в очередь. В противном случае мы снова будем искать этот узел.

Какая предел памяти? Размер очереди или обработанные узлы?

Очередь занимает всю доступную память. Нет очереди для обработанных узлов. Именно поэтому SMA * может перебирать узлы и потенциально застревать.

Что делать, если текущий узел не имеет детей вообще?

Если у узла нет детей, то это листовой узел. И если это листовой узел, то это конечный узел. В этом случае, если это не узел цели, мы устанавливаем его f-cost на бесконечность и распространяем эту информацию на своего родителя.

Answer 2

Мне удалось реализовать поиск графа с ним на C#, используя the PDF.

Я использовал 3 списка - frontier (открытый список), список листьев и список «ветка дерева».

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

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

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

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

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

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

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

• Два F-х, указанный в PDF, наш текущем F, и лучше всего забыть преемник Ф.

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

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

Базовый план алгоритм, как это (по аналогии с PDF-файлами):

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

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

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

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

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

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

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

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