Курсовая работа: Задача коммивояжера
Тур можно задать системой из шести подчеркнутых (выделенных другим цветом)
элементов матрицы С, например, такой, как показано на табл. 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 |
Дополнительно
в уменьшенной матрице поставлен запрет в клетке (2,1), т. к. выбрано ребро
(1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу
можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий,
стоит не меньше 35. Результат наших ветвлений и получения оценок показан на
рис.6.
Кружки представляют классы: верхний кружок
– класс всех туров; нижний левый – класс всех туров, включающих ребро (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 и
более.
|
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 |
Оцениваем
теперь нули в приведенной матрице C[(1,2),(3,1)]
нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант
имеет оценку 38+3=41. Для получения оценки положительного варианта убираем
строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрица
неприводима. Следовательно, оценка положительного варианта не увеличивается
(рис.8).
Страницы: 1, 2, 3, 4, 5, 6, 7 |