СМА*
 | Эта статья нуждается в дополнительных цитатах для проверки . ( март 2015 г. ) |
 | Эта статья может быть слишком технической для понимания большинства читателей . ( Ноябрь 2009 г. ) |
SMA* или упрощенная память с ограниченной памятью A* — это алгоритм кратчайшего пути, основанный на алгоритме A* . Основное преимущество SMA* заключается в том, что он использует ограниченную память, тогда как алгоритму A* может потребоваться экспоненциальная память. Все остальные характеристики SMA* унаследованы от A*.
Процесс
[ редактировать ]Характеристики
[ редактировать ]SMA* имеет следующие свойства
- Он работает с эвристикой , так же, как A*
- Он завершен, если разрешенная память достаточно велика для хранения самого поверхностного решения.
- Оптимально, если разрешенная память достаточно велика для хранения наименьшего оптимального решения, в противном случае будет возвращено лучшее решение, которое помещается в разрешенную память.
- Он избегает повторяющихся состояний, пока это позволяет ограничение памяти.
- Он будет использовать всю доступную память
- Увеличение объема памяти алгоритма только ускорит расчет.
- Когда доступно достаточно памяти для размещения всего дерева поиска, скорость вычислений оптимальна.
Выполнение
[ редактировать ]Реализация простой памяти A* очень похожа на реализацию A*; единственное отличие состоит в том, что узлы с самой высокой f-стоимостью удаляются из очереди, когда не остается места. Поскольку эти узлы удаляются, простой A*, ограниченный в памяти, должен запомнить f-стоимость наиболее забытого дочернего узла родительского узла. Когда кажется, что все исследованные пути хуже такого забытого пути, путь возрождается. [1]
Псевдокод:
функция простая памятью ограниченная A * -звезда ( задача ) : очереди очередь : набор узлов ; , упорядоченных по f - стоимости , начать очередь . вставить ( проблема . корень - узел ) ; в то время как True действительно начинается, если очередь . пустой () , затем вернуть ошибку ; //нет решения, которое помещается в данный узел памяти := очередь . начинать () ; // min-f-cost-node, если проблема . is - цель ( узел ) , затем вернуть успех ; s := next — преемник ( узел ), если ! проблема . is - цель ( s ) && глубина ( s ) == max_глубина , тогда f ( s ) := inf ; // не осталось памяти, чтобы пройти мимо s, поэтому весь путь бесполезен else f ( s ) := max ( f ( node ) , g ( s ) + h ( s )) ; // f-значение преемника является максимальным // f-значением родительского элемента и эвристикой преемника + длина пути до конца преемника , если если нет больше преемников то обновить f - стоимость узла узлов и его // , предки , если необходимо , если node . преемники ⊆ очередь, затем очередь . удалить ( узел ) ; // все дочерние элементы уже добавлены в очередь более коротким путем, если память заполнена , то начинаем плохой узел := самый мелкий узел с наивысшей f - стоимостью ; для родителя в плохом узле . родители начинают быть родителем . преемники . удалить ( плохой узел ) ; если нужно , то в очередь . вставить ( родительский ) ; конец за концом, если очередь . вставлять ( ы ) ; конец , пока конец Ссылки
[ редактировать ]- ^ Рассел, С. (1992). «Эффективные методы поиска с ограничением памяти». В Неймане, Б. (ред.). Материалы 10-й Европейской конференции по искусственному интеллекту . Вена, Австрия: John Wiley & Sons, Нью-Йорк, Нью-Йорк. стр. 1–5. CiteSeerX 10.1.1.105.7839 .