close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Курсовая работа по информатике
(Задача коммивояжера)
Краткий алгоритм решения задачи коммивояжера – поиска кратчайшего(наиболее
дешевого пути)
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, то потребовалось бы их рассмотреть.
Документ
Категория
Математика
Просмотров
18
Размер файла
115 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа