ВУЗ:
Составители:
Рубрика:
Рис. 1.15 Метод перебора в ширину
минимальны и соответствуют 9 единицам. Всего было построено 22 вершины, из которых раскрыто 16.
Задача коммивояжера не относится лишь только к путешественникам, это модель весьма широкого
класса задач. Например, задачи последовательной обработки деталей, обрабатывающихся на разных
станках в произвольном порядке; производство красителей на одном и том же оборудовании, когда очи-
стка оборудования от черного цвета для производства белого очень дорогостояща и длительна, а произ-
водство черного после белого не требует очистки вовсе. То же относится и к пластмассовым изделиям
(пленки разной толщины, технические и пищевые, разной окраски) и ко многим другим задачам. На
рис. 1.16 представлена блок-схема алгоритма поиска методом перебора вершин. Этот алгоритм работает
со списком вершин "о" и "з".
В список "о" помещаются нераскрытые дочерние вершины, перед раскрытием эти вершины пере-
мещаются в список "з", т.е. вычеркиваются из списка "о" и вносятся в список "з". Всякий раз в список
"о" помещается и список "з", а вершины перемещаются вместе с соответствующими указателями на ма-
теринскую вершину. Метод поиска вширь всегда находит глобальный экстремум, так как он строит
полный эксплицидный граф, т.е. находит стоимостную оценку всех возможных путей. Это дает воз-
можность выбрать среди них наилучший.
1.3.3 МЕТОД ПЕРЕБОРА В ГЛУБИНУ
Согласно этому методу прежде всего раскрывается та вершина, которая имеет наибольший уровень
(наибольшую глубину).
Наибольшую глубину имеет вершина, которая построена последней. Таким образом, раскрыва-
ется прежде всего вершина, построенная последней (рис. 1.17).
На рис. 1.18 изображена последовательность раскрытия вершин методом перебора вглубь. В верх-
ней части вершины цифра обозначает порядок раскрытия вершины. В центре кружка указывается уро-
вень (глубина) вершины. Алгоритм (рис. 1.17) раскрывает первой вершину самого большого уровня.
Вначале раскрывается а
0
(рис. 1.18), соответствующая городу 1. После ее раскрытия в списке "о"
образуются три дочерние вершины
, , .
После раскрытия одной из них, в частности (рис. 1.17), образуются две вершины третьего уровня
и , которые согласно алгоритму (рис. 1.17) раскрываются первыми. Таким образом, выявлен пер-
вый путь 1-2-3-4-1 и его стоимость С = 11.
Теперь раскрываются оставшиеся вершины, причем на любом пути раскрытие будет прекращено,
если затраты на нем превысят или будут равны 11.
Путь 1-2-3-4 обрывается, так как затраты равны 14. Путь 1-3 обрывается сразу, поскольку затраты
при переходе из города 1 в город 2 превышают 11 и равны 15 и т.д. Обрыв пути на рис. 1.18 обозначен
знаком "х".
Список "о"
Поместить начальную вершину
а
0
в "о"
Определяют
стоимость пути
ÂÎÑÑÒÀÍÀÂ-
ËÈÂÀÞÒ ÏÓÒÜ
ÏÎ ÑÒÐÅËÊÀÌ
Первую вершину
из "о" переместить в
список "з", назвав ее а
n
ÂÛÁÐÀÍ
ÎÏÒÈÌÀËÜ-
ÍÛÉ ÏÓÒÜ
а
n
– конечная?
Раскрыть а
n
. Установить
указатели (стрелки) от
2
Да
стоп
1
5
3
4
Да
нет7
нет
12
13
14
123
124
12
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
