Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
Решение задачи о рюкзаке методом обхода дерева поиска
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| Решение задачи о рюкзаке методом обхода дерева поиска
Рассматриваемая задача о рюкзаке заключается в следующем. Пусть заданы натуральное число ω и некоторое множество A={a 1 , a 2 , … , a n } из n натуральных чисел. Найти все подмножества множест- ва А, если таковые существуют, сумма элементов в которых в точности равна ω. Такие подмножества будем называть ω-совместимыми. Предполагается, что элементы в множестве A упорядочены неко- торым образом, так что наряду с множеством A будем использовать 17 обозначение вектор A=(a 1 , a 2 , … , a n ), называемый в дальнейшем рюк- зачным вектором. Ниже предлагается алгоритм перечисления ω-совместимых под- множеств для заданной пары (A, ω), основанный на выполнении шагов двух типов для некоторого текущего множества В: первый тип – расширение, если это возможно, построенного на данный момент множества В, за счет добавления очередного элемента из рюкзачного вектора, и, если условия расширения не выполняются, то второй тип – удаление последнего добавленного элемента. Шаги расширения и возврата могут быть наглядно представлены с помощью дерева поиска, которое строится следующим образом. Вер- шинам дерева сопоставляются подмножества множества А, а ребрам – его элементы. Корню дерева (вершине нулевого яруса) ставится в со- ответствие само множество А. Пусть построено i ярусов дерева поиска. Рассмотрим вершину v i-го яруса (i>0), сопоставим ей множество, эле- менты которого могут быть использованы для построения ω- совместимого множества без нарушения условия расширения. Если это множество пусто, то v является концевой вершиной, в противном случае ветвям дерева, исходящим из данной вершины, сопоставим элементы данного множества. Построение заканчивается, когда на не- котором ярусе все вершины дерева оказываются концевыми. Изложенный выше алгоритм перечисления всех ω-совместимых подмножеств множества А можно представить в виде специальной процедуры обхода дерева, которая состоит из двух операций – операции спуска (переход с i-го яруса на i+1), соответствующей рас- ширению строящегося множества, и операции подъема, соответст- вующей шагу возврата. Данная процедура обеспечивает левый обход дерева в глубину. Если сумма элементов, сопоставленных ребрам пу- ти, ведущего от корня к концевой вершине, в точности равна ω, то эти элементы образуют ω-совместимое множество. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|