Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Поиск в пространстве состоянийСодержание книги
Поиск на нашем сайте
Фундаментальная идея, которая появилась в результате этих первых опытов, получила наименование поиск в пространстве состояний. По существу, идея очень проста. Множество проблем можно сформулировать в терминах трех важнейших ингредиентов: исходное состояние проблемы, например исходное состояние головоломки; тест завершения — проверка, достигнуто ли требуемое конечное состояние или найдено решение проблемы (примером может послужить правило определения, собрана ли головоломка); множество операций, которые можно использовать для изменения текущего состояния проблемы, например шаги или перемещения фигур при сборке головоломки. Один из способов представления такого концептуального пространства состояний — граф, в котором состояниям соответствуют узлы, а операциям — дуги. Рассмотрим в качестве примера задачу построения слова из некоторого множества букв, как в игре Scrabble. Задавшись набором операций установки букв, можно сформировать пространство состояний. Предположим, что множество доступных букв включает Т, С и А. На каждом уровне графа мы будем добавлять по одной определенной букве. Каждая ветвь, исходящая из узла, соответствует установке буквы в определенную позицию в последовательности, а эта последовательность должна образовать осмысленное слово (рис. 2.1). Если это произошло, то головоломка считается собранной (например, если образовалась комбинация "act" или "cat"). (Сейчас мы не будем стремиться собрать какое-нибудь сложное слово вроде "scrabble", которое может принести играющему больше очков.)
Рис. 2.1. Дерево пространства состояний головоломки Scrabble с буквами Т, С и А Это пространство состояний обладает двумя интересными свойствами, которые присущи далеко не всем пространствам состояний: оно конечно, поскольку существует только п! способов расставить я букв; оно не содержит повторяющихся узлов, что может привести к образованию петель на графе. Метод формирования анаграмм последовательным перечислением является примером применения алгоритма, получившего наименование generate-and-test (порождение и проверка). (1) Генерировать новое состояние, модифицируя существующее; например, изменить последовательность букв, добавив новую в существующую последовательность. (2) Проверить, не является ли образовавшееся состояние конечным (решением); например, проверить, не является ли образовавшаяся последовательность осмысленным словом. Если это так, то завершить, иначе перейти к шагу (1). Множество решений, которые удовлетворяют условию на шаге (2), иногда называют пространством решений. В некоторых головоломках, например в уже упомянутой "8 ферзей", решений много, а в других существует всего несколько или только одно. Действительно, существует довольно много способов разместить восемь ферзей на шахматной доске так, чтобы ни один из них не оказался под боем, а вот для головоломки "8-Puzzle" существует единственное решение (см. упр. 7). Алгоритм имеет два основных варианта: поиск в глубину (depth-first search) и поиск в ширину (breadth-first search). Отличаются варианты порядком формирования состояний на шаге (1). Действительные алгоритмы приведены в упр. 5, а здесь мы дадим только их неформальное описание. Для любого данного узла N алгоритм поиска в глубину строит потомок этого узла, т.е. формирует состояние, которое образуется в результате применения операторов к узлу N, а потом переходит к формированию узла, ближайшего к N, на том же уровне графа ("соседу" N), т.е. формирует состояние, которое образуется в результате применения оператора к узлу-родителю N. Алгоритм поиска в ширину действует наоборот — сначала формируются все "соседи" узла N, а потом уже строятся его потомки. Таким образом, в алгоритме поиска в ширину просматриваются последовательно состояния, представленные узлами одного и того же уровня на графе (рис. 2.2), а в алгоритме поиска в глубину просматриваются состояния на одном пути, а затем происходит возврат назад на один уровень и формируется следующий путь (рис. 2.3).
Рис. 2.2. Граф пространства состояний при использовании алгоритма поиска в ширину
Рис. 2.3. Граф пространства состояний при использовании алгоритма поиска в глубину На обоих рисунках числа на дугах графа указывают номер шага, на котором формируется тот узел (состояние), для которого эта дуга является входящей. Конечно, этот номер еще зависит и от того, в каком порядке используются операторы из имеющегося множества. В представленном примере сначала применяется оператор, добавляющий очередную букву в конец последовательности, затем оператор, добавляющий букву на предпоследнюю позицию, и т.д., а последним применяется оператор, добавляющий букву на первое место. Но ведь можно использовать и обратный порядок применения операторов. Оба алгоритма завершат работу (найдут конечное состояние) после формирования узла "act", а не "cat". Но алгоритму поиска в ширину придется для этого "посетить" пять узлов (сформировать и проанализировать пять состояний), а алгоритму поиска в глубину — четыре.
|
||||
Последнее изменение этой страницы: 2016-04-07; просмотров: 362; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.3.235 (0.007 с.) |