РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум достигается.
Когда имеется та или иная дополнительная информация о множестве, решение этой задачи иногда удается осуществить без полного перебора элементов всего множества M. Но чаще всего полный перебор производить приходится. В этом случае обязательно возникает задача, как лучше перебор организовать.
Метод ветвей и границ - это один из методов организации полного перебора. Он применим не всегда, а только тогда, когда выполняются специфические дополнительные условия на множество M и минимизируемую на нем функцию. А именно, - предположим, что имеется вещественно-значная функция на множестве подмножеств множества M со следующими двумя свойствами:
- 1)для (здесь - множество, состоящее из единственного элемента ); 2) если и, то.
В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:
- - разобьем множество M на части (любым способом) и выберем ту из его частей 1, на которой функция минимальна; - затем разобьем на несколько частей множество 1 и выберем ту из его частей 2, на которой минимальна функция ; - затем разобьем 2 на несколько частей и выберем ту из них, где минимальна, и так далее, пока не придем к какому-либо одноэлементному множеству.
Это одноэлементное множество называется рекордом. Функция, которой мы при этом выборе пользуемся, называется оценочной. Очевидно, что рекорд не обязан доставлять минимум функции f; однако, вот какая возможность возникает сократить перебор при благоприятных обстоятельствах.
Описанный выше процесс построения рекорда состоял из последовательных этапов, на каждом из которых фиксировалось несколько множеств и выбиралось затем одно из них. Пусть - подмножества множества M, возникшие на предпоследнем этапе построения рекорда, и пусть множество оказалось выбранным с помощью оценочной функции. Именно при разбиении и возник рекорд, который сейчас для определенности обозначим через. Согласно сказанному выше, , ; кроме того, по определению оценочной функции, .
Предположим, что ; тогда для любого элемента m множества M, принадлежащего множеству, будут верны неравенства ; это значит, что при полном переборе элементов из M элементы из уже вообще не надо рассматривать. Если же неравенство не будет выполнено, то все элементы из надо последовательно сравнить с найденным рекордом и как только отыщется элемент, дающий меньшее значение оптимизируемой функции, надо им заменить ре-корд и продолжить перебор. Последнее действие называется улучшением рекорда.
Слова метод ветвей и границ связаны с естественной графической интерпретацией всего изложенного: строится многоуровневое дерево, на нижнем этаже которого располагаются элементы множества M, на котором ветви ведут к рекорду и его улучшениям и на котором часть ветвей остаются "оборванными", потому что их развитие оказалось нецелесообразным.
Мы рассмотрим сейчас первый из двух запланированных в этом курсе примеров применения метода ветвей и границ - решение задачи о коммивояжере. Вот ее формулировка: "Имеется несколько городов, соединенных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по которому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат ("обход коммивояжера"), и, если таковой путь имеется, установить кратчайший из таких путей".
Формализуем условие в терминах теории графов. Города будут вершинами графа, а дороги между городами - ориентированными (направленными) ребрами графа, на каждом из которых задана весовая функция: вес ребра - это длина соответствующей дороги. Путь, который требуется найти, это - ориентированный остовный простой цикл минимального веса в орграфе (напомним: цикл называется остовным, если он проходит по всем вершинам графа; цикл называется простым, если он проходит по каждой своей вершине только один раз; цикл называется ориентированным, если начало каждого последующего ребра совпадает с концом предыдущего; вес цикла - это сумма весов его ребер; наконец, орграф называется полным, если в нем имеются все возможные ребра); такие циклы называются также гамильтоновыми.
Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес, считая, что - это "компьютерная бесконечность", т. е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом можно будет говорить, что в данном, исходном графе "цикла коммивояжера" нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе.
Отсюда следует, что задачу о коммивояжере достаточно решить для полных орграфов с весовой функцией. Сформулируем теперь это в окончательном виде: пусть - полный ориентированный граф и - весовая функция; найти простой остовный ориентированный цикл ("цикл коммивояжера") минимального веса.
Пусть конкретный состав множества вершин и - весовая матрица данного орграфа, т. е. , причем для любого.
Введем некоторые термины. Пусть имеется некоторая числовая матрица. Привести строку этой матрицы означает выделить в строке минимальный элемент (его называют константой приведения) и вычесть его из всех элементов этой строки. Очевидно, в результате в этой строке на месте минимального элемента окажется ноль, а все остальные элементы будут неотрицательными. Аналогичный смысл имеют слова привести столбец матрицы.
Слова привести матрицу по строкам означают, что все строки матрицы приводятся. Аналогичный смысл имеют слова привести матрицу по столбцам.
Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам.
Весом элемента матрицы называют сумму констант приведения матрицы, которая получается из данной матрицы заменой обсуждаемого элемента на. Следовательно, слова самый тяжелый нуль в матрице означают, что в матрице подсчитан вес каждого нуля, а затем фиксирован нуль с максимальным весом.
Приступим теперь к описанию метода ветвей и границ для решения задачи о коммивояжере.
Первый шаг. Фиксируем множество всех обходов коммивояжера (т. е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо непусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через, то сумму констант приведения матрицы весов обозначим через (). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M1; таким образом, итог первого шага: множеству всех обходов коммивояжера сопоставлено число () и матрица M1.
Второй шаг. Выберем в матрице M1 самый тяжелый нуль; пусть он стоит в клетке ; фиксируем ребро графа и разделим множество на две части: на часть, состоящую из обходов, которые проходят через ребро, и на часть, состоящую из обходов, которые не проходят через ребро.
Сопоставим множеству следующую матрицу M1,1: в матрице M1 заменим на число в клетке. Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M1,1; только что запомненную сумму констант приведения прибавим к () и результат, обозначаемый в дальнейшем через (), сопоставим множеству.
Теперь множеству тоже сопоставим некую матрицу M1,2. Для этого в матрице M1 заменим на число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим запомненную сумму констант приведения к числу () и полученное число, обозначаемое в дальнейшем через (), сопоставим множеству.
Теперь выберем между множествами и то, на котором минимальна функция (т. е. то из множеств, которому соответствует меньшее из чисел () и ().
Заметим теперь, что в проведенных рассуждениях использовался в качестве исходного только один фактический объект - приведенная матрица весов данного орграфа. По ней было выделено определенное ребро графа и были построены новые матрицы, к которым, конечно, можно все то же самое применить. При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра.
К выбранному множеству с сопоставленными ему матрицей и числом повторим все то же самое и так далее, пока это возможно.
Доказывается, что в результате получится множество, состоящее из единственного обхода коммивояжера, вес которого равен очередному значению функции ; таким образом, оказываются выполненными все условия, обсуждавшиеся при описании метода ветвей и границ.
После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.
Похожие статьи
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
Провести комплексное исследование численных методов для задачи решения нелинейных уравнений. 1. Решить нелинейные уравнения А) ; Б) ; В) . 2....
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Определение . Алгебраическим дополнением минора матрицы называется его Дополнительный минор , умноженный на (-1) в степени, равной сумме номеров строк и...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Любое частное решения уравнения (1) на координатной плоскости х0у изображено в виде графика функции у=у (х, с) (с=const). В теории дифференциальных...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Определители (детерминанты) - Методы решения системы линейных уравнений
Определение. Определителем квадратной матрицы А= называется число, которое может быть вычислено по элементам матрицы по формуле: Det A = , где (1) М1к -...
-
Матрицы и определители - Методы решения системы линейных уравнений
Определение. Матрицей размера mn, где m - число строк, n - число столбцов, называется таблица чисел, расположенных в определенном порядке. Эти числа...
-
Счетные и несчетные множества - Методы решения системы линейных уравнений
Пусть, например, А и В Ї некоторые множества. Тогда их возможные взаимоотношения можно рассмотреть в виде таблицы: Диаграмма Венна Диаграмма Венна...
-
Расчет верхней и нижней границы надежности схемы методом минимальных путей и сечений Как видно из схемы, она не является последовательно-параллельной,...
-
Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
При написании программ численного интегрирования желательно, чтобы для любой функции распределение узлов являлось оптимальным или близким к нему. Однако...
-
Теория: Применяется, как правило, для задач линейного программирования, содержащих не более 2 переменных. Суть геометрического метода сводится к...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
ФУНКЦИИ, Основные понятия - Свойства функций
Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы
Построить опорный план по одному из правил. Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из...
-
ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера
Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута...
-
Любая правильная рациональная дробь P(x)/Q(x) может быть единственным образом представлена в виде суммы простейших рациональных дробей. Для этого прежде...
-
Производной. - Методы решения системы линейных уравнений
Наиболее просто основные теоремы дифференциального исчисления формулируются для гладких функций. [ Править ] Производные и гладкие функции Пусть функция...
-
Свойства операции умножения матриц - Методы решения системы линейных уравнений
1)Умножение матриц не коммутативно, т. е. АВ ВА даже если определены оба произведения. Однако, если для каких - либо матриц соотношение АВ=ВА...
-
Функции и ее свойства - Методы решения системы линейных уравнений
В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую...
-
Ранг матрицы. - Методы решения системы линейных уравнений
Как было сказано Выше , минором матрицы порядка s называется определитель матрицы, образованной из элементов исходной матрицы, находящихся на пересечении...
-
Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f(x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде...
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Частные производные высших порядков - Методы решения системы линейных уравнений
Пусть z=f(x, y). Тогда и - частные производные по переменным х и у. В некоторых случаях существуют снова от этих функций частные производные, называемые...
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера