Задача коммивояжера
Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.
Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на табл. 2. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На табл. 2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.
Теперь будем рассуждать от приведенной матрицы на табл. 2. Если в ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров.
Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились).
Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).
Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса – включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.
Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 6 с вычеркнутой первой строкой и вторым столбцом.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | - | 01 | 0 | 3 | 3 | 6 |
| 2 | 01 | - | 1 | 4 | 1 | 0 |
| 3 | 1 | 2 | - | 01 | 0 | 3 |
| 4 | 4 | 5 | 01 | - | 1 | 3 |
| 5 | 4 | 2 | 0 | 1 | - | 0 |
| 6 | 7 | 1 | 3 | 3 | 01 | - |
| табл. 5 |
| 1 | 3 | 4 | 5 | 6 | |
| 2 | 01 | 1 | 4 | 1 | 0 |
| 3 | 1 | - | 01 | 0 | 3 |
| 4 | 4 | 01 | - | 1 | 3 |
| 5 | 4 | 0 | 1 | - | 0 |
| 6 | 7 | 3 | 3 | 01 | - |
| табл. 6 |
| 1 | 3 | 4 | 5 | 6 | |
| 2 | 01 | 1 | 4 | 1 | 0 |
| 3 | 03 | - | 01 | 0 | 3 |
| 4 | 3 | 01 | - | 1 | 3 |
| 5 | 3 | 0 | 1 | - | 0 |
| 6 | 6 | 3 | 3 | 01 | - |
| табл. 7 |
| 3 | 4 | 5 | 6 | ||
| 2 | 1 | 4 | 1 | 0 | |
| 4 | 01 | - | 1 | 3 | |
| 5 | 0 | 1 | - | 0 | |
| 6 | 3 | 3 | 01 | - | |
| табл. 8 |
| 3 | 4 | 5 | 6 | |
| 2 | 1 | 3 | 1 | 0 |
| 4 | 01 | - | 1 | 3 |
| 5 | 0 | 02 | - | 0 |
| 6 | 3 | 2 | 03 | - |
| табл. 9 |
| 3 | 4 | 6 | |
| 2 | 1 | 3 | 03 |
| 4 | 03 | - | 3 |
| 5 | 0 | 03 | 0 |
| табл. 10 |
| 3 | 4 | |
| 4 | 0 |
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |
Кружки представляют классы: верхний кружок
– класс всех туров; нижний левый – класс всех туров, включающих ребро (1,2);
нижний правый – класс всех туров, не включающих ребро (1,2). Числа над кружками
– оценки снизу.
Продолжим ветвление в положительную сторону: влево - вниз. Для
этого оценим нули в уменьшенной матрице C[1,2] на табл. 7. Максимальная оценка в
клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7
есть 35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из
матрицы C[1,2] еще строку 3 и
столбец 1, получив матрицу C[(1,2),(3,1)] на табл. 8. В эту матрицу нужно поставить запрет в
клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е.
[3,1,2], и нужно запретить преждевременное замыкание (2,3). Эта матрица
приводится по столбцу на 1 (табл. 9), таким образом, каждый тур
соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и
более.