|
|
Поиск решений в пространстве состоянийПоиск решений в пространстве состояний сводится к определению последовательности операторов, отображающих начальные состояния в целевые. Если такая последовательность не одна и задан критерий оптимальности, то поиск сводится к нахождению оптимальной последовательности, т.е. последовательности операторов, обеспечивающей экстремум заданного критерия оптимальности. Для поиска решений в пространстве состояний удобно использовать дерево (граф) состояний. На дереве состояний поиск решения сводится к определению пути (оптимального, если задан критерий оптимальности) от корня дерева к целевой вершине. Наглядно поиск можно проиллюстрировать на дереве состояний, когда начальное состояние одно. Поэтому сначала рассмотрим задачи, определяемые тройкой (S 0, F, G), где множество S 0 начальных состояний состоит из одного элемента. В указанной тройке F -множество операторов, G – множество целевых состояний. Для построения дерева состояний следует, используя операторы из множества F, применимые к начальному состоянию (корню дерева), построить вершины первого уровня. Затем используя, операторы из F, применимые к вершинам первого уровня, построить вершины второго уровня и т.д. Применение операторов к какой-либо вершине дерева для построения всех ее дочерних вершин называется раскрытием вершины, поэтому операторы из множества F рассматриваются как правила раскрытия вершин. После порождения дочерних вершин производится проверка, не являются ли они целевыми. Если целевая вершина не обнаружена, то выполняется следующий этап раскрытия путем применения правил раскрытия к каждой вершине, порожденной на предыдущем этапе. Полученное множество вершин вновь анализируется на присутствие целевой вершины. Процесс продолжается до обнаружения целевой вершины. Рассмотрим процедуру построения графа состояний на примере выбора маршрута транспортным роботом. Схема маршрутов представлена на рис. 8.1. А – начальный пункт. Состояние обозначается строкой, в которой перечисляются все пункты, пройденные к текущему моменту. Операторы соответствуют выбору того или иного маршрута. Так как из каждого пункта можно попасть в любые другие 3 пункта, то множество состоит из 12 операторов, причем применимыми к любому данному состоянию являются не более трех операторов. На графе состояний этой задачи (рис. 8.3) начальной вершине (корню дерева) соответствует состояние А. Корень дерева порождает три дочерние вершины, соответствующие состояниям AB, AC и AD. Каждая из вершин, порожденных корнем, порождает по две вершины и каждая из вершин второго и третьего уровней – по одной. На дугах указаны расстояния, которые проходит робот при переходе из одного состояния в другое. На концевых вершинах, соответствующих целевым состояниям, указаны также длины маршрутов из начального состояния в целевое.
Рис. 8.3 Граф состояний задачи о выборе маршрута Поиск решений имеет итеративный характер, причем число итераций и вершин, раскрытых до нахождения целевой вершины, существенно зависит от порядка раскрытия вершин. Порядок раскрытия вершин называют стратегией поиска. Выделяют два основных типа стратегий поиска: «слепой» перебор и упорядоченный перебор вершин – кандидатов на раскрытие. Слепой перебор характеризуется тем, что расположение целевых вершин или их близость не влияют на порядок раскрытия. Существует несколько алгоритмов слепого перебора. Рассмотрим три наиболее типичных: алгоритм полного перебора, алгоритм равных цен, алгоритм перебора в глубину. Алгоритм полного перебора Вершины раскрываются в том порядке, в котором они были порождены. Первой раскрывается начальная вершина. Проверяется среди порожденных вершин наличие целевой. Если есть, поиск заканчивается. Если нет, то раскрывается первая из порожденных вершин и проверяется наличие целевых вершин. Затем раскрывается вторая из порожденных вершин и т.д. Для записи алгоритмов поиска в пространстве состояний введем понятия списков открытых (ОТК) и закрытых (ЗКР) вершин. Список закрытых вершин – это список, где размещаются идентификаторы раскрытых вершин и идентификатор вершины, которую предстоит раскрыть в данный момент. Вершины из списка ЗКР, кроме последней, раскрывать нельзя. Список открытых вершин – это список, где размещаются идентификаторы вершин, которые могут и должны быть раскрыты. Стратегии поиска различаются правилами размещения вершин в списке ОТК и выбора очередной вершины для раскрытия. Алгоритм полного перебора включает следующие шаги. 1. Поместить начальную вершину в список ОТК. 2. Если список ОТК пуст, выдать сообщение о неудаче поиска, иначе перейти к следующему шагу. 3. Взять первую вершину из списка ОТК и перенести ее в список ЗКР, присвоить вершине идентификатор 4. Раскрыть вершину 5. Проверить, не является ли одна из дочерних вершин В этом алгоритме предполагается, что начальная вершина не может быть целевой. Алгоритм позволяет найти оптимальное (минимальное по числу дуг) решение. Например, использование этого алгоритма для решения задачи о выборе маршрута (минимальной длины) сводится к построению графа состояний (см. рис. 8.3). Имея этот граф и сравнивая длины различных маршрутов, ведущих к целевым состояниям, можно выбрать оптимальные маршруты. Как следует из графа состояний, таких маршрутов два – маршруты, ведущие к целевым состояниям ABCDA и ADCBA. Алгоритм равных цен Пусть каждой дуге поставлена в соответствие некоторая функция стоимости Алгоритм равных цен включает следующие шаги. 1. Поместить начальную вершину 2. Если список ОТК пуст, выдать сообщение о неудаче поиска, иначе перейти к шагу 3. 3. Взять из списка ОТК ту вершину, для которой величина 4. Если 5. Раскрыть вершину Алгоритм равных цен является обобщением алгоритма полного перебора и сводится к нему при условии, что стоимости раскрытия всех вершин равны. При применении этого алгоритма к задаче о выборе маршрута раскрывается меньшее число вершин. Граф решения приведен на рис. 8.4, где на дугах указаны стоимости
Рис. 8.4 Граф решения задачи о выборе маршрута при использовании алгоритма равных цен Алгоритм перебора в глубину Определим глубину вершины числом, равным номеру ее уровня. При переборе в глубину всегда раскрывается вершина, имеющая наибольшую глубину. По тем или иным соображениям задается граничная глубина. Вершины, имеющие глубину, равную граничной, не раскрываются. Таким образом, метод перебора в глубину можно определить как метод перебора, при котором всегда раскрывается та из вершин, которая имеет наибольшую глубину, меньшую граничной. Алгоритм перебора в глубину включает следующие шаги. 1. Поместить начальную вершину в список ОТК. 2. Если список ОТК пуст, выдать сообщение о неудаче поиска, иначе перейти к шагу 3. 3. Взять первую вершину из списка ОТК и поместить в список ЗКР. Присвоить этой вершине идентификатор 4. Если глубина вершины 5. Раскрыть вершину 6. Если одна из этих вершин целевая, то выдать решение, в ином случае перейти к шагу 2. Один из возможных графов решения задачи выбора маршрута с помощью алгоритма перебора в глубину приведен на рис. 8.5. При применении этого алгоритма решение зависит от способа упорядочения вершин в списке ОТК. В приведенном решении найден неоптимальный маршрут.
Рис. 8.5 Граф решения задачи о выборе маршрута при использовании алгоритма перебора в глубину Во всех рассмотренных алгоритмах перебора предполагается, что начальная вершина только одна. Если начальных вершин несколько, то эти алгоритмы изменяются только на шаге 1: на шаге 1 в список ОТК помещаются все начальные вершины. Достоинством методов слепого перебора являются, во-первых, простота алгоритмической реализации, во-вторых, обязательность получения решения, если оно существует. Недостатком этих методов является резкое возрастание числа вершин, которые необходимо раскрыть в процессе поиска решения, с увеличением размерности задачи. Это существенно сужает круг практических задач, которые могут быть решены методами слепого перебора.   ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
.
. Требуется найти путь минимальной стоимости. Раскрытие вершин осуществляется в порядке возрастания их стоимости. Обозначим 
– стоимость некоторой вершины 
.
в список ОТК.
имеет наименьшее значение, и поместить ее в список ЗКР. Присвоить этой вершине идентификатор 
вычислить стоимость 
по формуле 
. Поместить эти вершины вместе с соответствующими им 
, а на вершинах кроме обозначения состояния – значение функции 
