8. Задача коммивояжера Тема: Использование алгоритма решения задачи коммивояжера. Пример решения задачи о выборе оптимального маршрута путешествияНа этом занятии мы построим сетевую модель реальной экономической задачи. Введем сначала некоторые определения.
Циклом называется путь в сети, у которого начальная и конечная вершины пути совпадают.
Цикл называется простым, если в цикле не повторяются вершины и ребра.
Весом цикла назовем сумму весов ребер, входящих в цикл.
Простой цикл в сети, содержащий все вершины сети, называется ГАМИЛЬТОНОВЫМ циклом.
Задача о построении гамильтонова цикла минимального веса для заданной сети называется задачей КОММИВОЯЖЕРА.
Решение задачи коммивояжера является трудной задачей так, как все известные алгоритмы решения имеют экспоненциальную оценку сложности, т.е. они имеют сложность порядка O(en). Такие задачи получили название NP-полных задач. Известные алгоритмы решения таких задач являются алгоритмами полного перебора всех вариантов и не являются эффективными.
Алгоритмы построения цикла минимального веса в сети подробно разбирался на лекции. На этом занятии мы используем процедуру, реализующую такой алгоритм, для решения задачи выбора маршрута зарубежного путешествия.
1. Постановка задачи, создание мат. модели задачи. (40 мин.)
1.1 Математическое моделирование задачи о выборе маршрута зарубежного путешествия.
Прочитайте внимательно следующую задачу и постройте для нее сетевую модель - сеть с именем Trv<Номер группы><Ваш порядковый номер> (Например, Trv20202).
Задача 1.
Студент 4-ого курса Саратовского университета после успешной сдачи сессии решил попутешествовать по свету. Он решил посетить несколько городов. Вооружившись справочниками по маршрутам воздушного сообщения различных авиакомпаний, он занес в Таблицу 1 стоимости полета из одного города в другой. Виза, которую получил студент не позволяет повторно возвращаться в уже посещенный город. После составления этой таблицы, он понял, что необходимо так выбрать маршрут своего путешествия, чтобы сумма, потраченная на билеты была минимальной и, чтобы не приходилось посещать один город два раза.Предложите такой маршрут.
Таблица 1.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 Покажите свой отчет преподавателю.