Метод ветвей и границ в задаче о коммивояжере.
Заказать уникальную курсовую работу- 2222 страницы
- 6 + 6 источников
- Добавлена 16.05.2011
- Содержание
- Часть работы
- Список литературы
- Вопросы/Ответы
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
Формулировка и некоторые свойства решений задачи коммивояжера
Постановка задачи коммивояжера как задачи на графе
Метод ветвей и границ. Основная схема.
Решение задачи о коммивояжере методом ветвей и границ.
Заключение
Список литературы
Заменяем на ( элемент (1,4) в M1:
1 2 3 4 5 1 ( 4 4 ( 6 2 2 ( 0 1 3 3 3 0 ( 4 0 4 0 5 1 ( 7 5 0 1 3 0 ( Таблица 9
приводим полученную матрицу:
1 2 3 4 5 1 ( 0 0 ( 2 2 2 ( 0 1 3 3 3 0 ( 4 0 4 0 5 1 ( 7 5 0 1 3 0 ( Таблица 10
Получили матрицу M1.2. Сумма констант приведения в этом случае равна 4, так что 14+4=18.
Следовательно, дальше работаем с множеством .
Найдем веса нулей в M1.1 (они указаны в скобках):
1 2 3 5 2 2 ( 0(2) 3 3 3 0(1) ( 0(3) 4 ( 4 0(4) 6 5 0(3) 1 3 ( Таблица 11
Самым тяжелым является нуль в клетке (4,3). Значит рассматривать будем множества и .
Рассмотрим . Снова заменяем на ( числа в клетках с номерами (4,2), (4,5) и (3,1). После этого строку номер 4 и столбец номер 3 следует вычеркнуть, получим:
1 2 5 2 2 ( 3 3 ( 0 0 5 0 1 ( Таблица 12
Приведение этой матрицы:
1 2 5 2 0 ( 1 3 ( 0 0 5 0 1 ( Таблица 1
Оценочная функция для этого случая: =15+2=17.
Теперь запишем матрицу для множества :
1 2 3 5 2 2 ( 0 3 3 3 0 ( 0 4 ( 4 ( 6 5 0 1 3 ( Таблица 14
Результат ее приведения:
1 2 3 5 2 2 ( 0 3 3 3 0 ( 0 4 ( 0 ( 2 5 0 1 3 ( Таблица 15
Оценочная функция: =15+4=19. Следовательно, дальнейшему рассмотрению подлежит .
Найдем веса нулей:
1 2 5 2 0(1) ( 1 3 ( 0(1) 0(1) 5 0(1) 1 ( Таблица 16
Так как вес нулей одинаковый, выбираем любую из соответствующих клеток. Для определенности возьмем (2,1).
Теперь речь пойдет о множествах и .
Для первого множества заменяем в последней матрице элемент с номером (3,2) на (. Вычеркиваем строку номер 2 и столбец номер 1:
2 5 3 ( 0 5 1 ( Таблица 17
Эта матрица после приведения:
2 5 3 ( 0 5 0 ( Таблица 18
Находим значение оценочной функции: =17+1=18.
Повторим это для множества . Запишем матрицу:
1 2 5 2 ( ( 1 3 ( 0 0 5 0 1 ( Таблица 19
После приведения эта матрица выглядит так:
1 2 5 2 ( ( 0 3 ( 0 0 5 0 1 ( Таблица 20
Вычисляем значение оценочной функции: =17+1=18.
Значение оценочных функций для обоих множеств получились равными, это означает, что для дальнейшего рассмотрения подходят оба множества. Выберем любое из множеств и .
Рассмотрим первый случай, так как там уже получена матрица размером 2(2. Её нулевые клетки дают те ребра, которые дополняют ранее найденные до конечного маршрута коммивояжера. Заметим что вес полученного обхода равен значению оценочной функции - 18.
Найденный таким образом обход : (1,4)(4,3)(2,1)(5,2)(3,5) или 1(4(3(5(2(1.
Легко заметить, что найденный рекорд на самом деле является искомым оптимумом, так как значения оценочной функции на всех оборванных ветвях (на границах) больше или равны весу рекорда.
Если бы в ходе разбиения при равных значениях оценочных функции были выбраны другие множества, можно было получить другой оптимум: 1(4(3(2(5(1.
Заключение
Задачу коммивояжера можно рассматривать как частичный случай Гамильтоновой задаче о круговом путешествии. Суть задачи сводится к нахождению маршрута, при котором коммивояжер должен пройти все города, посетив каждый из них ровно один раз и вернуться в первый город. При этом маршрут должен быть минимизирован относительно некоторой характеристики (километраж, время затраченной на дорогу, расход горючего, стоимость проезда или другие).
Известно несколько методов решения данной задачи: полный перебор возможных маршрутов, “деревянный алгоритм”, алгоритм Крускала, метод ветвей и границ и др. Отличие метода ветвей и границ заключается в том, что оно дает оптимальное решение и позволяет избежать полного перебора, таким образом, сократить ресурсы, затрачиваемые на решение задачи.
Основная идея данного метода состоит в том, что сначала находится множество всех возможных гамильтоновых контуров и нижняя граница весов маршрутов для этого множества. Затем все множество контуров разбивается на две части. Одна часть содержит маршруты, проходящие через некоторое ребро графа(i,j), а другая не содержит это ребро. После чего выбирается то множество, на котором оценочная функция достигает минимума.
Основная задача в практической реализации метода ветвей и границ состоит в нахождении метода определения нижних границ подмножества и в самом разбиении гамильтоновых маршрутов на части. Определение нижних границ основано на утверждении: если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять некоторое число , то задача останется эквивалентной исходной и на оптимальность маршрута это не повлияет.
Список литературы
Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.
Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.
Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».
Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».
Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.
Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.
О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.
Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».
22
1.Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.
2.Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.
3.Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.
4.Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
5.О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».
6.Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».
Вопрос-ответ:
Что такое метод ветвей и границ в задаче о коммивояжере?
Метод ветвей и границ - это алгоритм решения задачи о коммивояжере, который основывается на применении комбинаторных методов поиска оптимального пути. Он позволяет найти наилучшее решение задачи за конечное время.
Какая постановка задачи коммивояжера как задачи на графе?
Задача коммивояжера может быть сформулирована как задача на графе, где города представлены вершинами, а расстояние между ними - ребрами. Задача заключается в нахождении такого пути, который проходит через каждый город ровно один раз и имеет минимальную сумму длин ребер.
Как осуществляется решение задачи о коммивояжере методом ветвей и границ?
Основная схема решения задачи о коммивояжере методом ветвей и границ состоит в последовательном разбиении исходной задачи на подзадачи, каждая из которых решается с применением отсечений и оценки нижней границы. После решения каждой подзадачи происходит переход к следующей ветви. Алгоритм продолжает работу до нахождения оптимального решения.
Какие свойства решений задачи коммивояжера можно отметить?
Решение задачи коммивояжера может иметь следующие свойства: 1) каждый город посещается только один раз; 2) для каждого города определен свой следующий город в пути; 3) пятьлистное окончательное решение должно быть полным, то есть содержать все вершины графа.
Какие результаты дает применение метода ветвей и границ в задаче коммивояжера?
Применение метода ветвей и границ в задаче коммивояжера позволяет найти оптимальное или приближенное решение задачи. Этот метод обеспечивает достаточно точные результаты при разумном времени работы. Однако, при большом количестве городов, метод может иметь высокую вычислительную сложность.
Что такое метод ветвей и границ в задаче о коммивояжере?
Метод ветвей и границ - это метод решения задачи о коммивояжере, который основывается на построении дерева перебора возможных путей и ограничении этого перебора с помощью верхней и нижней границы.
Какая постановка задачи коммивояжера используется при применении метода ветвей и границ?
Задача коммивояжера формулируется как задача на графе, где необходимо найти минимальный замкнутый путь, проходящий через все вершины и возвращающийся в начальную вершину.
Как работает основная схема метода ветвей и границ в решении задачи о коммивояжере?
Основная схема метода ветвей и границ включает в себя построение дерева перебора возможных путей, вычисление верхней и нижней оценки для каждого пути, отсечение путей с верхней оценкой выше текущего наилучшего пути, и повторение этого процесса до нахождения оптимального пути.
Как происходит решение задачи о коммивояжере методом ветвей и границ?
Решение задачи о коммивояжере методом ветвей и границ включает в себя построение дерева перебора возможных путей, вычисление верхней и нижней оценки для каждого пути, отсечение путей с верхней оценкой выше текущего наилучшего пути, и повторение этого процесса до нахождения оптимального пути.
Как можно привести матрицу к виду, подходящему для применения метода ветвей и границ?
Матрицу можно привести к виду, подходящему для применения метода ветвей и границ, путем замены элемента 1 4 в M1 на 0 0 2 2 2 и замены элемента 2 6 в M1 на 0 1 3 3 3 0.
Какая основная схема метода ветвей и границ?
Основная схема метода ветвей и границ включает в себя поиск оценочной верхней и нижней границы по всем возможным ветвлениям, выбор наиболее оптимального варианта ветвления и повторение алгоритма для найденного подмножества задачи.