Задача коммивояжера
Суть задачи сводится к поиску оптимального (кратчайшего, быстрейшего или самого дешевого) пути, проходящего через промежуточный пункты по одному разу и возвращающегося в исходную точку. Дана матрица расстояний. Решение задачи с помощью алгоритма Литтла.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 03.03.2024 |
| Размер файла | 47,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Задача коммивояжера
Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) - задача коммивояжера (англ. "Travelling salesman problem", TSP). Также встречается название "задача о странствующем торговце". Суть задачи сводится к поиску оптимального (кратчайшего, быстрейшего или самого дешевого) пути, проходящего через промежуточный пункты по одному разу и возвращающегося в исходную точку. К примеру, нахождение наиболее выгодного маршрута, позволяющего коммивояжеру посетить со своим товаром определенные города по одному разу и вернуться обратно. Мерой выгодности маршрута может быть минимальное время поездки, минимальные расходы на дорогу или минимальная длина пути. В наше время, когда стоимость доставки часто бывает сопоставима со стоимостью самого товара, а скорость доставки - один из главных приоритетов, задача нахождения оптимального маршрута приобретает огромное значени).
Алгоритм решения
Дана матрица расстояний, представленная в таблице 1. Необходимо с помощью алгоритма Литтла решить задачу коммивояжера.
Табл.1
|
j i |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
? |
7 |
16 |
21 |
2 |
17 |
|
|
2 |
13 |
? |
21 |
15 |
43 |
23 |
|
|
3 |
25 |
3 |
? |
31 |
17 |
9 |
|
|
4 |
13 |
10 |
27 |
? |
33 |
12 |
|
|
5 |
9 |
2 |
19 |
14 |
? |
51 |
|
|
6 |
42 |
17 |
5 |
9 |
23 |
? |
1) Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы Ui из соответствующих элементов строки матрицы.
|
j i |
1 |
2 |
3 |
4 |
5 |
6 |
Ui |
|
|
1 |
? |
7 |
16 |
21 |
2 |
17 |
2 |
|
|
2 |
13 |
? |
21 |
15 |
43 |
23 |
13 |
|
|
3 |
25 |
3 |
? |
31 |
17 |
9 |
3 |
|
|
4 |
13 |
10 |
27 |
? |
33 |
12 |
10 |
|
|
5 |
9 |
2 |
19 |
14 |
? |
51 |
2 |
|
|
6 |
42 |
17 |
5 |
9 |
23 |
? |
5 |
2) Внизу полученной матрицы присоединяем строку Vj, в которой записываем минимальные элементы столбцов. Вычитаем элементы Vj из соответствующих столбцов матрицы.
|
j i |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
? |
5 |
14 |
19 |
0 |
15 |
|
|
2 |
0 |
? |
8 |
2 |
30 |
10 |
|
|
3 |
22 |
0 |
? |
28 |
14 |
6 |
|
|
4 |
3 |
0 |
17 |
? |
23 |
2 |
|
|
5 |
7 |
0 |
17 |
12 |
? |
49 |
|
|
6 |
37 |
12 |
0 |
4 |
18 |
? |
|
|
Vj |
0 |
0 |
0 |
2 |
0 |
2 |
3) В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2.
Табл.2
|
j i |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
? |
5 |
14 |
17 |
019 |
13 |
|
|
2 |
03 |
? |
8 |
02 |
30 |
8 |
|
|
3 |
22 |
04 |
? |
26 |
14 |
4 |
|
|
4 |
3 |
00 |
17 |
? |
23 |
04 |
|
|
5 |
7 |
07 |
17 |
10 |
? |
47 |
|
|
6 |
37 |
12 |
08 |
2 |
18 |
? |
4) Находим константу приведения:
.
Таким образом, нижней границей множества всех гамильтоновых контуров будет число
.
5) Находим степени нулей полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак "?" и устанавливаем сумму минимальных элементов соответствующей строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых .
6) Определяем максимальную степень нуля. Она равна 19 и соответствует клетке (1;5). Таким образом, претендентом на включение в гамильтонов контур является дуга (1;5).
7) Разбиваем множество всех гамильтоновых контуров на два: и . Матрицу с дугой (1;5) получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент (5;1) на знак "?".
|
j i |
1 |
2 |
3 |
4 |
6 |
|
|
2 |
0 |
? |
8 |
0 |
8 |
|
|
3 |
22 |
0 |
? |
26 |
4 |
|
|
4 |
3 |
0 |
17 |
? |
0 |
|
|
5 |
? |
0 |
17 |
10 |
47 |
|
|
6 |
37 |
12 |
0 |
2 |
? |
8) Матрицу гамильтоновых контуров получим из таблицы 2 путем замены элемента (1;5) на знак "?".
|
j i |
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
? |
5 |
14 |
17 |
? |
13 |
5 |
|
|
2 |
0 |
? |
8 |
0 |
30 |
8 |
||
|
3 |
22 |
0 |
? |
26 |
14 |
4 |
||
|
4 |
3 |
0 |
17 |
? |
23 |
0 |
||
|
5 |
7 |
0 |
17 |
10 |
? |
47 |
||
|
6 |
37 |
12 |
0 |
2 |
18 |
? |
||
|
14 |
9) Делаем дополнительное приведение матрицы контуров : = 0. Нижняя граница множества равна .
10) Находим константу приведения для множества контуров
:.
Следовательно, нижняя граница множества равна .
11) Сравниваем нижние границы подмножеств и . Так как
,
то дальнейшему ветвлению подвергаем множество .
На рис.1 представлено ветвление по дуге (1;5).
Рисунок 1- Ветвление по дуге
Далее выполняем все действия как на педыдущих шагах
Ответ
На рис.2 представлено дерево ветвлений. Определим полученный гамильтонов контур. В него вошли дуги . Длина контура равна матрица алгоритм литтл
.
Так как границы оборванных ветвей больше длины контура 1 - 5 - 4 - 6 - 3 - 2 - 1, то этот контура имеет наименьшую длину.
Рисунок 2 - Дерево ветвлений
...Подобные документы
Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.
курсовая работа [541,3 K], добавлен 08.10.2015Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа [253,0 K], добавлен 07.06.2011Оптимальная настройка параметров "алгоритма отжига" при решении задачи коммивояжера. Влияние начальной температуры, числа поворотов при одной температуре и коэффициента N на результат. Сравнение и определение лучшей функции для расчётов задачи.
контрольная работа [329,9 K], добавлен 20.11.2011О происхождении задачи удвоения куба (одной из пяти знаменитых задач древности). Первая известная попытка решения задачи, решение Архита Тарентского. Решение задачи в Древней Греции после Архита. Решения с помощью конических сечений Менехма и Эратосфена.
реферат [630,3 K], добавлен 13.04.2014Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Решение первой задачи, уравнения Пуассона, функция Грина. Краевые задачи для уравнения Лапласа. Постановка краевых задач. Функции Грина для задачи Дирихле: трехмерный и двумерный случай. Решение задачи Неймана с помощью функции Грина, реализация на ЭВМ.
курсовая работа [132,2 K], добавлен 25.11.2011Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008Описание газлифтного процесса с помощью системы дифференциальных уравнений с частными производными гиперболического типа. Конечно-разностная аппроксимация производных функций и решение дискретной линейно-квадратичной задачи оптимального управления.
статья [41,4 K], добавлен 17.10.2012Обоснование выбора оптимального маршрута по критерию минимума времени на его прохождение. Словесная постановка маршрутной задачи. Математическая постановка задачи. Оптимизация маршрута с города Рязановский до города Королева. Оценка его вариантов выбора.
курсовая работа [64,6 K], добавлен 19.12.2009Линейные операции над векторами. Уравнение прямой, проходящей через две точки. Варианты решений систем линейных уравнений. Действия с матрицами. Модель транспортной задачи, ее решение распределительным методом. Исследование функций с помощью производных.
контрольная работа [1,0 M], добавлен 09.10.2011Слабые асимптотики произведения функций Хевисайда. Решение задачи Коши методом прямого интегрирования. Оценка задачи со ступенчатой функцией в качестве начального условия. Предел на бесконечности, получаемый при неограниченном уменьшении малого параметра.
курсовая работа [1,9 M], добавлен 23.09.2016Применение математических и вычислительных методов в планировании перевозок. Понятие и виды транспортных задач, способы их решения. Особенности постановки задачи по критерию времени. Решение транспортной задачи в Excel, настройка параметров решателя.
курсовая работа [1,0 M], добавлен 12.01.2011Математическое моделирование и особенности задачи распределения. Обоснование и выбор метода решения. Ручное решение задачи (венгерский метод), а также с использованием компьютера. Формулировка полученного результата в сопоставлении с условием задачи.
курсовая работа [383,9 K], добавлен 26.05.2010Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Предмет вычислительной техники - задачи, которые умеют решать машины. Измерение сложности задачи. Алгоритм сортировки слиянием. Полиномиальные и не полиномиальные задачи. Понятие недетерменированного алгоритма. Графическое представление классификации.
презентация [277,7 K], добавлен 22.10.2013Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача [53,0 K], добавлен 24.07.2009
