Метод ветвей и границ - OXFORDST.RU

Метод ветвей и границ

7.3. Метод ветвей и границ

Начало развитию подхода, получившего название метод ветвей и границ, положила работа Ленд и Дойг (1960). Это, скорее, даже не метод, а концепция или процедурная оболочка, на основе которой стали разрабатывать алгоритмы решения целочисленных задач различной природы. Ценность предложенной идеи стала особенно заметна после появления первого точного алгоритма решения задачи коммивояжера, построенного по схеме ветвей и границ (Литтл с соавторами, 1963). Метод можно применять как к полностью, так и частично целочисленным задачам.

Суть идеи схожа с известной шуткой о ловле льва в пустыне: делим пустыню пополам; если льва нет в первой половине, ищем во второй, которую делим пополам и т. д. В отличии от льва оптимум не перемещается, и в этом смысле наша задача легче.

Метод заключается в построении дерева задач, корнем которого является исходная задача, возможно без условия целочисленности (НЗ). Нижележащие задачи порождаются вышележащими так, что их допустимые множества (ДМ) являются непересекающимися подмножествами ДМ вышележащей задачи. Рост дерева происходит за счет перспективных ветвей. Перспективность определяется по оценке критериятерминальной задачи ветвиV ирекордуZ.ОценкаV– это значение критерия, заведомо не хуже оптимального, аZ– достигнутое в процессе решения значение критерия исходной задачи (в качестве начального может приниматься значение, заведомо хуже оптимального). Значит, задача будет порождающей только при условии, что ее оценка лучше рекорда. При этом уровень, на котором находится задача, не имеет значения.

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

(7.9)

Очевидно, что если, например,V22 окажется хуже рекорда илиD22=, правая ветвь обрывается (говорят также, что она прозондирована). Если же оценкаV22 будет лучше Z, производится ветвление: множествоD22 разбивается на 2 подмножества. Решение завершится, когда все ветви будут прозондированы.

Вид оценки зависит от направленности критерия: при максимизации используется верхняя оценка, при минимизации – нижняя. Последующее изложение метода будет относиться к задаче на максимум.

Для алгоритмической реализации схемы ветвей и границ необходимо решить два основополагающих вопроса:

Каким образом разбивать перспективное множество на подмножества;

Как определять верхнюю оценку критерия на рассматриваемом множестве.

Ответы на них зависят от типа задачи (частично или полностью целочисленная, имеет особые свойства или нет, с булевыми или не булевыми переменными). Ниже рассматривается общий случай.

Пусть известен диапазон возможных значений j-й переменной

которая в непрерывном оптимальном решении оказалась нецелочисленной и равной xj * . Тогда целочисленное значение этой переменной может достигаться либо в интервале 0  хj,либо в интервале +1 хjdj, где — целая часть (рис. 7.6).

Это соответствует разбиению непрерывного множестваD н на два непересекающихся подмножества D1 н и D2 н , объединение которых не равно D н . В то же время такое разбиение целочисленного множества удовлетворяет соотношениям (7.9). При этом целочисленные множества, как исходное, так и порожденные, включены в соответствующие непрерывные множества. Следовательно, поиск целочисленного решения на непрерывном множестве даст тот же результат, что и на целочисленном. Легко увидеть, что приведенное выделение подинтервалов по одной переменной приводит к разбиению исходного множества на два подмножества при любом числе переменных.

Теперь перейдем ко второму вопросу. Так как целочисленное множество является подмножеством соответствующего непрерывного, оптимальное значение критерия на непрерывном множестве всегда будет не меньше, чем на целочисленном. Поэтому в качестве верхней оценки V можно брать оптимальное значение критерия L * непрерывной задачи.

Выбор начального значения рекорда зависит от ситуации:

если известно какое-либо целочисленное значение, то рекорд принимается равным критерию в этом решении;

при положительности всех коэффициентов критерия можно взять нулевое значение рекорда;

в иных случаях за начальное значение рекорда берется –М, где М- максимально представимое в компьютере число.

По ходу разбиения формируются порождаемые задачи, которые помещаются в список задач. Первоначальный список содержит только одну задачу – исходную задачу без условий целочисленности. И в последующем список будет содержать только непрерывные задачи.

Таким образом, базовый алгоритм, реализующий метод ветвей и границ, включает следующие шаги.

Задается начальное значение рекорда и в список задач помещается исходная задача без требования целочисленности переменных.

Анализируется список задач: если он пуст, то переход на шаг 6. Иначе выбирается одна из задач с удалением ее из списка.

Выбранная задача решается одним из методов линейного программирования. Если задача неразрешима или оптимальное значение критерия L*Z, ветвь обрывается (задача прозондирована). Переход на шаг 2.

Полученное решение анализируется на целочисленность. Если решение целочисленное, оно фиксируется, рекорду присваивается оптимальное значение критерия решенной непрерывной задачи (Z:=L*), ветвь обрывается и осуществляется переход на шаг 2.

Выбирается одна из переменных, имеющих нецелочисленные значения. По ней производится ветвление: порождаются 2 задачи, одна образуется присоединением к решенной (родительской) задаче условия хj,другая – добавлением к родительской ограничения хj +1. Эти задачи заносятся в список задач. Переход на шаг2.

Вывод результатов (если значение рекорда больше начального, получено оптимальное решение исходной задачи, иначе задача неразрешима).

Приведенный алгоритм является базовым, так как не включает однозначных правил выбора задачи из списка и ветвящей переменной. Для частично целочисленных задач при выборе переменной для ветвления исключаются непрерывные переменные.

Пример 7.3. Применим алгоритм ветвей и границ к задаче

L=9x1+5x2 max;

xj0 ,целые.

Отбрасывая условие цедочисленности, получаем непрерывную задачу, которую помещаем в список задач. Так как коэффициенты критерия положительны, начальное значение рекорда принимаем равным нулю. Берем из списка единственную задачу и решаем ее. Получаем оптимальное решение в вершине А (рис. 7.7):x1 * =4,72; x2 * =2,19 . Ветвление производим по переменнойx1. Добавляя к решенной задаче ограничение x14, образуем задачу 2, а добавление x15 дает задачу 3. Допустимые множества новых задач покзаны на рис. 7.7. Эти задачи помещаем в список задач. Решение задачи 2 достигается в точке В, а задачи 3 – в С. Весь ход решения исходной задачи представлен в виде дерева решений на рис. 7.10. Порядок решения задач из списка отражает счетчик итераций k. На 3-й итерации (задача 4) получено целочисленное решение со значением критерия 41 (точка D нарис. 7.8). Поэтому изменяется рекорд: Z=41.Задача 6 имеет нецелочисленное решение (вершина Е на рис. 7.9), задача 8 – целочисленное решение в точкеF. В результате после 7-й итерации рекорд становится равным 50.

Остальные задачи не имеют допустимых решений, то есть список задач исчерпывается и, таким образом, констатируем получение оптимального решения исходной задачи, равное решению непрерывной задачи 8.

Из приведенного дерева решений видно, что число задач в списке могло быть меньше при другом порядке решения задач. Действительно, если бы сначала были решены задачи правой ветви с рекордом Z=50, то после решения задачи 2 не произошло бы ветвления, так как верхняя оценка оказалась бы ниже рекорда (V=L * =45,17 6 / 9 6 7 8 9 > Следующая > >>

Читайте также  Общечеловеческие ценности иллюзия и реальность

Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.

МЕТОД ВЕТВЕЙ И ГРАНИЦ

Метод ветвей и границ относится к группе комбинаторных методов дискретного программирования и является одним из наиболее распространенных методов этой группы. Центральную идею комбинаторных методов составляет замена полного перебора допустимого множества X частичным перебором.

На практическом занятии рассматривается метод ветвей и границ для задачи целочисленного линейного программирования (ЛП) следующего вида:

f (x) = X Cj-xj ^ max , j=1

xj — целые, j = 1, n.

Допустимое множество Х данной задачи предполагается ограниченным.

В данном случае на каждом этапе (шаге) решаются непрерывные задачи ЛП: на предварительном (нулевом) этапе — задача L0; на k-м, k = 1, 2. этапе — задачи L2k-1 и L2k. Задача L0 , как и в методе отсечений, представляет собой исходную задачу без учета требования целочисленности; задача Lv, v = 1,2. получается в результате добавления к задаче L0 дополнительных ограничений.

Верхняя граница (оценка) целевой функции f для задачи

Lv, v = 0,1 Д. определяется следующим образом:

где x ‘ — решение задачи Lv .

Если задача Lv не имеет решения, то полагается B,v = .

В процессе решения строится дерево задач, в котором v -я, v = 0,1,2. вершина соответствует задаче Lv . Обозначим через I множество вершин, из которых возможно ветвление. Для ветвления на k-м, k =1,2. этапе выбирается v-я, veI, вершина (задача Lv ), которая имеет максимальную верхнюю оценку E,v.

Пусть в решении x(v) некоторая компонента x(v), 1 [xrv)] +1, где [a] — целая часть действительного числа а.

В результате задача Lv разветвляется (разбивается) на две не связанные между собой задачи L2k-1 и L2k. Задача L2k-1 представляет собой задачу Lv с дополнительным ограничением xr [xv)] +1, т.е.

Для ускорения процесса решения вводится нижняя граница целевой функции f для целочисленного решения, обозначаемая

0. После решения задачи Lv значение 0v определяется следующим образом:

0v- , если задача Lv не имеет решения либо x

не является целочисленным; max <0v"7, 0 , x2 >0 , x1, x2 — целые.

Предварительный (нулевой) этап

Записываем задачу L0 (исходная задача без учета требования целочисленности):

f (x) = 2×1 + 3×2 ^ max , 5×1 + 7×2 0, x2 > 0.

Этой задаче соответствует нулевая вершина дерева задач (см. ниже рис. 11.6).

Решаем графически задачу L0 (рис. 11.1).

‘1 2 3 4 5 6 7ЧХч9

Из рис. 1 1 .1 следует, что задача L0 имеет решение x Точка x(0) является решением системы уравнений

(5×1 + 7 x2 = 35 , 4×1 + 9×2 = 36 . Находим x(0) и 3 ; составляем задачи L1 и L2 : L 2

x 2 0, 0 0, x2 > 3.

Этой задаче соответствует вторая вершина дерева задач (см. ниже рис. 11.6).

Решаем графически задачу L2 (рис. 11.3). ‘1 234567X9

Из рис. 11.3 следует, что задача L2 имеет решение x . Точка x(2) является решением системы уравнений

Г 4 x1 + 9 x 2 = 36,

4 x1 + 9 • 3 = 36 ^ 4 x1 = 9 ^ x1 = 2-4;

В2 = f(x(2)) = 2 • 2- + 3 • 3 = 13-.

Поскольку x(2) не является целочисленным, то полагаем

Просматриваем вершины из I = <1, 2>.? Поскольку Е1 = 14-j >02 =, то не прекращаем ветвление из 1-й вершины. Таким образом, I = <1, 2>.

Поскольку >2 = 13-2 >02 , то не прекращаем ветвление из 2-й вершины. Таким образом, I = <1, 2>.

Проверяем условие окончания вычислений. Поскольку IФ 0, то выполняем 2-й этап.

Выбираем для ветвления 1-ю вершину, поскольку выполняется условие

Выбираем нецелочисленную компоненту xj1-* = 4-5; осу-ществляем ветвление по переменной x1: x1 5 ; составляем задачи L3 и L4:

Записываем задачу L3:

f (x) = 2×1 + 3×2 ^ max ,

5×1 + 7×2 5, 0 04 = 14, то не прекращаем ветвление из 4-й вершины. Таким образом, I = <4>.

Проверяем условие окончания вычислений. Поскольку I Ф0, то выполняем 3-й этап.

На 3-м этапе следует осуществлять ветвление из вершины

4, которой соответствует оптимальное значение f (x(4)) = 14 7.

Несмотря на то, что полученное значение f превышает нижнюю границу целевой функции для целочисленного решения 04 = 14, дальнейшее ветвление из вершины 4 не позволяет улучшить нижнюю границу 0, поскольку f (x(4)) -04

Написанием алгоритма о рюкзаке, используя метод ветвей и границ

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

  1. Разбиваем текущую задачу на подзадачи.
  2. Для каждой подзадачи выполняем оценку минимального и максимального значения нашей функции. 2.1. Если оценка снизу лучше текущего рекорда, то она становится новым рекордом. 2.2. Если оценка сверху хуже текущего рекорда, то отбрасываем эту подзадачу.
  3. Выбираем из нерешённых подзадач самую перспективную. 3.1. Если нерешённых подзадач не осталось, то рекорд — это решение. (goto 5)
  4. Решаем выбранную подзадачу (goto 1)
  5. Ура!

Будьте добры помогите с наброском кода и объясните псевдокод.

1 ответ 1

Основой любого алгоритма, построенного по стратегии Ветвей и Границ является древовидный полный перебор. То есть «скелетом» данной стратегии является банальный рекурсивный просмотр всех возможных вариантов наполнения рюкзака. На каждом уровне рекурсии одна рекурсивная подветка соответствует варианту «берем следующий предмет» (если позволяет остаточная емкость рюкзака), вторая рекурсивная подветка соответствует варианту «не берем следующий предмет». Это и есть наши подзадачи. Это и есть Ветви.

Каждая листовая вершина нашего дерева перебора будет соответствовать какому-то варианту наполнения рюкзака и все такие варианты будут перебраны данной стратегией. Если реализовать все это буквально, то мы, перебрав и сравнив все возможные варианты, найдем точное решение нашей задачи. В каком порядке просматриваются предметы значения не имеет, так как в конечном итоге мы все равно переберем все возможные варианты.

Например, вот так может выглядеть решение (С++), выполненное через полный перебор

(Все это можно сделать и компактнее, но я заранее закладываю задел на будущие модификации под метод Ветвей и Границ.)

На таком входе, как видите, полный перебор выполнит рассмотрение 57 вариантов.

Идея Границ в стратегии Ветвей и Границ сводится к тому, что мы должны уметь относительно недорого заранее предсказывать наиболее оптимистичный вариант решения для каждой рекурсивной подветви, не проводя полного анализа этой подветви. Если этот наиболее оптимистичный вариант заведомо хуже уже имеющихся у нас на данный момент вариантов решения, то тратить усилия на просмотр такой подветки нет никакого смысла.

В данном случае (задача на максимизацию) требуется, чтобы это предсказание давало нам приблизительную оценку сверху для наилучшего потенциального решения, которое можно извлечь из рекурсивной подветви. Чем точнее будет эта оценка сверху, тем лучше (но надо найти оптимальный баланс между точностью оценки и трудоемкостью ее получения). Главное только, чтобы это была именно оценка сверху, т.е. она должна быть заведомо не меньше наилучшего решения для данной рекурсивной ветви.

Если у нас есть достаточно быстрый и дешевый способ построения такой оценки, мы будем использовать его для отсечения бесперспективных ветвей в переборе. Действуя по обычной переборной стратегии, в каждый момент времени мы имеем текущее лучшее решение, называемое рекордным решением. В процессе поиска других решений, спускаясь по нашему дереву перебора, мы будем использовать выбранный метод оценки сверху для оценки потенциального решения в очередной рекурсивной подветви. Если эта оценка говорит нам, что побить нынешний рекорд в данной подветви у нас нет никаких шансов, то продолжать просмотр данной рекурсивной ветви нет никакого смысла.

Читайте также  Европейский Север России

В классическом методе Ветвей и Границ для решения задачи максимизации оценка снизу не нужна. Нужна только оценка сверху. Однако если у вас есть возможность без лишних усилий получить еще и оценку снизу, то ее действительно можно применять для раннего задания значения рекорда (еще до построения первых завершенных решений), тем самым повышая шансы на то, что оценка сверху позволит нам отсеивать бесперспективные ветки на более ранней стадии. Но, еще раз, оценка снизу в задаче максимизации — не обязательна.

Для дискретной задачи о рюкзаке традиционным способом вычисления оценки сверху является «жадный» алгоритм для решения дробной задачи о рюкзаке (под «дробной задачей» имеется я виду возможность брать предметы лишь частично). Такая задача решается тривиально: в рюкзак надо класть предметы в порядке убывания их стоимости на единицу веса. Последний предмет, возможно, поместится в рюкзак лишь частично. Стоимость такого «жадно» заполненного рюкзака — это и есть оценка сверху для решения исходной дискретной задачи.

Вот тот же самый код, на том же самом входе, но теперь с реализацией метода Ветвей и Границ

В этом варианте кода я заранее сортирую входной набор предметов в порядке убывания их стоимости на единицу веса. Это позволяет тривиальным образом реализовать функцию вычисления оценки сверху find_best_greedily . Это также, возможно, накладывает свой (положительный) отпечаток на порядок формирования решений в процессе перебора, т.е. мы стараемся как можно раньше положить в наш рюкзак наиболее эффективные заполнители.

Как видите, этот вариант проверяет только 16 листовых вариантов, а в остальных случаях поддеревья рекурсивных вызовов «отвергаются» на ранних стадиях как бесперспективные на основе вычисленной предварительной оценки сверху.

Вышеприведенного уже достаточно для того, чтобы получить алгоритм по стратегии Ветвей и Границ. Дополнительной модификацией данной стратегии является приоритизация рекурсивных подветвей на основе вычисленной оценки сверху, т.е. обработка в процессе рекурсивного перебора в первую очередь именно той подветви, которая дает более высокую оценку и, поэтому, выглядит более перспективной. Такая подветвь имеет лучшие шансы улучшить наш рекорд как можно раньше и тем самым дать нам возможность раньше отказаться от обработки второй подветви перебора.

В том же примере кода прямая модификация функции find_best для реализации этой стратегии может выглядеть так

В этом варианте проверяется только 2 листовых варианта, т.е. бесперспективные поддеревья рекурсивных вызовов «отвергаются» на еще более ранних стадиях.

В пункте 2 я несколько схитрил, так как в процессе рекурсивного просмотра сначала проверяю вариант «не брать очередной предмет», а затем вариант «брать очередной предмет». Интуитивно кажется, что разумнее было бы сначала проверять вариант «брать очередной предмет», т.к. мы стараемся именно максимизировать наполнение рюкзака. Это должно дать нам возможность раньше находить качественные рекордные решения и тем самым усиливать отсев бесперспективных ветвей перебора. Действительно, если в варианте 2 поменять местами рекурсивные ветки, то реализация найдет оптимальное решение, просмотрев всего 2 листовых варианта, т.е. не больше чем в варианте 3. То есть на этом примере приоритизация ветвей из варианта 3 ничего на самом деле не дает. Наверное существуют входы, на которых приоритизация из шага 3 должна давать положительный эффект, но возможно что эта овчинка и не стоит выделки.

Также, в примерах выше я взял слишком большой размер рюкзака — 1500, что приводит к тому, что в рюкзак помещается «почти все». Возможно, более интересное поведение алгоритма получится наблюдать на рюкзаках меньшего размера. 900 выглядит интересно.

Метод ветвей и границ

б) Метод ветвей и границ

Комплексный подход по схеме ветвлений объединяет целый ряд близких комбинаторных методов, как-то: метод ветвей и границ, метод последовательного конструирования, анализа и отсева вариантов и др. Общая идея метода крайне проста. Множество допустимых планов некоторым способом разбивается на подмножество. В свою очередь каждое из подмножеств по этому же или другому способу снова разбиваются на подмножества до тех пор, пока каждое подмножество не будет представлять собой точку в многомерном пространстве. В силу конечности наборов значений переменных дерево подмножеств (схема ветвлений) конечно.

Построение схемы ветвления есть не что иное, как формирование процедуры перебора. Перебор может осуществляться различными способами. Сечение исходной допустимой области G гиперплоскостью на части G11 и G12. С последующим разделением G11 на G21 и G22 (рис. 18-8) представляет собой построение дерева ветвлений с соответствующими подмножествами, как это показано на рис. 18-9.


Рис. 18-8. Пояснение к методу ветвей и границ


Рис. 1809. Граф решения для метода ветвей и границ

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

Понятно, что выбор оценок и схемы ветвления взаимосвязаны и трудно указать общие рекомендации по использованию на практике этого метода.

Схема ветвления иллюстрируется решением обобщенной задачи одномерного раскроя (пример 18-5) с конкретными числовыми данными.

Пример 18-5. Имеются заготовки длиной я1 = 18, а2 = 16, а3 = 13. Разрезая их на части, но не склеивая, можно получать детали длиной b1 = 12, b2 = 10, b3 = 8, b4 = 6, b5 = 5, b6 = 4. Стоимость каждой детали известна и в условных единицах численно равна их длине. Перечисленные детали представляют собой «портфель заказов», который желательно обеспечить в первую очередь. В том случае, если это невозможно, максимизируется стоимость получаемых деталей из заданной номенклатуры. Если же портфель заказов обеспечивается, необходимо максимизировать стоимость дополнительной продукции.

Величину будем называть дефицитом. Отрицательность дефицита еще не означает существование варианта раскроя, при положительном дефиците раскрой невозможен. Это свойство может быть использовано для указания перспективности варианта. Так, если заготовка а2 раскраивается на b3 и b5, то независимо от комбинаций остальных отрезков раскрой невыполним, поскольку для оставшихся отрезков дефицит положителен.

Первые этапы приводимой ниже схемы ветвления, использующей комбинаторные отношения подмножеств вариантов, показаны на рис. 18-10. На первом этапе формируются разбиения первой группы отрезков (заготовок) на вторую группу (деталей) независимо от того, какой именно отрезок первой группы разрезается. Количество ветвей первого этапа можно вычислить лишь по рекуррентным соотношениям. Смысл подмножества <1, 2, 3>заключается в том, что один из отрезков первой группы в результате раскроя дает один отрезок второй группы, один из оставшихся отрезков первой группы раскраивается на два отрезка второй группы из числа оставшихся и, наконец, последний отрезок первой группы делится на три части, образуя три отрезка второй группы. На втором этапе формируются все перестановки (с учетом порядка) элементов первого этапа. Скажем, вариант <2, 1, 3>означает, что именно первый элемент первой группы аг разрезается на две части и т. д.

Очередной этап ветвления образуется фиксацией отрезков второй группы при» указанном на предыдущем этапе числе частей, на которое разрезается первый элемент. Другими словамй, формируем сочетания по числу разделений первого элемента первого множества на число элементов второго множества. В дальнейшем фиксируем отрезки второй группы при втором элементе первой группы и, наконец, при оставшемся элементе первой группы получаем конкретные варианты раскроя, всего 447 вариантов. В подробно описанной схеме ветвления в отличие от часто применяемых ни на одном этапе не используется конкретный числовой материал. Рекомендуется построить для этого же примера иную схему ветвления, начиная с третьего этапа, по следующему признаку: отрезки второй группы фиксируются при элементе первой группы, разрезаемом на меньшее число частей. Затем надо сравнить схемы. Нетрудно убедиться, что на каждом этапе ветвление осуществляется по регулярной процедуре, что позволяет запоминать лишь один вариант. Сравнение дефицитов предыдущего и последующего вариантов позволяет выделить перспективный и соответствующую ему ветвь. Окончательный результат имеет вид:

Читайте также  Методика воспитания выносливости


Рис. 18-10. Пояснение к примеру 18-5

