• скачать файл

Курсовая работа по информатике

с. 1

Курсовая работа по информатике


(Задача коммивояжера)
Краткий алгоритм решения задачи коммивояжера – поиска кратчайшего(наиболее дешевого пути)

  1. Для заданной матрицы : N x N (N =6) определить минимальное значение в каждой строке и вычесть его из всех значений строки, получив таким образом матрицу, в которой в каждой строе имеется по крайней мере один ноль, минимальные значения найденные в строках сложить, получив некоторую предварительную сумму S. Затем в получившейся матрице определить минимальное значение в каждом столбце и также вычесть его из всех значений столбца, получив в итоге матрицу, в которой в каждой строке и каждом столбце имеется по крайней мере один ноль. Минимальные значения, найденные в столбцах сложить с предварительной суммой S, получив тем самым величину S – минимальную стоимость проезда. Таким образом, результатом первого этапа является приведенная матрица N x N и предварительная минимальная сумма стоимости проезда – S.

  2. В полученной приведенной матрице определить в каждой строке минимальное число, за исключением одного нуля, затем среди этих минимальных чисел определить максимальное и номер строки матрицы - k, в которой находится это число. Найти в этой строке первый нулевой элемент и номер столбца- l в котором он был найден. Таким образом, результатом второго этапа являются два числа соответствующие номеру города, откуда необходимо ехать – k и номеру города – куда ехать - l.

  3. Получить новую матрицу размером N-1 x N-1 соответствующую предыдущей матрице размером N x N , c вычеркнутой k- той строкой и вычеркнутым l – тым столбцом. В соответствие с имеющимся к этому моменту маршрутом в получившейся матрице установить, если это необходимо, значение в соответствующей ячейке матрицы.

Получить дополнительную матрицу размером N x N соответствующую предыдущей матрице размером N x N c установленным значением в ячейке, находящейся на пересечении k- той строки и l – того столбца.

Продолжить выполнение алгоритма поиска кратчайшего пути, вернувшись к шагу 1 с новыми матрицами размера N-1 x N-1 и N x N.


Исходным заданием для выполнения данной курсовой работы является матрица 6 x 6 заполненная числами в соответствие с фамилией именем и отчеством студента. Например: Студент ИВАНОВ ИВАН ИВАНОВИЧ в качестве исходного задания получает следующую матрицу:



И

В

А

Н

О

В



И

В

А

Н

И

В



А

Н

О

В

И

Ч



И

В

А

Н

О

В



И

В

А

Н

И

В



После чего все буквы заменяются на соответствующие им порядковые номера по алфавиту:

1

А

11

Й

21

У

31

Э

2

Б

12

К

22

Ф

32

Ю

3

В

13

Л

23

Х

33

Я

4

Г

14

М

24

Ц







5

Д

15

Н

25

Ч







6

Е

16

О

26

Ш







7

Ё

17

П

27

Щ







8

Ж

18

Р

28

Ъ







9

З

19

С

29

Ы







10

И

20

Т

30

Ь






Таким образом, для студента ИВАНОВа ИВАН ИВАНОВИЧа исходная матрица стоимостей будет следующей:



















Номер города







































































































Номер города






















Результатом курсового проекта должна быть решенная задача коммивояжера задачи.
Пример решения для студента ИВАНОВа ИВАН ИВАНОВИЧа:

Шаг 1:














Минимальное значение в строке = 1













Минимальное значение в строке = 1













Минимальное значение в строке = 1













Минимальное значение в строке = 3













Минимальное значение в строке = 1













Минимальное значение в строке = 1

После вычитания минимальных значений по строкам получим:









































































































Минимальные значения по столбцам

После вычитания минимальных значений по столбцам получим:









































































Минимальная сумма проезда = 1+1+1+3+1+1+0+0+2+0+0+0= 10

Шаг 2:

















Номер города















Минимальное число за исключением одного нуля = 0















Минимальное число за исключением одного нуля = 2















Минимальное число за исключением одного нуля = 2















Минимальное число за исключением одного нуля = 0















Минимальное число за исключением одного нуля = 2















Минимальное число за исключением одного нуля = 2

k=2 , l=5 таким образом предварительный вариант : из города № 2  в город № 5

Шаг 3:

Получается сокращенная матрица 5 х 5 вычеркиванием столбца, соответствующего 5 городу и строки, соответствующей 2 городу:











































































