Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 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.
|