Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Представление задачи в виде И-ИЛИ графов





Для некоторых задач представление в виде И-ИЛИ графа является более естественным, чем в виде пространства состояний. Это задачи, которые разбиваются на взаимно независимые задачи.

Рассмотрим традиционный пример о поиске кратчайшего маршрута от пункта a до пункта z (рис. 16).

Рисунок 16. Карта дорог для задачи о поиске пути от пункта a до пункта z

Разумеется, эту задачу проще решить с помощью обычного пространства состояний, причем пространство состояний в точности соответствовало бы карте. Попробуем представить ее с помощью разложимой системы продукций. Нашей исходной задачей, или начальной вершиной, является задача «найти путь от a до z» так как f и g — мосты, то попасть из a в z можно либо через пункт f, либо через пункт g. Следовательно, «найти путь из a в z» вершина типа «ИЛИ». Задачи «найти путь от a до z через f» и «найти путь от a до z через g» разбиваются на две подзадачи: «путь от a до моста» и «путь от моста до z». Следовательно, эти задачи являются вершины типа «И». Дальнейшее разбиение можно построить, вводя дополнительные промежуточные пункты. Изобразим часть И-ИЛИ графа на рис. 17:

Рисунок 17. Верхняя часть «И-ИЛИ» графа для задачи о мостах

Целевыми вершинами И-ИЛИ графа являются задачи, решаемые непосредственно, т.е. задачи о нахождении пути между вершинами карты, соединенные ребром.

После проведения на этом И-ИЛИ графе какого-либо вида поиска (глубина, ширина, эвристический поиск) будет построено следующее дерево решения (рис. 18):

Рисунок 18. Дерево решения задачи о мостах, построенное эвристическим поиском на «И-ИЛИ» графе

Путь от a до z можно восстановить обходом терминальных вершин слева направо: a — b, b — d, d — f, f — i, i — z.

Date: 2015-08-07; view: 523; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию