Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема


НазваниеРешение задачи о коммивояжере методом ветвей и гра-ниц: основная схема
страница1/5
Дата публикации05.05.2013
Размер0.49 Mb.
ТипРешение
userdocs.ru > Математика > Решение
  1   2   3   4   5
Дискретная математика
Лекция 1
Общее описание метода ветвей и границ организации полного перебо-ра возможностей. Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема.
Пусть - конечное множество и - веществен-но-значная функция на нем; требуется найти минимум этой функции и эле-мент множества, на котором этот минимум достигается.

Когда имеется та или иная дополнительная информация о множестве, решение этой задачи иногда удается осуществить без полного перебора эле-ментов всего множества M. Но чаще всего полный перебор производить при-ходится. В этом случае обязательно возникает задача, как лучше перебор ор-ганизовать.

Метод ветвей и границ - это один из методов организации полного пе-ребора. Он применим не всегда, а только тогда, когда выполняются специфи-ческие дополнительные условия на множество M и минимизируемую на нем функцию. А именно, -

предположим, что имеется вещественно-значная функция на множе-стве подмножеств множества M со следующими двумя свойствами:

1) для (здесь - множество, состоящее из един-ственного элемента );

2) если и , то .

В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:

разобьем множество M на части (любым способом) и выберем ту из его частей 1, на которой функция минимальна; затем разобьем на несколько частей множество 1 и выберем ту из его частей 2, на которой минимальна функция ; затем разобьем 2 на несколько частей и выберем ту из них, где минимальна , и так далее, пока не придем к какому-либо одноэлементному множеству .

Это одноэлементное множество называется рекордом. Функция , которой мы при этом выборе пользуемся, называется оценочной. Очевидно, что рекорд не обязан доставлять минимум функции f; однако, вот какая воз-можность возникает сократить перебор при благоприятных обстоятельст-вах.

Описанный выше процесс построения рекорда состоял из последова-тельных этапов, на каждом из которых фиксировалось несколько множеств и выбиралось затем одно из них. Пусть - подмножества множества M, возникшие на предпоследнем этапе построения рекорда, и пусть множе-ство оказалось выбранным с помощью оценочной функции. Именно при разбиении и возник рекорд, который сейчас для определенности обозна-чим через . Согласно сказанному выше, , ; кроме того, по определению оценочной функции, .

Предположим, что ; тогда для любого элемента m множества M, принадлежащего множеству , будут верны неравенства

; это значит, что при полном переборе элементов из M элементы из уже вообще не надо рассматривать. Если же неравенство не будет выполнено, то все элементы из надо последова-тельно сравнить с найденным рекордом и как только отыщется элемент, дающий меньшее значение оптимизируемой функции, надо им заменить ре-корд и продолжить перебор. Последнее действие называется улучшением рекорда.

Слова метод ветвей и границ связаны с естественной графической интерпретацией всего изложенного: строится многоуровневое дерево, на нижнем этаже которого располагаются элементы множества M, на котором ветви ведут к рекорду и его улучшениям и на котором часть ветвей остаются «оборванными», потому что их развитие оказалось нецелесообразным.

Мы рассмотрим сейчас первый из двух запланированных в этом курсе примеров применения метода ветвей и границ - решение задачи о коммивоя-жере. Вот ее формулировка.

Имеется несколько городов, соединеных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по кото-рому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат («обход коммивояжера»), и, если таковой путь имеется, установить кратчайший из таких путей.

Формализуем условие в терминах теории графов. Города будут верши-нами графа, а дороги между городами - ориентированными (направленными) ребрами графа, на каждом из которых задана весовая функция: вес ребра - это длина соответствующей дороги. Путь, который требуется найти, это – ориен-тированный остовный простой цикл минимального веса в орграфе (напомним: цикл называется остовным, если он проходит по всем вершинам графа; цикл называется простым, если он проходит по каждой своей вершине только один раз; цикл называется ориентированным, если начало каждого последу-ющего ребра совпадает с концом предыдущего; вес цикла - это сумма весов его ребер; наконец, орграф называется полным, если в нем имеются все воз-можные ребра); такие циклы называются также гамильтоновыми.

Очевидно, в полном орграфе циклы указанного выше типа есть. Заме-тим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рас-смотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно до-полнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес , считая, что  - это «компьютерная бесконечность», т.е. мак-симальное из всех возможных в рассмотрениях чисел. Если во вновь постро-енном полном орграфе найти теперь легчайший гамильтонов цикл, то при на-личии у него ребер с весом  можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший га-мильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе.

Отсюла следует, что задачу о коммивояжере достаточно решить для полных орграфов с весовой функцией. Сформулируем теперь это в оконча-тельном виде:

пусть - полный ориентированный граф и -

весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

Пусть конкретный состав множества вершин и

- весовая матрица данного орграфа, т.е.

,

причем для любого .

Рассмотрение метода ветвей и границ для решения задачи о коммивоя-жере удобнее всего проводить на фоне конкретного примера. Пользуясь вве-денными здесь обозначениями, мы проводим это описание в следующей лек-ции.

Введем некоторые термины. Пусть имеется некоторая числовая матри-ца. ^ Привести строку этой матрицы означает выделить в строке минималь-ный элемент (его называют константой приведения) и вычесть его из всех элементов этой строки. Очевидно, в результате в этой строке на месте мини-мального элемента окажется ноль, а все остальные элементы будут неотрица-тельными. Аналогичный смысл имеют слова привести столбец матрицы.

Слова привести матрицу по строкам означают, что все строки матри-цы приводятся. Аналогичный смысл имеют слова привести матрицу по столбцам.

Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам.

Весом элемента матрицы называют сумму констант приведения матрицы, которая получается из данной матрицы заменой обсуждаемого элемента на . Следовательно, слова самый тяжелый нуль в матрице озна-чают, что в матрице подсчитан вес каждого нуля, а затем фиксирован нуль с максимальным весом.

Приступим теперь к описанию метода ветвей и границ для решения за-дачи о коммивояжере.

^ Первый шаг. Фиксируем множество всех обходов коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо не пусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множе-ство всех обходов коммивояжера обозначить через , то сумму констант приведения матрицы весов обозначим через (). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M1; таким обра-зом, итог первого шага:

множеству  всех обходов коммивояжера сопоставлено число () и матрица M1.

^ Второй шаг. Выберем в матрице M1 самый тяжелый нуль; пусть он стоит в клетке ; фиксируем ребро графа и разделим множество  на две части: на часть , состоящую из обходов, которые проходят через ребро , и на часть , состоящую из обходов, которые не проходят через ребро .

Сопоставим множеству следующую матрицу M1,1: в матрице M1 заменим на  число в клетке . Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M1,1; только что запомненную сумму констант приведения прибавим к () и результат, обозначаемый в дальнейшем через (), сопоставим множеству .

Теперь множеству тоже сопоставим некую матрицу M1,2. Для этого в матрице M1 заменим на  число в клетке и полученную в ре-зультате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим запомненную сумму констант приведения к числу () и полученное число, обозначаемое в дальнейшем через (), сопоставим множеству .

