Решение задачи коммивояжёра
Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Использование операции редукции для определения нижней границы множества. Вычисление ребра ветвления. Получение сокращенной матрицы, которая подлежит операции приведения.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 16.03.2014 |
| Размер файла | 18,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Решение задачи коммивояжёра
План
Введение
1. Задача
Введение
Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр - странствующий торговец) - одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз.
1. Задача
Требуется найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов A1, A2,…, A6. Задана матрица расстояний между любыми парами городов, причём расстояние от города Ai до города Aj может не совпадать с расстоянием от Ai до Aj. Элемент матрицы aij считается равным расстоянию от Ai до Aj, где с = m + n
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
||
|
A1 |
- |
c+2 |
2c |
c+3 |
2c |
c+1 |
|
|
A2 |
c |
- |
c+5 |
c-1 |
c-1 |
3c |
|
|
A3 |
c |
c+1 |
- |
c+7 |
c+2 |
c+3 |
|
|
A4 |
c-1 |
c+2 |
c |
- |
c+1 |
c-1 |
|
|
A5 |
c+5 |
c+2 |
c |
c |
- |
2c |
|
|
A6 |
c |
c+1 |
c+2 |
c+5 |
c+7 |
- |
Решение.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 4 + 7 + 9 + 3 + 4 + 2 = 29
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
4 |
4 |
5 |
4 |
3 |
3 |
|
|
2 |
2 |
M |
7 |
1 |
1 |
6 |
1 |
|
|
3 |
2 |
3 |
M |
9 |
4 |
5 |
2 |
|
|
4 |
1 |
3 |
2 |
M |
3 |
1 |
1 |
|
|
5 |
7 |
4 |
1 |
1 |
M |
4 |
1 |
|
|
6 |
2 |
3 |
4 |
7 |
9 |
M |
2 |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
1 |
1 |
2 |
1 |
0 |
|
|
2 |
1 |
M |
6 |
0 |
0 |
5 |
|
|
3 |
0 |
1 |
M |
7 |
2 |
3 |
|
|
4 |
0 |
2 |
1 |
M |
2 |
0 |
|
|
5 |
6 |
3 |
0 |
0 |
M |
3 |
|
|
6 |
0 |
1 |
2 |
5 |
7 |
M |
|
|
dj |
0 |
1 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
0 |
1 |
2 |
1 |
0 |
|
|
2 |
1 |
M |
6 |
0 |
0 |
5 |
|
|
3 |
0 |
0 |
M |
7 |
2 |
3 |
|
|
4 |
0 |
1 |
1 |
M |
2 |
0 |
|
|
5 |
6 |
2 |
0 |
0 |
M |
3 |
|
|
6 |
0 |
0 |
2 |
5 |
7 |
M |
Шаг№1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
0(0) |
1 |
2 |
1 |
0(0) |
0 |
|
|
2 |
1 |
M |
6 |
0(0) |
0(1) |
5 |
0 |
|
|
3 |
0(0) |
0(0) |
M |
7 |
2 |
3 |
0 |
|
|
4 |
0(0) |
1 |
1 |
M |
2 |
0(0) |
0 |
|
|
5 |
6 |
2 |
0(1) |
0(0) |
M |
3 |
0 |
|
|
6 |
0(0) |
0(0) |
2 |
5 |
7 |
M |
0 |
|
|
dj |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (2,5), следовательно, множество разбивается на два подмножества (2,5) и (2*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
0 |
1 |
2 |
1 |
0 |
0 |
|
|
2 |
1 |
M |
6 |
0 |
M |
5 |
0 |
|
|
3 |
0 |
0 |
M |
7 |
2 |
3 |
0 |
|
|
4 |
0 |
1 |
1 |
M |
2 |
0 |
0 |
|
|
5 |
6 |
2 |
0 |
0 |
M |
3 |
0 |
|
|
6 |
0 |
0 |
2 |
5 |
7 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
1 |
2 |
3 |
4 |
6 |
di |
|
|
1 |
M |
0 |
1 |
2 |
0 |
0 |
|
|
3 |
0 |
0 |
M |
7 |
3 |
0 |
|
|
4 |
0 |
1 |
1 |
M |
0 |
0 |
|
|
5 |
6 |
M |
0 |
0 |
3 |
0 |
|
|
6 |
0 |
0 |
2 |
5 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
0 |
0 |
Поскольку нижняя граница этого подмножества (2,5) меньше, чем подмножества (2*,5*), то ребро (2,5) включаем в маршрут.
Шаг№2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
|
i j |
1 |
2 |
3 |
4 |
6 |
di |
|
|
1 |
M |
0(0) |
1 |
2 |
0(0) |
0 |
|
|
3 |
0(0) |
0(0) |
M |
7 |
3 |
0 |
|
|
4 |
0(0) |
1 |
1 |
M |
0(0) |
0 |
|
|
5 |
6 |
M |
0(1) |
0(2) |
3 |
0 |
|
|
6 |
0(0) |
0(0) |
2 |
5 |
M |
0 |
|
|
dj |
0 |
0 |
1 |
2 |
0 |
0 |
Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (5,4), следовательно, множество разбивается на два подмножества (5,4) и (5*,4*). коммивояжер матрица математический редукция
Нижняя граница гамильтоновых циклов этого подмножества:
|
i j |
1 |
2 |
3 |
4 |
6 |
di |
|
|
1 |
M |
0 |
1 |
2 |
0 |
0 |
|
|
3 |
0 |
0 |
M |
7 |
3 |
0 |
|
|
4 |
0 |
1 |
1 |
M |
0 |
0 |
|
|
5 |
6 |
M |
0 |
M |
3 |
0 |
|
|
6 |
0 |
0 |
2 |
5 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
2 |
0 |
2 |
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
1 |
2 |
3 |
6 |
di |
|
|
1 |
M |
0 |
1 |
0 |
0 |
|
|
3 |
0 |
0 |
M |
3 |
0 |
|
|
4 |
0 |
1 |
1 |
0 |
0 |
|
|
6 |
0 |
0 |
2 |
M |
0 |
|
|
dj |
0 |
0 |
1 |
0 |
1 |
Чтобы исключить подциклы, запретим следующие переходы: (4,2).
Поскольку нижняя граница этого подмножества (5,4) меньше, чем подмножества (5*,4*), то ребро (5,4) включаем в маршрут.
Шаг№3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
|
i j |
1 |
2 |
3 |
6 |
di |
|
|
1 |
M |
0(0) |
0(0) |
0(0) |
0 |
|
|
3 |
0(0) |
0(0) |
M |
3 |
0 |
|
|
4 |
0(0) |
M |
0(0) |
0(0) |
0 |
|
|
6 |
0(0) |
0(0) |
1 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
0 |
Наибольшая сумма констант приведения равна (0 + 0) = 0 для ребра (1,2), следовательно, множество разбивается на два подмножества (1,2) и (1*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
|
i j |
1 |
2 |
3 |
6 |
di |
|
|
1 |
M |
M |
0 |
0 |
0 |
|
|
3 |
0 |
0 |
M |
3 |
0 |
|
|
4 |
0 |
M |
0 |
0 |
0 |
|
|
6 |
0 |
0 |
1 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
0 |
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
1 |
3 |
6 |
di |
|
|
3 |
0 |
M |
3 |
0 |
|
|
4 |
0 |
0 |
0 |
0 |
|
|
6 |
0 |
1 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
Чтобы исключить подциклы, запретим следующие переходы: (4,2), (4,1),
Поскольку нижняя граница этого подмножества (1,2) меньше, чем подмножества (1*,2*), то ребро (1,2) включаем в маршрут.
Шаг№4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
|
i j |
1 |
3 |
6 |
di |
|
|
3 |
0(3) |
M |
3 |
3 |
|
|
4 |
M |
0(1) |
0(3) |
0 |
|
|
6 |
0(1) |
1 |
M |
1 |
|
|
dj |
0 |
1 |
3 |
0 |
Наибольшая сумма констант приведения равна (3 + 0) = 3 для ребра (3,1), следовательно, множество разбивается на два подмножества (3,1) и (3*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
|
i j |
1 |
3 |
6 |
di |
|
|
3 |
M |
M |
3 |
3 |
|
|
4 |
M |
0 |
0 |
0 |
|
|
6 |
0 |
1 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
3 |
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
3 |
6 |
di |
|
|
4 |
0 |
0 |
0 |
|
|
6 |
1 |
M |
1 |
|
|
dj |
0 |
0 |
1 |
Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*,1*), то ребро (3,1) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,6) и (6,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(2,5), (5,4), (4,6), (6,3), (3,1), (1,2)
Длина маршрута равна F(Mk) = 13
Размещено на Allbest.ru
...Подобные документы
Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа [253,0 K], добавлен 07.06.2011Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.
курсовая работа [541,3 K], добавлен 08.10.2015Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача [53,0 K], добавлен 24.07.2009Основные операции над матрицами и их свойства. Произведение матриц или перемножение матриц. Блочные матрицы. Понятие определителя. Панель инструментов Матрицы. Транспонирование. Умножение. Определитель квадратной матрицы. Модуль вектора.
реферат [109,2 K], добавлен 06.04.2003Линейные операции над матрицами. Умножение и вычисление произведения матриц. Приведение матрицы к ступенчатому виду и вычисление ранга матрицы. Вычисление обратной матрицы и определителя матрицы, а также решение систем линейных уравнений методом Гаусса.
учебное пособие [658,4 K], добавлен 26.01.2009Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.
контрольная работа [551,9 K], добавлен 27.08.2009Оптимальная настройка параметров "алгоритма отжига" при решении задачи коммивояжера. Влияние начальной температуры, числа поворотов при одной температуре и коэффициента N на результат. Сравнение и определение лучшей функции для расчётов задачи.
контрольная работа [329,9 K], добавлен 20.11.2011Предмет и задачи исследования операций. Основные понятия и принципы исследований, математические модели. Детерминированная задача согласования по определению минимального времени выполнения комплекса работ, времени начала и окончания каждой операции.
курсовая работа [233,9 K], добавлен 20.11.2012Решение задачи Коши для дифференциального уравнения. Погрешность приближенных решений. Функция, реализующая явный метод Эйлера. Вычисление погрешности по правилу Рунге. Решение дифференциальных уравнений второго порядка. Условие устойчивости для матрицы.
контрольная работа [177,1 K], добавлен 13.06.2012Нахождение полинома Жегалкина методом неопределенных коэффициентов. Практическое применение жадного алгоритма. Венгерский метод решения задачи коммивояжера. Применение теории нечетких множеств для решения экономических задач в условиях неопределённости.
курсовая работа [644,4 K], добавлен 16.05.2010Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа [23,5 K], добавлен 12.06.2011Структура текстовой задачи. Условия и требования задач и отношения между ними. Методы и способы решения задач. Основные этапы решения задач. Поиск и составление плана решения. Осуществление плана решения. Моделирование в процессе решения задачи.
презентация [247,7 K], добавлен 20.02.2015Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Описание метода потенциалов Математическая постановка задачи об оптимальных перевозках. Метод решения задачи об оптимальных перевозках средствами Ms Excel. Постановка параметрической транспортной задачи, ее математическое и компьютерное моделирование.
курсовая работа [802,5 K], добавлен 21.10.2014Графический и симплексный методы решения ОЗЛП. Построение функции цели, образующая совместно с системой ограничений математическую модель экономической задачи. Нахождение неотрицательного решения системы линейных уравнений. Решение транспортной задачи.
лабораторная работа [322,9 K], добавлен 10.04.2009О происхождении задачи удвоения куба (одной из пяти знаменитых задач древности). Первая известная попытка решения задачи, решение Архита Тарентского. Решение задачи в Древней Греции после Архита. Решения с помощью конических сечений Менехма и Эратосфена.
реферат [630,3 K], добавлен 13.04.2014Геометрическая формулировка задачи распознавания: построение поверхности, которая разделяет множества, соответствующие в пространстве признакам различных классов объектов. Основные понятия и определения. Непараметрические парзеновские оценки плотностей.
курсовая работа [272,7 K], добавлен 10.04.2011
