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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

найти путь от любой раскрытой вершины к корню дерева, переходя по стрелке последовательно к мате-
ринским вершинам.
Ниже рассматриваются различные методы поиска оптимального пути на графе. При этом рассмат-
риваются деревья, как более простые графы. Все методы поиска на деревьях отличаются правилами вы-
бора вершины, подлежащей раскрытию в первую очередь.
МЕТОДЫ СЛЕПОГО ПОИСКА
К методам слепого поиска относятся методы, которые принимают решение о раскрытии очередной
вершины по тому результату, который уже достигнут, не принимая во внимание (не прогнозируя), ка-
кой успех ожидается при дальнейшем движении по тому или иному пути.
К методам слепого поиска относятся:
− метод полного перебора (перебора в ширину);
− метод перебора в глубину;
− метод равных цен.
Применение перечисленных методов удобно рассмотреть на примере решения задачи коммивояже-
ра, граф которой изображен
на рис. 1.14.
Рис. 1.14 Граф задачи коммивояжера
Коммивояжеру требуется последовательно обойти все города, начиная с первого, и снова вер-
нуться в него. При этом стоимость пути должна быть минимальной. Стоимость пути из города в го-
род (из вершины в вершину) указана на ребрах графа (рис. 1.14), причем стоимость на прямом и об-
ратном пути может быть различной.
Стоимость дорог для разных направлений приведена в табл. 1.1.
1.1 Стоимость дорог
Города 1 2 3 4
1 0 2 15 3
2 1 0 5 8
3 6 2 0 2
4 2 8 3 0
МЕТОД ПЕРЕБОРА В ШИРИНУ (ПОЛНОГО ПЕРЕБОРА)
В данном методе вершины раскрываются в том порядке, в котором они появляются, т.е. первой рас-
крывается вершина, которая первой и появляется. Другими словами, в этом методе вершины раскрыва-
ются слоями: сначала вершины первого уровня, затем второго и т.д.
Вершиной первого уровня будет корень дерева, соответствующий стартовому городу 1.
Далее необходимо формализовать состояние списка городов, которые коммивояжер уже прошел. Эти
состояния в рамках стоят рядом с соответствующей вершиной. Первому городу соответствует состояние
.
1
1
4
2
3
8
8
2

Страницы