Xreferat.com » Рефераты по математике » Решение задачи коммивояжера методом ветвей и границ

Решение задачи коммивояжера методом ветвей и границ

CELLPADDING=8 CELLSPACING=0> 8

Определим константы приведения для этих матриц


Решение задачи коммивояжера методом ветвей и границ, Решение задачи коммивояжера методом ветвей и границ

Следовательно


Решение задачи коммивояжера методом ветвей и границ, Решение задачи коммивояжера методом ветвей и границ


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


j

i

1 2 4 6
2 03 ∞ 02 8
3 22 022 26 ∞
4 3 00 ∞ 08
5 ∞ 010 10 47

Претендентом к включению в гамильтонов контур станет дуга (3;2). Разбиваем множество Решение задачи коммивояжера методом ветвей и границ на два Решение задачи коммивояжера методом ветвей и границ и Решение задачи коммивояжера методом ветвей и границ.


j

i

1 4 6
2 0 0 8
4 3 ∞ 0
5 ∞ 10 47 10

j

i

1 2 4 6
2 0 ∞ 0 8
3 22 ∞ 26 ∞ 22
4 3 0 ∞ 0
5 ∞ 0 10 47

Очевидно


Решение задачи коммивояжера методом ветвей и границ, Решение задачи коммивояжера методом ветвей и границ


Следовательно, очередному ветвлению нужно подвергнуть подмножество Решение задачи коммивояжера методом ветвей и границ.

Переходим к ветвлению подмножества Решение задачи коммивояжера методом ветвей и границ. Определяем степени нулей. Претендентом на включение в гамильтонов контур является дуга (5;4). Разбиваем множество Решение задачи коммивояжера методом ветвей и границ на два подмножества: Решение задачи коммивояжера методом ветвей и границ и Решение задачи коммивояжера методом ветвей и границ.

Находим нижние границы


Решение задачи коммивояжера методом ветвей и границ, Решение задачи коммивояжера методом ветвей и границ


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

Определим полученный гамильтонов контур. В него вошли дуги


Решение задачи коммивояжера методом ветвей и границ


Длина контура равна


Решение задачи коммивояжера методом ветвей и границ


Так как границы оборванных ветвей больше длины контура 1 – 5 – 4 – 6 – 3 – 2 – 1, то этот контура имеет наименьшую длину.

алгоритм крускал коммивояжер

Решение задачи коммивояжера методом ветвей и границ

Рис.25


Выводы


Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики (расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал.

Существуют несколько методов решения задачи коммивояжера: метод полного перебора, с помощью метода ветвей и границ (алгоритм Литтла), алгоритма Крускала, «деревянного» алгоритма и т.д. Однако только метод ветвей и границ дает нам в итоге самое оптимальное решение.

Основная идея метода Литтла состоит в том, что вначале строят нижнюю границу длин маршрутов для всего множества гамильтоновых контуров Решение задачи коммивояжера методом ветвей и границ. Затем все множество контуров Решение задачи коммивояжера методом ветвей и границ разбивают на два подмножества таким образом, чтобы первое подмножество Решение задачи коммивояжера методом ветвей и границсостояло из гамильтоновых контуров, содержащих некоторую дугу (i,j), а другое подмножество Решение задачи коммивояжера методом ветвей и границ не содержало этой дуги.

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

Используя ЭВМ, методом ветвей и границ можно решить задачи коммивояжера для Решение задачи коммивояжера методом ветвей и границ.

6. Список использованной литературы


1. О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».

2. Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».

3. В. М. Бондарев «Основы программирования» 1998 г., 368 с. изд. дом «Феникс»

Размещено на

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: