Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Курсовая работа - Решение задачи коммивояжера - файл Введение стр2.doc


Курсовая работа - Решение задачи коммивояжера
скачать (194.4 kb.)

Доступные файлы (21):

1.1, 1.2 стр5.doc34kb.20.01.2009 14:21скачать
1.1 стр4.doc32kb.26.12.2005 12:31скачать
1.2 стр6.doc27kb.20.01.2009 14:23скачать
1.2 стр7.doc25kb.20.01.2009 14:23скачать
1.3 стр8.doc54kb.20.01.2009 14:24скачать
1.4 стр9.doc27kb.20.01.2009 14:25скачать
1.6 стр15.doc33kb.20.01.2009 14:27скачать
1.6 стр16.doc30kb.20.01.2009 14:26скачать
2.2, 2.1, 2.2, 2.3 стр19.doc322kb.01.06.2009 20:20скачать
2.4 стр20.doc33kb.01.06.2009 20:19скачать
2.4 стр21.doc25kb.20.01.2009 14:16скачать
2.5 стр22.doc25kb.20.01.2009 14:16скачать
2.5 стр23.doc25kb.20.01.2009 14:16скачать
2.5 стр24.doc25kb.20.01.2009 14:16скачать
2.5 стр25.doc23kb.20.01.2009 14:16скачать
Введение стр2.doc35kb.20.01.2009 14:17скачать
Введение стр3.doc24kb.20.01.2009 14:17скачать
Заключение стр24.doc24kb.20.01.2009 14:18скачать
Лист задания.doc33kb.07.12.2004 11:35скачать
Литература стр26.doc25kb.20.01.2009 14:19скачать
Приложение стр25.doc48kb.20.01.2009 14:19скачать

Введение стр2.doc



ВВЕДЕНИЕ
Дана задача коммивояжера в классической формулировке: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут посещения каждого города один раз с возвращением в исходный пункт. Кратчайший маршрут находится полным перебором, при этом оценка времени вычислений составляет t (n - 1)! без учета повторяющихся путей (например, 1-2-3-1 и 2-3-1-2). При этом в декартовом пространстве на плоскости полученный маршрут является границей неправильного многоугольника. Таким образом, можно предположить, что существует такая точка, что лучи, исходящие из нее, пересекают границы полученного многоугольника только в его вершинах. Будем называть эту точку — «центром массы» полученной фигуры. Предположим, что только вершинам многоугольника можно сопоставить понятие единичной «массы», а внутреннее пространство многоугольника «массой» не наделено. Координаты точки «центра массы» можно определить по формулам:

, где n — число городов,— координаты i[1, n]-города.

Каждому i-му городу сопоставляется луч, проходящий через точки и . После посещения города i[1, n], маршрут проходит в город j[1, n], , если при этом отрезок с концами и пересекает не более одного луча.

Предложенный алгоритм дает оценку времени вычислений t n(n - 1)(n - 2) в худшем случае и t * n * 1(n - 2) в лучшем случае при удачном выборе города – получателя для любого города - отправителя, где n — цикл по i городам - отправителям коммивояжера, (n-1)

2301055905000ПЗ


Лист

Дата

Подпись

№ документа

Лист

Изм.

2



Скачать файл (194.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации