Глава 10. ГРАФОВЫЕ ПРЕДСТАВЛЕНИЯ В РЕШЕНИИ ЗАДАЧ

10.0. Основные понятия и определения

На языке пространства состояний задачу можно представить в виде направленного графа, а решение ее — как путь между выделенными узлами графа; при этом естественно задать вопрос: „Как найти путь на графе?". В этой главе излагается ряд соответствующих алгоритмов. В основном они заимствованы из работы Нильсона (1971), который всесторонне исследовал теоретико-графовые методы в решении задач. К некоторым проблемам, не укладывающимся в рамки рассматриваемого здесь ограниченного понятия решения задач, можно также применить теоретико-графовые методы. Интересующемуся читателю рекомендуем учебник Харари, Нормана и Картрайта (1965).

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

Решение минимально, если не существует другого решения с меньшей стоимостью. Длиной решения называется число узлов в нем.

Эти идеи можно проиллюстрировать графически. На рис. 10.1 показана гипотетическая карта дорог западного побережья США. Ясно, что из Сиэтла в Сан-Диего ведет несколько путей, каждому из которых соответствует стоимость, выраженная в милях. Это конечная задача. На рис. 10.2 представлена часть бесконечного графа, дающего правильно построенные выражения элементарной алгебры, которые можно вывести из х с помощью равенств

Вывод из х можно осуществить за три или пять шагов.

Хотя эти задачи очень просты, на них можно продемонстрировать ряд особенностей поиска на графе. Во-первых, почему они просты? Возможно, потому, что человек может видеть сразу весь граф. Рассмотрим, каким образом граф можно представить в ЭВМ, или, что эквивалентно, в устройстве с совершенной памятью. Все, что такое устройство знало бы о графе, — это информация о фактически пройденных дугах. Это то, с чем должен работать вычислительный алгоритм. Нам понадобятся следующие определения:

Заметим, что не требуется, чтобы узел принадлежал

Из этих определений сразу следует, что

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

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

В заключение отметим, что если узлы на кратчайшем пути, то

(кликните для просмотра скана)