ВУЗ:
Составители:
Рубрика:
Вершина раскрывается, появляются вершины второго уровня (рис. 1.15), соответствующие горо-
дам 2, 3, 4, в которые имеет право направиться коммивояжер. Соответствующие состояния дочерних
вершин будут , , . . Эти состояния представляют собой
список уже пройденных городов.
Затем применяется оператор раскрытия к вершинам второго уровня. При этом учитывается, что из
вершины "а" коммивояжер может направиться только в города 3 и 4, в город 1 возвращаться рано, так
как коммивояжер не прошел еще всех городов. Применяя этот алгоритм, можно построить весь путь,
т.е. перевести имплицидное задание дерева в эксплицидное.
При раскрытии вершин 4-го уровня алгоритм отправляет коммивояжера назад в город 1, так как
все города пройдены.
Для каждого пути внизу проставлена суммарная цена пути, равная сумме цен соответствующего
перехода. Как видно из рис. 1.15, оптимальным маршрутом является путь 1-4-3-2-1. Потери на этом
пути
12
13
14
У
р
овень
123
1234
1
2
3
4
1
1
2
15
3
2 3 4
12
13 14
124
132
134 143
142
5
6
7
8
9
10
1324
11
13
15
12
14
16
1423
1243 1342
1432
17 19 21
18
20
22
12341
13421 14231
12431 13421 14321
5
5
8
2
2
8
3
2
3 8
8
5
2
2 6
2
1
6 1
9
11
27 22
15 26
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
