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

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

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 выглядит интересно.

Известная как минимум с 19 века задача коммивояжера имеет множество способов решения и неоднократно описана. Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.

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

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

Алгоритм Литтла является частным случаем МВиГ, т.е. в худшем случае его сложность равна сложности полного перебора. Теоретическое описание выглядит следующим образом:

Имеется множетво S всех гамильтоновых циклов рафа. На каждом шаге в S ищется ребро (i, j), исключение которого из маршрута максимально увеличит оценку снизу. Далее происходит разбиение множества на два непересекающихся S1 и S2. S1 — все циклы, содержащие ребро (i, j) и не содержащие (j, i). S2 — все циклы, не содержащие (i, j). Далее вычисляется оценка снизу для длины пути каждого множества и, если она превышает длину уже найденного решения, множество отбрасывается. Если нет — множества S1 и S2 обрабатываются так же, как и S.

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

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

Стоит оговориться, что нужно вести учет двух видов бесконечностей — одна добавляется после удаления строки и столбца из матрицы, чтобы не возникало преждевременных циклов, другая — при отбрасывании ребер. Случаи будут рассмотрены чуть позже. Первую бесконечность обозначим как inf1, вторую — inf2. Диагональ заполнена inf1.

1. Из каждого элемента каждой строки вычитается минимальный элемент данной строки. При этом минимальный элемент строки прибавляется к нижней границе
2. Из каждого столбца аналогично вычитается минимальный элемент и прибавляется к нижней границе.
3. Для каждого нулевого элемента M(i, j) вычисляется коэффициент, равный сумме минимальных элементов строки i и столбца j, исключая сам элемент (i, j). Этот коэффициент показывает, насколько гарантированно увеличится нижняя граница решения, если исключить из него ребро (i, j)
4. Ищется элемент с максимальным коэффициентом. Если их несколько, можно выбрать любой (все равно оставшиеся будут рассмотрены на следующих шагах рекурсии)
5. Рассматриваются 2 матрицы — M1 и M2. M1 равна M с удаленными строкой i и столбцом j. В ней находится столбец k и строка l, в которых не содержится inf1 и элемент M(k, l) приравнивается inf1. Как было сказано ранее, это необходимо во избежание преждевременных циклов (т.е. на первых этапах (k, l) == (j, i)). Матрица M1 соответствует множеству, сожержащему ребро (i, j). Вместе с удалением столбца и строки ребро (i, j) включается в путь.
6. M2 равна матрице M, у которой элемент (i, j) равен inf2. Матрица соответствует множетсву путей, не сожержащих ребро (i, j) (важно понимать, что ребро (j, i) при этом не исключается).
7. Переход к п.1 для матриц M1 и M2.

Эвристика состоит в том, что у матрицы M1 нижняя граница не больше, чем у матрицы M2 и в первую очередь рассматривается ветвь, содержащая ребро (i, j).

Пример

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

Так что приведу шаги поиска оптимального пути для этой матрицы.

Реализация

Шаг 1

Получение нулей в каждой строке и каждом столбце.

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

• Решение онлайн
• Видеоинструкция
• Оформление Word