Програмне забезпечення ЕОМ

Теперь будем рассуждать от приведенной матрицы на табл. 1. Если в ней удастся построить  правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими

подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 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 или больше. Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 5 с вычеркнутой первой строкой и вторым столбцом.

Дополнительно в уменьшенной матрице  поставлен запрет в клетке (2,1), т. к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу можно привести на 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	-
табл. 4

 

	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	-
табл. 5

 

	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	-
табл. 6

 

	3	4	5	6
2	1	4	1	0
4	01	-	1	3
5	0	1	-	0

 

 

 

Кружки представляют классы: верхний  кружок – класс всех туров; нижний левый – класс всех туров, включающих ребро (1,2); нижний правый – класс всех туров, не включающих ребро (1,2). Числа над кружками – оценки снизу.

 Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C[1,2] на табл. 6. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7 есть 35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C[(1,2),(3,1)] на табл. 7. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. [3,1,2], и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (табл. 8), таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (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	-
табл. 8

 

	3	4	6
2	1	3	03
4	03	-	3
5	0	03	0
табл. 9

	3	4
4	0	-
5	0	0
табл. 10

 

 

 

 

 

 

 

 

Оцениваем теперь нули в  приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 9. Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается (рис.8).

Оценивая нули в матрице  на табл. 9, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на табл. 11.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1→2→6→5→4→3→1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего  тура не содержат. Поэтому соответствующие  вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

Для получения  оценки положительного варианта исключаем  из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 1.

Удовлетворительных теоретических  оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.

 

2.2 Метод динамического программирования

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

Пусть i – произвольный город (i Î N), а V – любое подмножество городов, не содержащее города 1 и города i. Через М(i, V ) обозначим совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Через В(i, V ) обозначим длину кратчайшего пути множества М(i, V ). Для решаемой задачи В(i, V ) – функция Беллмана. Как очевидно, В(1, {2, 3, …, n}) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города.

Если V – одноэлементное множество, V ={j}, где j ≠ 1 и j ≠ i, то совокупность М (i, V) состоит из единственного пути µ   = (i, j, 1). Поэтому

       i ÎN,  j Î {2, 3,…, n},   j ≠ i. (1.1)

Предположим, что значения функции В(i, V ) для всех i ÎN \ {1} и всех возможных k-элементных (k < n – 1) множеств V уже вычислены. Тогда значение В(i, V'), где V' – произвольное (k + 1)-элементное подмножество совокупности N \ {1, i}, вычисляется по формуле

(1.2)

Уравнения (1.1)–(1.12) – рекуррентные соотношения динамического программирования для решения задачи коммивояжера, они обеспечивают реализацию обратного метода Беллмана. Вычислительная сложность задачи равна ,где С – произвольная константа (С > 0), n – число городов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. ПРОЕКТИРОВАНИЕ АРХИТЕКТУРЫ РАЗРАБАТЫВАЕМЫХ ПРОГРАММНЫХ СРЕДСТВ

3.1 Схема взаимодействия  программ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.1 Схема взаимодействия модулей программы

 

Модуль получения исходных данных: исходные данные вводятся для  дальнейшей работы программы с помощью клавиатуры или мыши.

Осуществляется проверка корректности введенных данных, если они не соответствуют требованиям, то отображается предупреждение.

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

Модуль метода динамического программирования: при передаче управления данному модулю осуществляется составления поиск кратчайшего пути по методу динамического программирования.