#алгоритм
При написании вариантов решения алгоритма задачи о рюкзаке, написал все самые знаменитые
варианты решения: полный перебор, жадный, используя динамическое программирование.
А вот с вариант используя метод ветвей и границ, никак не получается.
Нашел такой псевдокод :
Разбиваем текущую задачу на подзадачи.
Для каждой подзадачи выполняем оценку минимального и максимального значения нашей
функции.
2.1. Если оценка снизу лучше текущего рекорда, то она становится новым рекордом.
2.2. Если оценка сверху хуже текущего рекорда, то отбрасываем эту подзадачу.
Выбираем из нерешённых подзадач самую перспективную.
3.1. Если нерешённых подзадач не осталось, то рекорд - это решение. (goto 5)
Решаем выбранную подзадачу (goto 1)
Ура!
Не пойму его.
Будьте добры помогите с наброском кода и объясните псевдокод.
Заранее благодарен.
Ответы
Ответ 1
Основой любого алгоритма, построенного по стратегии Ветвей и Границ является древовидный полный перебор. То есть "скелетом" данной стратегии является банальный рекурсивный просмотр всех возможных вариантов наполнения рюкзака. На каждом уровне рекурсии одна рекурсивная подветка соответствует варианту "берем следующий предмет" (если позволяет остаточная емкость рюкзака), вторая рекурсивная подветка соответствует варианту "не берем следующий предмет". Это и есть наши подзадачи. Это и есть Ветви. Каждая листовая вершина нашего дерева перебора будет соответствовать какому-то варианту наполнения рюкзака и все такие варианты будут перебраны данной стратегией. Если реализовать все это буквально, то мы, перебрав и сравнив все возможные варианты, найдем точное решение нашей задачи. В каком порядке просматриваются предметы значения не имеет, так как в конечном итоге мы все равно переберем все возможные варианты. Например, вот так может выглядеть решение (С++), выполненное через полный перебор #include#include
#include struct Item { unsigned weight = 0, cost = 0; static Item guardian() { return { std::numeric_limits ::max(), std::numeric_limits ::max() }; } bool is_guardian() const { return weight == std::numeric_limits ::max(); } Item &operator +=(const Item &rhs) { weight += rhs.weight; cost += rhs.cost; return *this; } Item &operator -=(const Item &rhs) { weight -= rhs.weight; cost -= rhs.cost; return *this; } bool is_better_than(const Item &rhs) const { return cost > rhs.cost; } friend std::ostream &operator <<(std::ostream &strm, const Item &item) { strm << "{ w = " << item.weight << ", c = " << item.cost << " }"; return strm; } }; class Items { public: using Container = std::list - ; Items(unsigned max_weight) : max_weight(max_weight) {} Item find_best(Container source) { source.push_back(Item::guardian()); items.clear(); Items current(max_weight); find_best(current, source.begin()); return total; } friend std::ostream &operator <<(std::ostream &strm, const Items &items) { strm << items.total << ": "; for (const Item &item : items.items) strm << item << " "; return strm; } private: Container items; Item total; unsigned max_weight; void pop_back() { Item item = std::move(items.back()); items.pop_back(); total -= item; } bool push_back(Item item) { if (total.weight + item.weight > max_weight) return false; total += item; items.push_back(std::move(item)); return true; } void find_best(Items ¤t, Container::const_iterator it_remaining) { if (it_remaining->is_guardian()) { std::cout << "Leaf: " << current << std::endl; if (current.total.is_better_than(total)) *this = current; return; } find_best(current, std::next(it_remaining)); if (current.push_back(*it_remaining)) { find_best(current, std::next(it_remaining)); current.pop_back(); } } }; int main() { Items backpack(1500); backpack.find_best({ { 200, 40 }, { 314, 50 }, { 198, 100 }, { 500, 60 }, { 300, 30 }, { 400, 45 } }); std::cout << std::endl << "Best: " << backpack << std::endl; } http://coliru.stacked-crooked.com/a/0c1d77a852250ae2 (Все это можно сделать и компактнее, но я заранее закладываю задел на будущие модификации под метод Ветвей и Границ.) На таком входе, как видите, полный перебор выполнит рассмотрение 57 вариантов. Идея Границ в стратегии Ветвей и Границ сводится к тому, что мы должны уметь относительно недорого заранее предсказывать наиболее оптимистичный вариант решения для каждой рекурсивной подветви, не проводя полного анализа этой подветви. Если этот наиболее оптимистичный вариант заведомо хуже уже имеющихся у нас на данный момент вариантов решения, то тратить усилия на просмотр такой подветки нет никакого смысла. В данном случае (задача на максимизацию) требуется, чтобы это предсказание давало нам приблизительную оценку сверху для наилучшего потенциального решения, которое можно извлечь из рекурсивной подветви. Чем точнее будет эта оценка сверху, тем лучше (но надо найти оптимальный баланс между точностью оценки и трудоемкостью ее получения). Главное только, чтобы это была именно оценка сверху, т.е. она должна быть заведомо не меньше наилучшего решения для данной рекурсивной ветви. Если у нас есть достаточно быстрый и дешевый способ построения такой оценки, мы будем использовать его для отсечения бесперспективных ветвей в переборе. Действуя по обычной переборной стратегии, в каждый момент времени мы имеем текущее лучшее решение, называемое рекордным решением. В процессе поиска других решений, спускаясь по нашему дереву перебора, мы будем использовать выбранный метод оценки сверху для оценки потенциального решения в очередной рекурсивной подветви. Если эта оценка говорит нам, что побить нынешний рекорд в данной подветви у нас нет никаких шансов, то продолжать просмотр данной рекурсивной ветви нет никакого смысла. В классическом методе Ветвей и Границ для решения задачи максимизации оценка снизу не нужна. Нужна только оценка сверху. Однако если у вас есть возможность без лишних усилий получить еще и оценку снизу, то ее действительно можно применять для раннего задания значения рекорда (еще до построения первых завершенных решений), тем самым повышая шансы на то, что оценка сверху позволит нам отсеивать бесперспективные ветки на более ранней стадии. Но, еще раз, оценка снизу в задаче максимизации - не обязательна. Для дискретной задачи о рюкзаке традиционным способом вычисления оценки сверху является "жадный" алгоритм для решения дробной задачи о рюкзаке (под "дробной задачей" имеется я виду возможность брать предметы лишь частично). Такая задача решается тривиально: в рюкзак надо класть предметы в порядке убывания их стоимости на единицу веса. Последний предмет, возможно, поместится в рюкзак лишь частично. Стоимость такого "жадно" заполненного рюкзака - это и есть оценка сверху для решения исходной дискретной задачи. Вот тот же самый код, на том же самом входе, но теперь с реализацией метода Ветвей и Границ #include
#include
#include struct Item { unsigned weight = 0, cost = 0; static Item guardian() { return { std::numeric_limits ::max(), std::numeric_limits ::max() }; } bool is_guardian() const { return weight == std::numeric_limits ::max(); } Item partial(unsigned partial_weight) const { return { partial_weight, (cost * partial_weight + weight - 1) / weight }; } Item &operator +=(const Item &rhs) { weight += rhs.weight; cost += rhs.cost; return *this; } Item &operator -=(const Item &rhs) { weight -= rhs.weight; cost -= rhs.cost; return *this; } double unit_cost() const { return (double) cost / weight; } bool is_better_than(const Item &rhs) const { return cost > rhs.cost; } friend std::ostream &operator <<(std::ostream &strm, const Item &item) { strm << "{ w = " << item.weight << ", c = " << item.cost << " }"; return strm; } }; class Items { public: using Container = std::list - ; Items(unsigned max_weight) : max_weight(max_weight) {} Item find_best(Container source) { source.sort([](const Item &lhs, const Item &rhs) { return lhs.unit_cost() > rhs.unit_cost(); }); source.push_back(Item::guardian()); items.clear(); Items current(max_weight); find_best(current, source.begin()); return total; } friend std::ostream &operator <<(std::ostream &strm, const Items &items) { strm << items.total << ": "; for (const Item &item : items.items) strm << item << " "; return strm; } private: Container items; Item total; unsigned max_weight; void pop_back() { Item item = std::move(items.back()); items.pop_back(); total -= item; } bool push_back(Item item) { if (total.weight + item.weight > max_weight) return false; total += item; items.push_back(std::move(item)); return true; } void find_best(Items ¤t, Container::const_iterator it_remaining) { if (it_remaining->is_guardian()) { std::cout << "Leaf: " << current << std::endl; if (current.total.is_better_than(total)) *this = current; return; } Item estimate = find_best_greedily(current, std::next(it_remaining)); if (estimate.is_better_than(total)) find_best(current, std::next(it_remaining)); if (current.push_back(*it_remaining)) { Item estimate = find_best_greedily(current, std::next(it_remaining)); if (estimate.is_better_than(total)) find_best(current, std::next(it_remaining)); current.pop_back(); } } Item find_best_greedily(const Items ¤t, Container::const_iterator it_remaining) { Item total = current.total; for (; !it_remaining->is_guardian(); ++it_remaining) if (total.weight + it_remaining->weight > max_weight) { unsigned remainder = max_weight - total.weight; total += it_remaining->partial(remainder); break; } else total += *it_remaining; return total; } }; int main() { Items backpack(1500); backpack.find_best({ { 200, 40 }, { 314, 50 }, { 198, 100 }, { 500, 60 }, { 300, 30 }, { 400, 45 } }); std::cout << std::endl << "Best: " << backpack << std::endl; } http://coliru.stacked-crooked.com/a/da4f01a170a9be53 В этом варианте кода я заранее сортирую входной набор предметов в порядке убывания их стоимости на единицу веса. Это позволяет тривиальным образом реализовать функцию вычисления оценки сверху find_best_greedily. Это также, возможно, накладывает свой (положительный) отпечаток на порядок формирования решений в процессе перебора, т.е. мы стараемся как можно раньше положить в наш рюкзак наиболее эффективные заполнители. Как видите, этот вариант проверяет только 16 листовых вариантов, а в остальных случаях поддеревья рекурсивных вызовов "отвергаются" на ранних стадиях как бесперспективные на основе вычисленной предварительной оценки сверху. Вышеприведенного уже достаточно для того, чтобы получить алгоритм по стратегии Ветвей и Границ. Дополнительной модификацией данной стратегии является приоритизация рекурсивных подветвей на основе вычисленной оценки сверху, т.е. обработка в процессе рекурсивного перебора в первую очередь именно той подветви, которая дает более высокую оценку и, поэтому, выглядит более перспективной. Такая подветвь имеет лучшие шансы улучшить наш рекорд как можно раньше и тем самым дать нам возможность раньше отказаться от обработки второй подветви перебора. В том же примере кода прямая модификация функции find_best для реализации этой стратегии может выглядеть так void find_best(Items ¤t, Container::const_iterator it_remaining) { if (it_remaining->is_guardian()) { std::cout << "Leaf: " << current << std::endl; if (current.total.is_better_than(total)) *this = current; return; } Item estimate_without = find_best_greedily(current, std::next(it_remaining)); Item estimate_with; if (current.push_back(*it_remaining)) { estimate_with = find_best_greedily(current, std::next(it_remaining)); current.pop_back(); } if (estimate_without.is_better_than(estimate_with)) { if (estimate_without.is_better_than(total)) find_best(current, std::next(it_remaining)); if (estimate_with.is_better_than(total)) { current.push_back(*it_remaining); find_best(current, std::next(it_remaining)); current.pop_back(); } } else { if (estimate_with.is_better_than(total)) { current.push_back(*it_remaining); find_best(current, std::next(it_remaining)); current.pop_back(); } if (estimate_without.is_better_than(total)) find_best(current, std::next(it_remaining)); } } http://coliru.stacked-crooked.com/a/83341a8e18c889e4 В этом варианте проверяется только 2 листовых варианта, т.е. бесперспективные поддеревья рекурсивных вызовов "отвергаются" на еще более ранних стадиях. В пункте 2 я несколько схитрил, так как в процессе рекурсивного просмотра сначала проверяю вариант "не брать очередной предмет", а затем вариант "брать очередной предмет". Интуитивно кажется, что разумнее было бы сначала проверять вариант "брать очередной предмет", т.к. мы стараемся именно максимизировать наполнение рюкзака. Это должно дать нам возможность раньше находить качественные рекордные решения и тем самым усиливать отсев бесперспективных ветвей перебора. Действительно, если в варианте 2 поменять местами рекурсивные ветки, то реализация найдет оптимальное решение, просмотрев всего 2 листовых варианта, т.е. не больше чем в варианте 3. То есть на этом примере приоритизация ветвей из варианта 3 ничего на самом деле не дает. Наверное существуют входы, на которых приоритизация из шага 3 должна давать положительный эффект, но возможно что эта овчинка и не стоит выделки. Также, в примерах выше я взял слишком большой размер рюкзака - 1500, что приводит к тому, что в рюкзак помещается "почти все". Возможно, более интересное поведение алгоритма получится наблюдать на рюкзаках меньшего размера. 900 выглядит интересно.
Комментариев нет:
Отправить комментарий