Теперь выберем между множествами и то, на котором ми-нимальна функция  (т.е. то из множеств, которому соответствует меньшее из чисел () и ().

Заметим теперь, что в проведенных рассуждениях использовался в ка-честве исходного только один фактический объект - приведенная матрица весов данного орграфа. По ней было выделено определенное ребро графа и были построены новые матрицы, к которым, конечно, можно все то же самое применить. При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на  числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра; эту довольно трудную фразу мы еще не раз рассмотрим в

следующей лекции на конкретном примере.

К выбранному множеству с сопоставленными ему матрицей и числом  повторим все то же самое и так далее, пока это возможно.

Доказывается, что в результате получится множество, состоящее из единственного обхода коммивояжера, вес которого равен очередному значе-нию функции ; таким образом, оказываются выполненными все условия, обсуждавшиеся при описании метода ветвей и границ.

После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.

Лекция 2

Решение задачи о коммивояжере методом ветвей и границ. Примеры.

Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере.

Итак, требуется найти легчайший простой остовной ориентированный цикл в полном взвешенном ориентированном графе на пяти вершинах со следующей весовой матрицей:





1

2

3

4

5

1



9

8

4

10

2

6



4

5

7

3

5

3



6

2

4

1

7

2



8

5

2

4

5

2




Верхняя строка и левый столбец, выделенные затемненным фоном, содержат номера вершин графа; символ , стоящий на главной диагонали, означает, естественно, отсутствие ребер-петель (начинающихся и заканчивающихся в одной и той же вершине); кроме того, символ  здесь и всюду в дальнейшем обозначает «компьютерную бесконечность», т.е. самое большое из возможных в рассмотрении чисел; считается, что +любое число =.

Подсчитаем () в нашем примере. Для этого выполним приведение матрицы весов; сначала - по строкам:






1

2

3

4

5







1



9

8

4

10

4

 min в строке 1

2

6



4

5

7

4

 min в строке 2

3

5

3



6

2

2

 min в строке 3

4

1

7

2



8

1

 min в строке 4

5

2

4

5

2



2

 min в строке 5


результат приведения по строкам:





1

2

3

4

5

1



5

4

0

6

2

2



0

1

3

3

3

1



4

0

4

0

6

1



7

5

0

2

3

0




Определим константы приведения по столбцам:





1

2

3

4

5

1



5

4

0

6

2

2



0

1

3

3

3

1



4

0

4

0

6

1



7

5

0

2

3

0






0

1

0

0

0






min в

столбце 1



min в столбце 2



min в столбце 3



min в столбце 4



min в столбце 5


результат приведения матрицы:





1

2

3

4

5

1



4

4

0

6

2

2



0

1

3

3

3

0



4

0

4

0

5

1



7

5

0

1

3

0




сумма констант приведения ()=4+4+2+1+2+1=14.

Обозначим эту матрицу через M1; найдем в ней самый тяжелый нуль. Для этого запишем эту матрицу еще раз, указывая рядом с каждым нулем в скобках его вес:






1

2

3

4

5

1



4

4

0(4)

6

2

2



0(2)

1

3

3

3

0(1)



4

0(3)

4

0(1)

5

1



7

5

0(0)

1

3

0(0)




Самым тяжелым оказывается нуль в клетке (1,4). Следовательно, множество  разбивается на (все циклы, проходящие через ребро (1,4)) и (все циклы, не проходящие через ребро (1,4)).

Построим для множества соответствующую ему матрицу и зна-чение оценочной функции. Сейчас уместно отдельным абзацем напомнить ту самую «сложную» фразу из предыдущей лекции:

^ Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на  числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра.

Учитывая это напоминание, элемент с номером (4,1) заменим на  и вычеркнем строку номер 1 и столбец номер 4:





1

2

3

5

2

2



0

3

3

3

0



0

4



5

1

7

5

0

1

3




Приведем теперь эту матрицу:






1

2

3

5

2

2



0

3

3

3

0



0

4



4

0

6

5

0

1

3




Это - матрица ^ M1,1; сумма констант приведения здесь равна 1, поэтому 14+1= 15.

Для M1,2 заменяем на  элемент (1,4) в M1:






1

2

3

4

5

1



4

4



6

2

2



0

1

3

3

3

0



4

0

4

0

5

1



7

5

0

1

3

0




после этого приводим полученную матрицу:





1

2

3

4

5

1



0

0



2

2

2



0

1

3

3

3

0



4

0

4

0

5

1



7

5

0

1

3

0




Это - матрица M1,2; сумма констант последнего приведения равна 4, так что 14+4=18. Следовательно, дальнейшей разработке подвергается множество .

Вот веса нулей матрицы M1,1 (они указаны в скобках):





1

2

3

5

2

2



0(2)

3

3

3

0(1)



0(3)

4



4

0(4)

6

5

0(3)

1

3




самым тяжелым является нуль с номером (4,3), так что теперь следует рассматривать множества и .

Обратимся к первому из них. Опять напомним ту самую «сложную» фразу из предыдущей лекции:

^ Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на  числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра.

Следовательно, клетки с номерами (4,2), (4,5) и (3,1) надо заполнить символом ; после этого строку номер 4 и столбец номер 3 следует вычерк-нуть; получим:





1

2

5

2

2



3

3



0

0

5

0

1




Приведение этой матрицы:





1

2

5

2

0



1

3



0

0

5

0

1




Для оценочной функции: =15+2=17.

Матрица для множества :




1

2

3

5

2

2



0

3

3

3

0



0

4



4



6

5

0

1

3



Результат ее приведения:





1

2

3

5

2

2



0

3

3

3

0



0

4



0



2

5

0

1

3




Оценочная функция: =15+4=19. Следовательно, дальнейшей разработке подлежит . «Взвешиваем» нули:





1

2

5

2

0(1)



1

3



0(1)

0(1)

5

0(1)

1




Выбираем любую из соответствующих клеток; для определенности - клетку (2,1).

Теперь речь пойдет о множествах и .

Опять напомним фразу:

^ Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на  числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра. Поэтому для первого множества положим в последней матрице элемент с номером (3,2) равным , вычеркнем строку номер 2 и столбец номер 1:





2

5

3



0

5

1




Приведем эту матрицу:





2

5

3



0

5

0




Получаем для оценочной функции: =17+1=18.

Для множества матрица такова:






1

2

5

2





1

3



0

0

5

0

1




Приведение этой матрицы дает:





1

2

5

2





0

3



0

0

5

0

1




Для оценочной функции: =17+1=18.

Получилось, что для дальнейшей разработки можно брать любое из множеств и . В первом случае уже получена матрица размером 22; ее нулевые клетки дают те ребра, которые с найденными ранее составляют обход коммивояжера, причем вес этого обхода равен значению оценочной функции - 18. Вот этот обход:
(1,4)(4,3)(2,1)(5,2)(3,5) или 143521.
Найденный рекорд на самом деле является искомым оптимумом,

потому что значения оценочной функции на всех оборванных ветвях (на границах) больше или равны весу рекорда.

При ином варианте выборов по ходу разбиений можно было

получить другой оптимум: 143251.
  1   2   3   4   5

Похожие:

Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема icon1. Решение систем линейных алгебраических уравнений методом простой итерации
Эвм и дающих за конечное число действий решение дискретной задачи. Полученное решение дискретной задачи принимается за приближенное...
Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconАна-ая: гра-ми; гра-ми; гра-ми; гра-ми

Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconРешение принять решение это уже решение
Кейс (от английского case) — многозначное понятие, которое в данном контексте трактуется как случай, казус (от латинского casus),...
Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconОсновные задачи исследования
Разработать теоретический подход к решению задачи построения кт методом коллоидного синтеза
Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconПояснительная записка (обосновывающие материалы)
Схема функционального зонирования территории. Схема зон планируемого размещения объектов капитального строительства. Схема первоочёредного...
Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconПояснительная записка (обосновывающие материалы)
Схема функционального зонирования территории. Схема зон планируемого размещения объектов капитального строительства. Схема первоочередного...
Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconПояснительная записка (обосновывающие материалы)
Схема функционального зонирования территории. Схема зон планируемого размещения объектов капитального строительства. Схема первоочередного...
Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconЛабораторная работа № Тема: Решение задачи о загрузке методом динамического...
Необходимо определить оптимальное распределение грузов между суднами, обеспечивающее минимизацию затрат предприятий. Таким образом,...
Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconСтруктурная минимизация систем управления, наблюдения и стабилизации
Решение этой задачи возможно редуцировать на линейные стационарные системы наблюдения, т к задача управляемости и наблюдаемости для...
Решение задачи о коммивояжере методом ветвей и гра-ниц: основная схема iconПрактическое задание по курсу
Найти корень уравнения с точностью в интервале изоляции корня [ 5;0] методом Ньютона и методом дихотомии
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница