Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Поиск на основе данных и цели. Графы.



Поиск в пространстве состояния можно вести в двух направлениях: от исходных данных задачи к цели и в обратном направлении – от цели к исходным данным.

При поиске на основе данных, который иногда называют «прямой цепочкой», исследователь начинает процесс решения задачи, анализируя её условие, а затем применяет допустимые ходы или правила изменения состояния. В процессе поиска правила изменения состояния. В процессе поиска правила применяются к известным фактам для получения новых фактов, которые, в свою очередь, используются для генерации новых фактов. Этот процесс продолжается до тех пор, пока мы, если повезёт, не достигнем цели.

Возможен и альтернативный подход. Рассмотрим цель, которую мы хотим достичь. Проанализируем правила или допустимые ходы, ведущие к цели, и определим условия их применения. Эти условия становятся новыми целями, или подцелями, поиска. Поиск продолжается в обратном направлении от достигнутых подцелей до тех пор, пока (если повезет) мы не достигнем исходных данных. Таким образом определяется путь от данных к цели, который на самом деле строится в обратном направлении. Этот подход называется поиском от цели или «обратной цепочкой». Он напоминает простой детский трюк, заключающийся в поиске выхода из лабиринта из конечного искомого состояния к заданному начальному.

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

 

Граф — это множество вершин и дуг между ними. В размеченном графе для каждой вершины задается один или несколько дескрипторов (меток), которые позволяют отличить одну вершину графа от другой. На графе пространства состояний эти дескрипторы идентифицируют состояния в процессе решения задачи. Если дескрипторы двух вершин не различаются, то эти вершины считаются одинаковыми. Дуга между двумя вершинами определяется метками этих вершин.

Дуги графа также могут быть размеченными. Метка дуги используется для задания именованного отношения (как в семантических сетях) либо веса дуги (как в задаче о коммивояжере). Дуги между двумя вершинами тоже можно различать с помощью меток.

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

Путь (path) на графе — это последовательность дуг, соединяющих соседние вершины. Путь представляется списком дуг, систематизированным в порядке их следования.

Корневой граф содержит единственную вершину, от которой существует путь к любой вершине графа. Эта вершина называется корнем (root). При изображении корневого графа корень обычно помещают в верхней части рисунка над всеми остальными вершинами. Граф пространства состояний любой игры обычно является корневым графом, причем в качестве корня выступает начальное состояние игры.

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

Для корневых деревьев или графов отношения между вершинами описываются понятиями родителя, потомка и вершин-братьев (siblings) — вершин дерева, имеющих общую вершину-родителя. Они используются в обычном смысле наследования: при проходе вдоль направленной дуги родитель предшествует потомку. Концы всех направленных дуг, исходящих из одной вершины, называются вершинами-братьями.

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.