Формально задачу можно было бы свести к общему виду линейной задачи целочисленного программирования, но такое сведение приведет к значительному увеличению количества переменных и другим трудностям. Матрица коэффициентов при этом приобретает квадратичный вид с неплотным заполнением ее отличными от нуля элементами. Как правило, задачи многоиндексные с большим числом условий и сложной упорядоченностью рекомендуется решать по схеме ветвлений, используя специфику условий и ограничений.

Для задач дискретного типа этот метод получил наибольшее распространение в силу простоты и доступности самого метода и, кроме того, наиболее естественной формы описания систем условий и ограничений, являющихся, как правило, отправным пунктом построения дерева ветвления. По существу большинство оригинальных алгоритмов (Балаша — Фора — Мальгранжа, Черенина, Джеффриона, Хиллиера и др.) являются модификациями метода ветвей и границ с учетом специфики условий задачи [Л. 97].

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

Рубрика: Информационные технологии

Дата публикации: 09.01.2021 2021-01-09

Статья просмотрена: 58 раз

Библиографическое описание:

Клоков, С. А. Метод ветвей и границ для решения задачи о коммивояжёре / С. А. Клоков. — Текст : непосредственный // Молодой ученый. — 2021. — № 2 (344). — С. 21-23. — URL: https://moluch.ru/archive/344/77401/ (дата обращения: 17.09.2021).

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

Ключевые слова: минимальный путь, поиск пути, задача о коммивояжёре, метод ветвей и границ, грубый перебор, алгоритм

В современном мире оптимизация алгоритмов является очень важной проблемой, так как системы должны обрабатывать все большие данные за меньшее время. Одной из известных задач является задача коммивояжёра. Цели данной статьи — оптимизировать решение задачи о коммивояжёре с помощью метода ветвей и границ, разработать алгоритм решения для задачи на языке С++, оценить количество переборов при решении задачи стратегией с помощью грубой силы и с разработанным методом.

Формулировка задачи:

Есть N городов, соединённых между собой дорогами. Необходимо проложить между ними кратчайший замкнутый маршрут, проходящий через каждый город только один раз.

Расстояние из города j в город i считается неотрицательным числом: Dji ≥ 0. Часто Dji называют стоимостью ребра, так как дороги можно представить рёбрами, соединяющими города-вершины некоторого графа.

Допускается несимметричность матрицы Dji ≠ Dji. В ещё более общем случае пути между некоторыми городами могут отсутствовать.

Исходные условия можно записать в формате таблицы, где строки — города отправления, столбцы — города прибытия, в ячейках расстояния между ними.

Необходимые поля:

− Массив минимального пути

− Посещенные пути при текущем проходе

− Вес минимального пути

Необходимые методы:

− Начальный метод поиска пути

− Рекурсивный метод построения пути для заданного начала (в качестве параметра)

− Первый минимум массива

− Второй минимум массива

Алгоритм начального метода поиска пути

− Инициализация нижней границы (bound):

− Цикл вызова рекурсивного поиска минимального пути для каждого узла в качестве начальной точки

Алгоритм рекурсивного поиска пути

− Если все пройдено

  • Если есть путь до начальной точки
    • Длина пройденного пути = переданная длина + путь до начальной точки
    • Если длина пути меньше минимальной длины
      • Сохраняем путь и длину в качестве минимальных
  • Завершаем метод

− Иначе проходим по всем путям (i=0..N-1)

  • Если есть путь до не посещенной точки
    • Сохраняем нижнюю границу
    • Идем в узел i
    • Добавляем к текущей длине пути
    • Вычисляем нижнюю границу для текущего пути по формуле выше

− Если текущая длина + граница для текущего пути меньше минимума

  • Рекурсивный вызов следующего уровня (проходим в узел i)
  • Обрезаем узел
  • Очищаем массив посещенных узлов

Расчеты

В ходе тестирования метода ветвей и границ было совершено 30 генераций матриц и использован метод поиска пути для каждой из них. Результаты представлены в таблице 1. При использовании грубого метода использовалось:

(10! вариантов путей) * (10 переходов на 1 путь) = 36 288 000 переходов

Таблица количества переходов

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: