Алгоритм равных цен

Пусть каждой дуге поставлена в соответствие некоторая функция стоимости . Требуется найти путь минимальной стоимости. Раскрытие вершин осуществляется в порядке возрастания их стоимости. Обозначим – стоимость некоторой вершины .

Алгоритм равных цен включает следующие шаги.

1. Поместить начальную вершину в список ОТК.

2. Если список ОТК пуст, выдать сообщение о неудаче поиска, иначе перейти к шагу 3.

3. Взять из списка ОТК ту вершину, для которой величина имеет наименьшее значение, и поместить ее в список ЗКР. Присвоить этой вершине идентификатор .

4. Если – целевая вершина, то выдать решающий путь, в противном случае перейти к шагу 5.

5. Раскрыть вершину . Если не имеет дочерних вершин, перейти к шагу 2. В противном случае для каждой дочерней вершины вычислить стоимость по формуле . Поместить эти вершины вместе с соответствующими им в список ОТК и построить указатели, ведущие от них к вершине . Перейти к шагу 2.

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

Рис. 8.4 Граф решения задачи о выборе маршрута при использовании алгоритма равных цен