5.1.2. КЛАССИЧЕСКАЯ ЗАДАЧА О КОММИВОЯЖЕРЕ

Пусть - некоторый граф. Множество его дуг отображает транспортные пути между множеством городов, представляемых вершинами из множества Каждой дуге приписывается положительная стоимость

Задача состоит в построении такого маршрута, который проходит один, и только один раз через каждый город и имеет минимальную стоимость (если подобный маршрут существует)

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

Рис. 5.1 (см. скан) Неориентированный граф минимальная стоимость дуги, входящей в каждую вершину граф поиска

Пространство состояний, которое не следует смешивать с графом образуется следующим способом если в Я существует дуга причем вершина не принадлежит подпоследовательности то имеется дуга, направленная из состояния в состояние

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

Рассмотрим пример, изображенный на рис 5.1,а. На рис. 5.1, б показаны результаты расчета минимальной стоимости дуг, входящих в каждую вершину, а на рис 5 1, в изображен граф поиска, полученный на момент останова программы, реализующей вышеупомянутый алгоритм. Определенное таким образом конечное состояние имеет вид а его стоимость равна 11. Отметим, что в случае равенства оценок среди всех состояний с наименьшей оценкой выбирается для раскрытия самое глубинное состояние в графе поиска, т. е. принятое правило работает по принципу «больше влево».

На рис. 5.1, в для каждого состояния отмечено значение оценочной функции

Кроме того, в рамке отмечен порядковый номер раскрытия различных состояний. Таким образом, раскрытию был присвоен ранг 5 (но в этом случае нельзя было достичь никакого состояния-потомка) Раскрытие состояний или могло бы обеспечить другие оптимальные решения. Читатель может убедиться, что в данном примере этого не происходит