Целевая вершина

Cтраница 3

Процесс построения поисковых деревьев может закончиться в одном из следующих двух случаев: 1) обнаружена целевая вершина; 2) целевая вершина не обнаружена, но дальнейшее построение графа невозможно, так как для всех раскрываемых вершин множество преемников пусто. [31]

Если среди них не обнаруживается целевая вершина, то затем также обследуются по порядку все вершины глубины Я 2 и так далее, пока не будет обнаружена целевая вершина, то есть не будет получено решение задачи. Так как целевых вершин может быть несколько, то при необходимости поиск продолжается до тех пор, пока яв будут найдены все решения. [32]

Начинаясь в а, поиск вглубину заканчивается бесконечным циклом между d и h. a. b d h - d - h d -. [33]

Как видно из рис. 11.6, Верш - это состояние, из которого необходимо найти путь до цели; Путь - пути ( список вершин) между стартовой вершиной и Верш; Решение - Путь, продолженный до целевой вершины. [34]

Какие вершины И / ИЛИ-графа являются целевыми. Целевые вершины - это тривиальные, или примитивные задачи. В нашем примере такой подзадачей можно было бы считать подзадачу найти путь из а в с, поскольку между городами а и с на карте имеется непосредственная связь. [35]

Формулировка игровой задачи для игры двух лиц в форма И / ИЛИ-дерева. участники игры. - игрок и противник. [36]

Таким образом, все позиции противника - это И-вершины. Целевые вершины - это позиции, выигранные согласно правилам игры, например позиции, в которых король противника получает мат. Позициям проигранным соответствуют задачи, не имеющие решения. Для того, чтобы решить игровую задачу, мы должны построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе. [37]

Находясь в активном состоянии, процесс продолжает углублять свое поддерево. Встретив целевую вершину, он выдает соответствующее решение. Величина бюджета, предоставляемого процессу на данный конкретный запуск, определяется эвристической оценкой конкурирующей альтернативы, ближайшей к данной. [38]

Без использования знаний, которые может дать анализ промежуточных ситуаций, решение задачи производится путем последовательного перебора всех возможных вариантов. Исходная корневая вершина и целевая вершина показаны здесь кружками, остальные вершины обозначены прямоугольниками. [40]

Разумеется, такси тип результата получится только в том случае, когда Дер - будет содержать целевую вершину. Добавим также, что эта целевая вершина обязана быть листом поддерева Дер. [41]

Отметим, что одним из условий, заданных в целевой вершине, являются связывания цели, выражающие ограничения, которые должны быть удовлетворены в кортежах результата. Рассмотрим все накопленные к концу вычислений в целевой вершине кортежи. Многие из них не будут удовлетворять условиям связывания и могут быть исключены из этой вершины. Идея метода статической фильтрации состоит в том, чтобы исключить из процесса вычисления ненужные кортежи как можно раньше на предыдущих стадиях их продвижения к целевой вершине. [42]

Но в случае, когда в процессе расширения поддерева Дер встретится целевая вершина, процедура расширить должна сформировать соответствующий решающий путь. [43]

Поиск, проводимый в пределах очерченной штриховым контуром левой части дерева, безрезультатен: здесь не находится целевая вершина. В процессе поиска встречаются повторно одни и те же ситуации, перебор которых также бесполезен. [44]

Другой из применяемых процедур поиска является поиск в глубину. При этом после достижения первой же из вершин глубины 1 осуществляется переход к следующей за ней вершине глубины 2, и так до последней наиболее глубокой из вершин, к которой ведет данный путь. Если это не целевая вершина, то таким же образом обследуются следующая из вершин глу-бины 1 и другие связанные с нею вершины. Так как некоторые из них являются точками - ветвления, то проходят сначала в глубину по одной из ветвей, затем от точки ветвления также проходят в глубину по каждой из других ветвей. [45]

Страницы: 1 2 3 4