Так как эта матрица получена для варианта из 2  в 5 , то из 5  в 2 – нельзя, следовательно, на пересечении 5 и 2 необходимо поставить 

Дополнительная матрица получается, если принять альтернативный вариант – из 2 в 5 не ехать тогда в ячейке на пересечение столбца, соответствующего 5 городу и строки, соответствующей 2 городу устанавливаем ,





































































































Продолжаем алгоритм, вернувшись к шагу 1 с новыми матрицами размером 5 х 5 и 6 х 6.

Шаг1.






























Минимальное значение в строке = 0













Минимальное значение в строке = 0













Минимальное значение в строке = 0













Минимальное значение в строке = 0













Минимальное значение в строке = 0












































































































Минимальное значение в столбце

Таким образом, минимальная стоимость поездки при выборе маршрута из 2 в 5 осталась прежней : 10

Проведем теперь анализ измененной матрицы 6 х 6:



































Минимальное значение в строке = 0















Минимальное значение в строке = 2















Минимальное значение в строке = 0















Минимальное значение в строке = 0















Минимальное значение в строке = 0















Минимальное значение в строке = 0

После вычитания минимальных значений по строкам получим:








































































































































Минимальные значения по столбцам

Таким образом, минимальная стоимость поездки при выборе маршрута не ехать из 2 в 5 получается : 10+2+2 =14

Поэтому первоначально выбираем движение по маршруту из 2 в 5 и переходим к шагу 2 с матрицей 5 х 5 .































Минимальное значение в строке за исключением одного нуля = 0













Минимальное значение в строке за исключением одного нуля = 2













Минимальное значение в строке за исключением одного нуля = 0













Минимальное значение в строке за исключением одного нуля = 2













Минимальное значение в строке за исключением одного нуля = 2

k=3 , l=4 таким образом предварительный вариант : из города № 2  в город № 5 и из города № 3  в город № 4.

Шаг 3:

Получается сокращенная матрица 4 х 4 вычеркиванием столбца, соответствующего 4 городу и строки, соответствующей 3 городу:






















































Так как эта матрица получена для варианта из 3  в 4 , то из 4  в 3 – нельзя, следовательно, на пересечении 4 и 3 необходимо поставить 

Дополнительная матрица получается, если принять альтернативный вариант – из 3 в 4 не ехать тогда в ячейке на пересечение столбца, соответствующего 4 городу и строки, соответствующей 3 городу устанавливаем ,












































































Продолжаем алгоритм, вернувшись к шагу 1 с новыми матрицами размером 4 х 4 и 5 х 5.

Шаг1.


























Минимальное значение в строке = 0











Минимальное значение в строке = 0











Минимальное значение в строке = 0











Минимальное значение в строке = 0
















































































Минимальное значение в столбце

Таким образом, минимальная стоимость поездки при выборе маршрута из 2 в 5 и из 3 в 4 осталась прежней : 10

Проведем теперь анализ измененной матрицы 5 х 5:































Минимальное значение в строке = 0













Минимальное значение в строке = 2













Минимальное значение в строке = 0













Минимальное значение в строке = 0













Минимальное значение в строке = 0

После вычитания минимальных значений по строкам получим









































































































Минимальное значение в столбце

Таким образом, минимальная стоимость поездки при выборе маршрута из 2 в 5 и не ехать из 3 в 4 получается : 10+2=12

Поэтому первоначально выбираем движение по маршруту из 2 в 5 и из 3 в 4 и переходим к шагу 2 с матрицей 4 х 4:




























Минимальное значение в строке за исключением одного нуля = 9











Минимальное значение в строке за исключением одного нуля = 0











Минимальное значение в строке за исключением одного нуля = 9











Минимальное значение в строке за исключением одного нуля = 2

k=1 , l=3 таким образом предварительный вариант : из города № 2  в город № 5, из города № 3  в город № 4 и из города № 1  в город № 3.

Шаг 3:


Получается сокращенная матрица 3 х 3 вычеркиванием столбца, соответствующего 3 городу и строки, соответствующей 1 городу


































Так как эта матрица получена для варианта из2 в5, из1 в3 и из 3  в 4 , то из 4  в 1 – нельзя, следовательно, на пересечении 4 и 1 необходимо поставить 

Дополнительная матрица получается, если принять альтернативный вариант – из 1 в 3 не ехать тогда в ячейке на пересечение столбца, соответствующего 3 городу и строки, соответствующей 1 городу устанавливаем ,






















































Продолжаем алгоритм, вернувшись к шагу 1 с новыми матрицами размером 3х 3 и 4 х 4

Шаг1.






















Минимальное значение в строке = 0









Минимальное значение в строке = 0









Минимальное значение в строке = 0

























































Минимальное значение в столбце

Таким образом, минимальная стоимость поездки при выборе маршрута из 2 в 5, из 1 в 3 и из 3 в 4 осталась прежней : 10

Проведем теперь анализ измененной матрицы 4 х 4:




























Минимальное значение в строке = 9











Минимальное значение в строке = 0











Минимальное значение в строке = 0











Минимальное значение в строке = 0

После вычитания минимальных значений по строкам получим














































































Минимальное значение в столбце

После вычитания минимальных значений по столбцам получим






















































Таким образом, минимальная стоимость поездки при выборе маршрута из 2 в 5 ,из 3 в 4 и не ехать при этом из 1 в 3составляет : 10+9+12=31 что существенно больше предыдущего варианта. Поэтому первоначально выбираем движение по маршруту из 2 в 5, из 1 в 3 и из 3 в 4 и переходим к шагу 2 с матрицей 3 х 3:

Шаг 2:























Минимальное значение в строке за исключением одного нуля = 7









Минимальное значение в строке за исключением одного нуля = 9









Минимальное значение в строке за исключением одного нуля = 2

k=5 , l=1 таким образом предварительный вариант : из города № 2  в город № 5 , из города № 3  в город № 4, из города № 1  в город № 3 и из города № 5  в город № 1 .

Шаг 3:


Получается сокращенная матрица 2 х 2 вычеркиванием столбца, соответствующего 1 городу и строки, соответствующей 5 городу:




















Так как эта матрица получена для варианта из2 в5, из5 в1, из1 в3 и из 3  в 4 , то из 4  в 2 – нельзя, следовательно, на пересечении 4 и 2 необходимо поставить 

Дополнительная матрица получается, если принять альтернативный вариант – из 5 в 1 не ехать тогда в ячейке на пересечение столбца, соответствующего 5 городу и строки, соответствующей 1 городу устанавливаем ,






































Продолжаем алгоритм, вернувшись к шагу 1 с новыми матрицами размером 2х 2 и 3 х 3

Шаг1.


















Минимальное значение в строке = 0







Минимальное значение в строке = 0






































Минимальное значение в столбце

Таким образом, минимальная стоимость поездки при выборе маршрута из 2 в 5, из 5 в 1 из 1 в 3 и из 3 в 4 осталась прежней : 10

Проведем теперь анализ измененной матрицы 3 х 3:























Минимальное значение в строке = 0









Минимальное значение в строке = 9









Минимальное значение в строке = 0

После вычитания минимальных значений по строкам получим

























































Минимальное значение в столбце

После вычитания минимальных значений по столбцам получим



































Таким образом, минимальная стоимость поездки при выборе маршрута из 2 в 5 ,из 3 в 4 , из 1 в 3 и не ехать при этом из 5 в 1 составляет : 10+9+2=21, что существенно больше предыдущего варианта. Поэтому первоначально выбираем движение по маршруту из 2 в 5, из 5 в 1, из 1 в 3 и из 3 в 4 и переходим к шагу 2 с матрицей 2 х 2:

Шаг 2:


















Минимальное значение в строке за исключением одного нуля = 0







Минимальное значение в строке за исключением одного нуля = 0

k=4 , l=6 таким образом предварительный вариант : из города № 2  в город № 5 , из города № 3  в город № 4, из города № 1  в город № 3 из города № 5  в город № 1 , и из города № 4  в город № 6 .При этом единственной оставшейся возможностью оказывается поездка из города № 6  в город № 2 стоимость которой по приведенной матрице составляет 0.

В результате получаем маршрут 3462513 стоимость которого составляет 10 единиц.

Так как все альтернативные варианты рассмотренные в процессе поиска оптимального маршрута имели более высокую стоимость, то их можно не рассматривать.



Замечание: Если бы среди промежуточных альтернативных вариантов имелись бы маршруты со стоимостью меньшей чем 10, то потребовалось бы их рассмотреть.
с. 1