ВУЗ:
Составители:
Рубрика:
Если принять ψ(a
i
) ≡ 0, то (1.1) соблюдается, и оптимальный путь будет найден. Но при этом алго-
ритм метода ветвей и границ превратится в алгоритм равных цен, для нахождения оптимального пути
потребуется раскрыть слишком много вершин.
Следовательно, необходимо, чтобы прогноз ψ(a
i
), оставаясь меньше ψ
*
(a
i
) для каждой a
i
, давал как
можно большую оценку. Другими словами, требуется, чтобы функция ψ(a
i
) была как можно ближе к
нижней границе оценки функции ψ
*
(a
i
).
В качестве примера решим рассмотренную уже ранее задачу комивояжера (рис. 1.14).
Оценочная функция ψ(a
i
) выбирается, как среднее расстояние от города а
i
до тех городов, в кото-
рых комивояжер еще не побывал, включая и город 1, в который ему предстоит вернуться.
Итак, для первой вершины , как всегда, q( ) = 0, а обещание ψ( ) = (0 + 2 + 15 + 3)/4 = 5.
Таким образом, Q( ) = 5 (рис. 1.22).
Рис. 1.22 Метод ветвей и границ с оценочной функцией
среднего расстояния до непройденных городов
Для ее дочерних вершин , , расчеты Q(a
ι
) сведены в табл. 1.2. Наименьшее значение
Q соответствует вершине
(рис. 1.22).
Оценки дочерних вершин и приведены в табл. 1.2
1.2 Оценки вершин
Порядо
к
раскры-
тия
вершин
Вер-
шина
а
i
Прой-
ден-
ный
путь
q(a
i
)
Города,
которые
необхо-
димо
посетить
Расстоя-
ние
до горо-
да
ψ(а
i
)
Q
(a
i
)
1
9
1
13
14
12
12
124
142
143
14321
1432
2
5
8
15
3
8
3
2
9
2
6,7
18,3
3
4,3
11
12,5
14
4
10
5
9
9
1
1
1
1
123
124
12
14
12
13
Страницы
- « первая
- ‹ предыдущая
- …
- 17
- 18
- 19
- 20
- 21
- …
- следующая ›
- последняя »
