SMA* - История изменений

Patarakin в 08:28, 17 апреля 2023

2023-04-17T08:28:51Z

← Предыдущая версия		Версия от 11:28, 17 апреля 2023
Строка 1:		Строка 1:
	'''SMA''' или '''Упрощённый алгоритм с ограничением памяти A''' — это [[Задача о кратчайшем пути\|алгоритм кратчайшего пути]], основанный на '''[[A\|алгоритме A]]'''. Основное преимущество '''SMA''' заключается в том, что он использует ограниченную память, в то время как '''алгоритму A''' может потребоваться экспоненциальная память. Все остальные характеристики '''SMA''' унаследованы от '''A'''.		'''SMA''' или '''Упрощённый алгоритм с ограничением памяти A''' — это [[Задача о кратчайшем пути\|алгоритм кратчайшего пути]], основанный на '''[[A\|алгоритме A]]'''. Основное преимущество '''SMA''' заключается в том, что он использует ограниченную память, в то время как '''алгоритму A''' может потребоваться экспоненциальная память. Все остальные характеристики '''SMA''' унаследованы от '''A'''.

	~~__TOC__~~
	== Свойства ==		== Свойства ==
	'''SMA*''' имеет следующие свойства:		'''SMA*''' имеет следующие свойства:
Строка 18:		Строка 17:

	=== Псевдокод ===		=== Псевдокод ===

	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
	function SMA-star(problem): path		function SMA-star(problem): path
Строка 56:		Строка 56:
	</syntaxhighlight>		</syntaxhighlight>

	~~== Примечания ==~~
	~~{{примечания}}~~

	~~{{Алгоритмы поиска на графах}}~~

	~~[[Категория:Алгоритмы на графах]]~~
	~~[[Категория:Маршрутизация]]~~
	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]
	~~[[Категория:Игровой искусственный интеллект]]~~

Patarakin: 1 версия импортирована

2022-10-19T17:55:04Z

1 версия импортирована

← Предыдущая версия		Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>Alex NB OT: Проект Check Wikipedia: исправление ошибки 57 по запросу

2021-12-03T20:24:39Z

Проект Check Wikipedia: исправление ошибки 57 по запросу

Новая страница

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

__TOC__
== Свойства ==
'''SMA*''' имеет следующие свойства:

* '''SMA*''' работает с [[Эвристика|эвристикой]], как и '''A*'''.
* '''SMA*''' завершён, если разрешённая память достаточно велика для хранения самого поверхностного решения.
* Оптимально, если разрешённая память достаточно велика для хранения самого поверхностного оптимального решения, в противном случае будет возвращено лучшее решение, которое умещается в разрешённой памяти.
* '''SMA*''' избегает повторяющихся состояний, пока это позволяет ограниченная память.
* Будет использована вся доступная память.
* Увеличение объёма памяти алгоритма только ускорит расчёт.
* Когда доступно достаточно памяти, чтобы вместить всё дерево поиска, расчёт имеет оптимальную скорость.

== Реализация ==
Реализация '''SMA*''' очень похожа на реализацию '''A*''' с той лишь разницей, что когда не остаётся места, узлы с наибольшей '''''f-стоимостью''''' удаляются из очереди. Поскольку эти узлы удаляются, '''SMA*''' также должен помнить '''''f-стоимость''''' лучшего забытого потомственного узла с узлом предка. Когда кажется, что все исследованные пути хуже, чем этот забытый, путь создаётся заново<ref>{{cite journal|author=[[Рассел, Стюарт|Стюарт Рассел]]|year=1992
|citeseerx=10.1.1.105.7839|title='''Эффективные методы поиска с ограничением памяти'''|book-title=Материалы 10-й Европейской конференции по искусственному интеллекту|location=[[Вена]] ([[Австрия]])|editor=Б. Нойман|publisher=[[John Wiley & Sons|издательство ''Джон Уайли и сыновья'']], [[Нью-Йорк]] ([[Нью-Йорк (штат)|штат Нью-Йорк]])|pages=1–5}}</ref>.

=== Псевдокод ===
<syntaxhighlight lang="pascal">
function SMA-star(problem): path
queue: set of nodes, ordered by f-cost;
begin
queue.insert(problem.root-node);

while True do begin
if queue.empty() then return failure; // нет решения, которое уместилось бы в данной памяти
node := queue.begin(); // узел минимальной f-стоимости
if problem.is-goal(node) then return success;

s := next-successor(node)
if !problem.is-goal(s) && depth(s) == max_depth then
f(s) := inf;
// не осталось памяти, чтобы пройти мимо s, поэтому весь путь бесполезен
else
f(s) := max(f(node), g(s) + h(s));
// f-значение потомка — максимум f-значения предка и
// эвристика потомка + длина пути к потомку
endif
if no more successors then
update f-cost of node and those of its ancestors if needed

if node.successors ⊆ queue then queue.remove(node);
// все потомки уже добавлены в очередь более коротким способом
if memory is full then begin
badNode := shallowest node with highest f-cost;
for parent in badNode.parents do begin
parent.successors.remove(badNode);
if needed then queue.insert(parent);
endfor
endif

queue.insert(s);
endwhile
end
</syntaxhighlight>

== Примечания ==
{{примечания}}

{{Алгоритмы поиска на графах}}

[[Категория:Алгоритмы на графах]]
[[Категория:Маршрутизация]]
[[Категория:Алгоритмы поиска]]
[[Категория:Игровой искусственный интеллект]]