Методы исследования операций при принятии решений. Бодров В.И - 15 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Движение вдоль пути прекращается, если глубина достигла γ
пр
. После этого раскрывается самая
глубокая вершина при условии, что ее глубина не превышает γ
пр
.
После того, как все пути достигли глубины γ
пр
, кроме тех, которые были оборваны, глубина увели-
чивается и поиск продолжается до достижения большей глубины или конечного состояния.
1.3.4 МЕТОД РАВНЫХ ЦЕН
Метод равных цен заключается в том, что каждой вершине ставится в соответствие стоимость пути
от начальной вершины до рассматриваемой. При этом начальной вершине ставится в соответствие стои-
мость нуль.
Алгоритм (рис. 1.19) раскрывает ту вершину, стоимость пути для которой минимальна.
Как и раньше, блок 8 проверяет, не превышают ли уже достигнутые на новом пути затраты σ(а
n
) до
вершины a
n
стоимости М ранее построенного до конечной вершины пути.
Работа алгоритма равных цен проиллюстрирована на рис. 1.20.
Потребовалось построить всего 11 вершин, а раскрыть 6 вершин, чтобы найти наилучший путь 1-4-
3-2-1.
Данный алгоритм всегда находит глобальный оптимальный путь. Как и метод поиска вглубь, он не
рассматривает лишь те ветви, на которых не может быть минимальной стоимости, так как затраты уже
больше, чем достигнутые на всем ранее построенном пути.
1.4 Метод ветвей и границ
Все алгоритмы, рассмотренные в п. 1.3, относятся к методам слепого поиска. Про них можно
сказать, что это "близорукие" стратегии. Так, в методе равных цен для раскрытия выбирается верши-
на, путь до которой имел минимальную стоимость. Однако дальнейший путь до конечной вершины
может оказаться любым, и вполне возможно, что раскрываемая вершина не только не стоит на наи-
лучшем пути, а, может быть, на очень неудачном. Напротив, вершина, путь которой очень дорог,
может оказаться перспективной, если дальнейший путь от нее до конечной вершины будет дешевым.
Метод ветвей и границ учитывает не только, какова цена пути до некоторой вершины a
n
, но и про-
гнозирует стоимость дальнейшего пути от этой вершины.
Первую вершину из
списка "о" переместить
в список "з".
Назвать ее а
n

Страницы