SMA * - SMA*

SMA * или же Упрощенная память с ограничением A * это алгоритм кратчайшего пути на основе А * алгоритм. Основное преимущество SMA * заключается в том, что он использует ограниченную память, в то время как алгоритму A * может потребоваться экспоненциальная память. Все остальные характеристики SMA * унаследованы от A *.

Процесс

Как и A *, он расширяет наиболее перспективные ветви в соответствии с эвристикой. Что отличает SMA *, так это то, что он удаляет узлы, расширение которых оказалось менее перспективным, чем ожидалось. Такой подход позволяет алгоритму исследовать ветви и возвращаться для изучения других ветвей.

Расширение и сокращение узлов осуществляется за счет сохранения двух значений: ${\displaystyle f}$ для каждого узла. Узел ${\displaystyle x}$ хранит значение ${\displaystyle f(x)}$ который оценивает стоимость достижения цели путем прохождения пути через этот узел. Чем ниже значение, тем выше приоритет. Как и в A *, это значение инициализируется как ${\displaystyle h(x)+g(x)}$, но затем будет обновлен, чтобы отразить изменения в этой оценке, когда его дочерние элементы будут расширены. Полностью развернутый узел будет иметь ${\displaystyle f}$ по крайней мере так же высоко, как и его последователи. Кроме того, узел хранит ${\displaystyle f}$ ценность лучшего из забытых преемников. Это значение восстанавливается, если обнаруживается, что забытый преемник является наиболее многообещающим преемником.

Начиная с первого узла, он сохраняет ОТКРЫТО, лексикографически упорядоченный по ${\displaystyle f}$ и глубина. При выборе узла для расширения он выбирает лучший в соответствии с этим порядком. Выбирая узел для обрезки, он выбирает худший.

Характеристики

SMA * имеет следующие свойства

• Работает с эвристический, так же как A *
• Это завершено, если разрешенная память достаточно велика для хранения самого мелкого решения.
• Оптимально, если разрешенная память достаточно велика для хранения самого мелкого оптимального решения, в противном случае будет возвращено лучшее решение, которое умещается в разрешенной памяти.
• Он избегает повторяющихся состояний, пока это позволяет ограничение памяти.
• Он будет использовать всю доступную память
• Увеличение объема памяти алгоритма только ускорит расчет.
• Когда доступно достаточно памяти, чтобы вместить все дерево поиска, расчет имеет оптимальную скорость.

Выполнение

Реализация SMA * очень похожа на реализацию A *, с той лишь разницей, что когда не остается места, узлы с наибольшей f-стоимостью удаляются из очереди. Поскольку эти узлы удаляются, SMA * также должен запомнить f-стоимость лучшего забытого дочернего узла с родительским узлом. Когда кажется, что все исследованные пути хуже, чем такой забытый, путь создается заново.^[1]

Псевдокод:

функция SMA-звезда(проблема): дорожка  очередь: набор из узлы, упорядоченный к ж-Стоимость;начинать  очередь.вставлять(проблема.корень-узел);  пока Истинный делать начинать    если очередь.пустой() тогда возвращаться отказ; // нет решения, которое уместилось бы в данной памяти    узел := очередь.начинать(); // узел минимальной стоимости    если проблема.является-Цель(узел) тогда возвращаться успех;        s := следующий-преемник(узел)    если !проблема.является-Цель(s) && глубина(s) == Максимальная глубина тогда        ж(s) := инф;         // не осталось памяти, чтобы пройти мимо s, поэтому весь путь бесполезен    еще        ж(s) := Максимум(ж(узел), грамм(s) + час(s));        // f-значение преемника - максимум        // f-значение родительского и         // эвристика преемника + длина пути к преемнику    endif    если нет более преемники тогда       Обновить ж-Стоимость из узел и те из это предки если нужный        если узел.преемники ⊆ очередь тогда очередь.удалять(узел);     // все дети уже добавлены в очередь более коротким способом    если объем памяти является полный тогда начинать      badNode := самый мелкий узел с наибольший ж-Стоимость;      за родитель в badNode.родители делать начинать        родитель.преемники.удалять(badNode);        если нужный тогда очередь.вставлять(родитель);       конец    endif    очередь.вставлять(s);  в конце концовконец

Рекомендации

1. Рассел, С. (1992). «Эффективные методы поиска с ограничением памяти». В Neumann, Б. (ред.). Материалы 10-й Европейской конференции по искусственному интеллекту. Вена, Австрия: John Wiley & Sons, Нью-Йорк, Нью-Йорк. С. 1–5. CiteSeerX  10.1.1.105.7839.