Целевая вершина
Cтраница 4
В результате процесс поиска не успевает осознать, что А - это тоже целевая вершина и что порождено решающее дерево. Вместо этого происходит переключение активности на конкурирующую альтернативу с. Теперь процесс поиска обнаруживает, что найдено решающее дерево ( включающее в себя целевые вершины h и g), на чем поиск заканчивается. [46]
Алгоритм поиска пути называют допустимым, если он всегда отыскивает оптимальное решение ( т.е. путь минимальной стоимости) при условии, что такой путь существует. Наша реализация алгоритма поиска, пользуясь механизмом возвратов, выдает все существующие решения, поэтому, в нашем случае, условием допустимости следует считать оптимальность первого из найденных решений. Обозначим через h ( n) стоимость оптимального пути из произвольной вершины п в целевую вершину. [47]
 |
Программа поиска в глубину без зацикливания. [48] |
Верш Путь ], который претендует на то, что его можно продолжить вплоть до целевой вершины. [49]
При поиске в глубину сначала раскрывается та вершина, которая была построена самой последней. Глубина вершины в графе определяется следующим образом: 1) глубина вершины-корня равна нулю; 2) глубина промежуточной вершины равна единице плюс глубина наиболее близкой вершины-предка. При практической реализации поиск в глубину в некотором направлении завершается в следующих случаях: 1) при достижении целевой вершины; 2) при достижении терминальной вершины; 3) при построении в ходе поиска вершины, глубина которой превышает некоторую граничную глубину. [50]
Построение пространства осуществляется с помощью следующей операции. К некоторой вершине из х0ЕХ0 применяют все возможные операторы, порождающие все ее вершины-потомки. Порождение всех вершин-потомков для некоторой вершины х: называют операцией раскрытия вершин. Если получена целевая вершина, то она не раскрывается. [51]
Отметим, что одним из условий, заданных в целевой вершине, являются связывания цели, выражающие ограничения, которые должны быть удовлетворены в кортежах результата. Рассмотрим все накопленные к концу вычислений в целевой вершине кортежи. Многие из них не будут удовлетворять условиям связывания и могут быть исключены из этой вершины. Идея метода статической фильтрации состоит в том, чтобы исключить из процесса вычисления ненужные кортежи как можно раньше на предыдущих стадиях их продвижения к целевой вершине. [52]
Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина хо е Хо, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти. [53]
Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина изх0 & Х0, к ней применяются все возможные операторы, порождающие все дочерние вершины. Порождение всех дочерних вершин для некоторой вершины дс-называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти. В практических приложениях часто требуется обеспечить полноту поиска, т.е. организовать поиск так, чтобы все целевые вершины были найдены, если они существуют. Надежным способом обеспечения полноты является полный перебор всех вершин. Для задания процесса перебора необходимо определить порядок, в котором будут перебираться вершины графа. Обычно выделяют два основных способа поиска: поиск в глубину и поиск в ширину. При поиске в глубину сначала раскрывается та вершина, которая была построена самой последней. [54]
Руководствуясь правилами оценки ситуаций, которые могут быть заранее запрограммированы, машина, сравнив в нашем примере ситуации Л и В, установит, что ситуация А хуже, чем В. При этом она уже не будет заниматься дальше обследованием путей, идущих от вершины А. Исключается перебор всех вершин дерева поиска, находящихся в части дерева, обведенной у нас на рисунке штриховой линией. Дальнейший поиск ведется только от вершины В. На основании оценки ситуаций признается лучшей ситуация С, и дальше рассматриваются лишь пути, идущие от соответствующей вершины дерева. Перебор их тоже может быть исключен, если запрограммировать такое правило: если на стержень III посажен большой диск, то при следующем ходе нужно посадить на этот стержень малый диск. Таким образом, достигается сразу конечная целевая вершина, и на этом решение задачи заканчивается. [55]
Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина изх0 & Х0, к ней применяются все возможные операторы, порождающие все дочерние вершины. Порождение всех дочерних вершин для некоторой вершины дс-называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти. В практических приложениях часто требуется обеспечить полноту поиска, т.е. организовать поиск так, чтобы все целевые вершины были найдены, если они существуют. Надежным способом обеспечения полноты является полный перебор всех вершин. Для задания процесса перебора необходимо определить порядок, в котором будут перебираться вершины графа. Обычно выделяют два основных способа поиска: поиск в глубину и поиск в ширину. При поиске в глубину сначала раскрывается та вершина, которая была построена самой последней. [56]
Страницы: 1 2 3 4