Кто-либо реализовал SMA* алгоритм поиска?
Я нахожу описание алгоритма в AIMA (Искусственный интеллект: современный Подход), не корректно вообще. Что делает 'необходимый' средний? Каков предел памяти? Размер очереди или обработанные узлы? Что, если текущий узел не имеет никаких детей вообще?
Я задаюсь вопросом, корректен ли этот алгоритм сам или нет. Поскольку я искал Интернет, и никто еще не реализовал его.
Спасибо.
1 ответ
I believe this PDF is the SMA* section from AIMA, for those that don't have the book.
I first note the pseudocode from Wikipedia has a rather obvious error in the line:
parent.successors.remove(parent);
It should be
parent.successors.remove(badNode);
(How could a parent be its own successor?)
What does 'necessary' mean?
If its parent is not already in the queue, then we have to add it to the queue. Otherwise, we'll end up searching this node again.
What is the memory limit? The queue size or processed nodes?
The queue will take up all available memory. There is no queue for processed nodes. This is precisely why SMA* can re-traverse nodes and potentially get stuck.
What if the current node has no children at all?
If a node has no children, then it's a leaf node. And if it's a leaf node, then it's a terminal node. In that case, if it's not the goal node, we set its f-cost to infinity, and propagate that information to its parent.