Методические указания по выполнению курсовых работ по курсу (стр. 3 из 6)
Задача коммивояжера является NP-трудной задачей.
Поскольку решение исходной задачи является циклом, то окончательное решение не может быть представлено в виде дерева. Поэтому в рамках данного курса при поиске решения исходной задачи ребро из конечной вершины в начальную не будет отображаться, но будет учитываться при получении окончательного веса решения.
Методы решения
Метод ближайшего соседа и метод ближайшего города относятся к жадным методам поиска решения. Эти методы предназначены для работы на графах, в которых выполняется неравенство треугольника (в частности для евклидовой задачи коммивояжера), только в этом случае гарантируется ε‑оптимальность получаемого решения. [5].
- Метод ближайшего соседа
Более подробно данный метод и оценку получаемого решения можно посмотреть в работе [5].
Шаг 1. Произвольно выбираем вершину
убираем ее из исходного множества вершин 
, 
- множество вершин в строящемся гамильтоновом цикле, 
- множество ребер в гамильтоновом цикле.Шаг 2. Находим вершину
такую, что 
. Добавляем ребро в гамильтонов цикл 
, обозначаем 
, 
.Шаг 3. Повторяем Шаг 2 до тех пор пока
. Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины
из текущего множества 
отображать расстояние 
. Добавляемое в цикл на текущем шаге ребро 
, выделять цветом. Отображать текущую длину пути.Режим обучения:
Пользователь выбирает следующее добавляемое в цикл ребро, если ребро выбрано правильно, что оно выделяется цветом, если не правильно, то пользователь предупреждается об этом.
- Метод ближайшего города
Более подробно данный метод и оценку получаемого решения можно посмотреть в работе [5].
Шаг 1. S=1, произвольно выбираем вершину
убираем ее из исходного множества вершин 
, - множество вершин в строящемся гамильтоновом цикле, - множество ребер в гамильтоновом цикле.Шаг 2. Для каждой вершины
находим вершину 
такую, что 
и приписываем вершине 
пометку [ 
].Шаг 3. Выбрать такую вершину
, для которой 
. Добавляем в дерево вершину из пометки 
новую вершину 
вставляем после 
, следовательно множество ребер изменится следующим образом: 
. .Шаг 4. Повторяем шаги 2 и 3 тех пор пока
.Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины
из текущего множества 
отображать пометку [ ]. Добавляемое в цикл на текущем шаге ребро 
, выделять цветом. Отображать текущую длину цикла.Режим обучения:
Пользователь выбирает следующее добавляемое в цикл ребро, если ребро выбрано правильно, что оно выделяется цветом, если не правильно, то пользователь предупреждается об этом.
- Решение задачи коммивояжера на основе построения минимального остова
Более подробно с данным методом можно ознакомиться в работе [2].
Шаг 1. Выбираем шаг штрафования F.
Шаг 2. По матрице весов
, построить минимальный остов (алгоритмы см. выше).Шаг 3. Если
степень вершины 
, то полученный остов является гамильтоновым путем, выход.Штрафуем все вершины, имеющие степени больше двух:
. переход на Шаг 2.Замечание: для упрощения работы алгоритма можно изначально выбрать начальную и конечную вершину гамильтонова пути, для этого ко всем элементам матрицы
, , в соответствующих строках и столбцах прибавляется достаточно большое число, скажем 
.Указания по отображению процесса поиска решения:
Режим демонстрации:
На каждом шаге: отображать полученный остов (сам процесс построения не отображать), выделять цветом штрафуемые вершины, отображать веса ребер.
Режим обучения:
На начальном этапе пользователь задает значение штрафа. В построенном остове пользователь отмечает вершины, которые необходимо штрафовать. Если вершина выбрана правильно, то она выделяется цветом и соответственно изменяются веса смежных ребер. Если вершина выбрана не правильно, то пользователь предупреждается об этом.
- Метод на основе построения эйлерова цикла в минимальном остове
Более подробно с данным методом можно ознакомиться в работах [1, 3].
Шаг 1. Построить минимальный остов.
Шаг 2. Строим кратчайшее эйлерово дерево путем удвоения каждого ребра остова.
Шаг 3. s=1, выбрать произвольную вершину
, добавить вершину в цикл 
, пометить вершину 
как пройденную 
поместить 
в стек: 
.Шаг 4. Если s=n, выход.
Иначе, выбираем смежную с
вершину 
, для которой 
, исключаем ребро 
из эйлерова дерева, 
, 
, 
, 
поместить в стек 
.Если все смежные вершины посещены, то достаем вершину из стека
, , переходим на Шаг 4.Указания по отображению процесса поиска решения:
Режим демонстрации:
Отобразить полученный остов (сам процесс построения не отображать). На каждом шаге: выделять цветом добавляемое в цикл ребро, отображать содержимое стека и текущую длину строящегося цикла.
Режим обучения:
Пользователь выбирает добавляемые в цикл вершины. Если вершина выбрана правильно, то добавляемое ребро выделяется цветом, иначе пользователь предупреждается о неправильном выборе.