8. Задача коммивояжера
перейти к предыдущему занятиюперейти к оглавлениюперейти к следующему занятию
Тема: Использование алгоритма решения задачи коммивояжера. Пример решения задачи о выборе оптимального маршрута путешествия

 На этом занятии мы построим сетевую модель реальной экономической задачи. Введем сначала некоторые определения.

Циклом называется путь в сети, у которого начальная и конечная вершины пути совпадают.

Цикл называется простым, если в цикле не повторяются вершины и ребра.

Весом цикла назовем сумму весов ребер, входящих в цикл.

Простой цикл в сети, содержащий все вершины сети, называется ГАМИЛЬТОНОВЫМ циклом.

Задача о построении гамильтонова цикла минимального веса для заданной сети называется задачей КОММИВОЯЖЕРА.

Решение задачи коммивояжера является трудной задачей так, как все известные алгоритмы решения имеют экспоненциальную оценку сложности, т.е. они имеют сложность порядка O(en). Такие задачи получили название NP-полных задач. Известные алгоритмы решения таких задач являются алгоритмами полного перебора всех вариантов и не являются эффективными.

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

1. Постановка задачи, создание мат. модели задачи. (40 мин.)

1.1 Математическое моделирование задачи о выборе маршрута зарубежного путешествия.

Прочитайте внимательно следующую задачу и постройте для нее сетевую модель - сеть с именем Trv<Номер группы><Ваш порядковый номер> (Например, Trv20202).

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

Предложите такой маршрут.
Таблица 1.

 
Город
Саратов
Акапулько
Гонолулу
Токио
Гонконг
Лондон
Сидней
Рим
Саратов
-
190
210
680
690
460
780
750
Акапулько
190
-
380
760
790
610
670
450
Гонолулу
210
380
-
890
900
340
410
600
Токио
680
760
890
-
480
760
510
250
Гонконг
690
790
900
480
-
890
490
560
Лондон
460
610
340
760
890
-
720
600
Сидней
780
670
410
510
490
720
-
500
Рим
750
450
600
250
560
600
500
-
1.2 Просмотрите текст подсказки по теме Salesman problem (задача коммивояжера), для этого откройте подменю Help и выберите соответствующую команду.
1.3 Найдите решение задачи коммивояжера, выбрав команду Salesman problem в подменю процедур Property|NetWork. В процессе выполнения процедуры Вы должны выбрать вершину сети, с которой хотите начать построение цикла. Просмотрите результаты работы процедуры в окне результатов. В окне результатов Вы видите вес цикла минимального веса(Weight) и ребра, входящие в этот цикл. Если цикла не существует, то Вы увидите сообщение Cicle not Found в окне результатов.
1.4 Сохраните результаты работы процедуры в файле отчета (Нажать кнопку Add to Report в окне результатов). Закройте окно результатов, нажав на кнопку Close.
1.5 Просмотрите содержимое отчета (Команда Show Report в подменю Property).

2. Подготовка окончательного отчета. (40)

2.1 Опишите постановку задачи в окне отчета и приведите аргументы в пользу Вашего решения о выборе маршрута зарубежного путешествия.
2.2 Покажите свой отчет преподавателю.

перейти к предыдущему занятиюперейти к оглавлениюперейти к следующему занятию