Поиск в пространстве состояний - История изменений

Patarakin в 18:19, 19 октября 2022

2022-10-19T18:19:08Z

@@ Строка 1: / Строка 1: @@
-'''По́иск в простра́нстве состоя́ний''' ({{lang-en|state space search}}) — группа математических методов, предназначенных для решения задач [[ИИ|искусственного интеллекта]].
+'''По́иск в простра́нстве состоя́ний'''  — группа математических методов, предназначенных для решения задач [[ИИ|искусственного интеллекта]].
 Методы поиска в пространстве состояний осуществляют последовательный просмотр ''конфигураций'' или ''состояний'' задачи с целью обнаружения ''целевого состояния'', имеющего заданные характеристики или удовлетворяющего некоторому критерию.
@@ Строка 19: / Строка 19: @@
 * '''Функция стоимости пути''' — функция, назначающая каждой последовательности переходов между состояниями определённую стоимость. В простейшем случае стоимость цепочки переходов принимается равной количеству переходов в цепочке.
-Альтернативное определение проблемы поиска в пространстве состояний<ref name="ArtInt_48" /> включает
+Альтернативное определение проблемы поиска в пространстве состояний< включает
 * '''множество состояний''';
 * выделенное подмножество состояний, называемых '''начальными состояниями''';
@@ Строка 53: / Строка 53: @@
 '''Информированные методы поиска''' (''эвристические методы'') пользуются дополнительной информацией о конкретной задаче. Дополнительная информация ('''эвристика''') позволяет сократить перебор путём исключения заведомо бесперспективных вариантов. Такой подход ускоряет работу алгоритма по сравнению с [[Полный перебор|полным перебором]]. Недостатком эвристических алгоритмов может быть отсутствие гарантии того, что выбрано правильное или наилучшее из всех возможных решение.
 [[Категория:Алгоритмы поиска]]

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

2022-10-19T17:55:01Z

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

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

ru_wikipedia>InternetArchiveBot: Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8

2022-07-26T05:09:09Z

Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8

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

'''По́иск в простра́нстве состоя́ний''' ({{lang-en|state space search}}) — группа математических методов, предназначенных для решения задач [[ИИ|искусственного интеллекта]].

Методы поиска в пространстве состояний осуществляют последовательный просмотр ''конфигураций'' или ''состояний'' задачи с целью обнаружения ''целевого состояния'', имеющего заданные характеристики или удовлетворяющего некоторому критерию.

== Допущения ==
Описание состояния содержит всю информацию, необходимую для предсказания результата того или иного действия и определения, является ли текущее состояние целевым. Поиск в пространстве состояний основывается на нескольких предположениях<ref name="ArtInt_48" />:
* агент (под термином «агент» понимается некоторый механизм, устройство, деятель, который может переводить рассматриваемую систему с многими состояниями из одного состояния в другое состояние) имеет полную информацию о пространстве состояний и может определить, в каком состоянии находится система;
* агенту доступен набор действий, переводящих систему в другое состояние, эффект от которых детерминирован;
* некоторым состояниям присвоен статус «целевых состояний»; задача агента — достичь одного из целевых состояний; при достижении целевого состояния агент может определить, что достигнутое состояние является целевым;
* решение задачи поиска — это последовательность действий (изменений состояния системы), которые позволят агенту перейти из текущего или начального состояния в (одно из) целевых состояний.

== Формальное определение задачи ==

=== Компоненты задачи ===
Во многих задачах присутствует дискретное множество состояний, в которых может находиться определённый объект или система, с правилами и условиями перехода из одного состояния в другое (например, в играх). Подобные задачи могут быть формально определены с помощью четырёх компонентов:
* '''Начальное состояние''' — состояние, в котором система находится в начальный момент;
* '''Функция определения преемника''' — описание возможных переходов из одного состояния в другое;
* '''Проверка цели''' — некоторый алгоритм, позволяющий определить, является ли данное состояние целевым;
* '''Функция стоимости пути''' — функция, назначающая каждой последовательности переходов между состояниями определённую стоимость. В простейшем случае стоимость цепочки переходов принимается равной количеству переходов в цепочке.

Альтернативное определение проблемы поиска в пространстве состояний<ref name="ArtInt_48" /> включает
* '''множество состояний''';
* выделенное подмножество состояний, называемых '''начальными состояниями''';
* для каждого состояния — '''набор действий, доступных агенту''' в этом состоянии;
* '''функцию действия''' (action function), которая для заданного состояния и действия, доступного в этом состоянии, возвращает новое состояние;
* множество '''целевых состояний''', часто определяемое логической функцией <tt>goal(s)</tt>, которая принимает истинное значение, когда <tt>s</tt> — целевое состояние,
* критерий, определяющий '''качество приемлемого решения'''. Сюда могут входить ограничения на количество действий в решении, общую стоимость решения, требование оптимальности решения по числу или общей стоимости действий.

=== Граф пространства состояний ===
Большинство алгоритмических формулировок поиска на графах использует понятие '''явного графа''' ({{lang-en|explicit graph}}). Граф <math>G=\{V,E\}</math> может быть представлен в виде ''матрицы смежности'' или ''списка смежности''.

В алгоритмах поиска в пространстве состояний применяется понятие '''неявного графа''' ({{lang-en|[[:en:Implicit graph|implicit graph]]}}). Отличие неявного графа от явно заданного графа состоит в том, что рёбра графа не хранятся в памяти явно, а порождаются «на лету» ({{lang-en|on-the-fly}}) в соответствии с правилами перехода между состояниями. Определение графа пространства состояний включает в себя ''начальную вершину'', ''множество целевых вершин'' и ''процедуру развёртывания вершины''<ref name="hsta" />.

=== Решение задачи ===
'''Решением задачи''' называется путь от начального состояния до целевого состояния.

'''Оптимальным решением''' называется решение, имеющее наименьшую стоимость среди всех прочих решений.

== Оценка алгоритма поиска ==
Качество алгоритма оценивается с помощью четырёх основных показателей:
* '''Полнота''' — свойство алгоритма всегда находить решение, если оно существует;
* '''Оптимальность''' — свойство алгоритма всегда находить решение с наименьшей стоимостью;
* '''Временная сложность''' — оценка времени работы алгоритма;
* '''Пространственная сложность''' — оценка объёма памяти, необходимого алгоритму.

== Методы поиска в пространстве состояний ==
Методы поиска в пространстве состояний делятся на [[Информированный метод поиска|информированные]] и [[Неинформированный метод поиска|неинформированные]].

'''Неинформированные методы''' (''методы слепого поиска'', ''методы грубой силы'') не используют никакой информации о конкретной задаче, кроме информации о том, как отличить целевое состояние от любого другого.

Алгоритмы этой группы последовательно порождают все возможные состояния, достижимые из исходного состояния до тех пор, пока не будет найдено целевое состояние (решение). Различия между методами неинформированного поиска сводятся к последовательности просмотра состояний.

'''Информированные методы поиска''' (''эвристические методы'') пользуются дополнительной информацией о конкретной задаче. Дополнительная информация ('''эвристика''') позволяет сократить перебор путём исключения заведомо бесперспективных вариантов. Такой подход ускоряет работу алгоритма по сравнению с [[Полный перебор|полным перебором]]. Недостатком эвристических алгоритмов может быть отсутствие гарантии того, что выбрано правильное или наилучшее из всех возможных решение.

== См. также ==
* [[Информированный метод поиска]]
* [[Неинформированный метод поиска]]

== Примечания ==
{{примечания|1|refs=

<ref name="ArtInt_48">{{cite web
|url=http://artint.info/html/ArtInt_48.html
|title=3.2 State Spaces
|author=David Poole and Alan Mackworth
|work=Artificial Intelligence — foundations of computational agents
|access-date=2015-12-05
|archive-date=2015-11-25
|archive-url=https://web.archive.org/web/20151125184904/http://artint.info/html/ArtInt_48.html
|deadlink=no
}}</ref>

<ref name="hsta">{{книга
| автор = Edelkamp Stefan, Schrödl Stefan
| заглавие = Heuristic search: theory and applications
| издательство = [[Morgan Kaufmann Publishers]]
| год = 2012
| страниц = 712
| isbn = 978-0-12-372512-7
}}</ref>

}}

== Литература ==
* {{книга
| автор = Рассел Стюарт, Норвиг Питер
| заглавие = Искусственный интеллект: современный подход
| оригинал = Artificial Intelligence: A Modern Approach
| ссылка = http://aima.cs.berkeley.edu/
| место = М
| издательство = Вильямс
| издание = 2-е изд
| год = 2006
| страниц = 1408
| isbn = 5-8459-0887-6
}}

== Ссылки ==
* [http://www.raai.org/library/tolk/aivoc.html Толковый словарь по искусственному интеллекту]

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