Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с


Решение задачи о рюкзаке методом обхода дерева поиска



Pdf көрінісі
бет16/151
Дата26.01.2022
өлшемі1,64 Mb.
#24342
түріСеминар
1   ...   12   13   14   15   16   17   18   19   ...   151
Решение задачи о рюкзаке методом обхода дерева поиска 
Рассматриваемая задача о рюкзаке заключается в следующем.  
Пусть заданы натуральное число 
ω и некоторое множество A={a
1

a
2
, … , a
n
} из n натуральных чисел. Найти все подмножества множест-
ва А, если таковые существуют, сумма элементов в которых в точности 
равна 
ω. Такие подмножества будем называть ω-совместимыми
Предполагается,  что  элементы  в  множестве  A  упорядочены  неко-
торым  образом,  так  что  наряду  с  множеством  A  будем  использовать 


 
17 
обозначение вектор A=(a
1
a
2
, … , a
n
), называемый в дальнейшем рюк-
зачным вектором. 
Ниже  предлагается  алгоритм  перечисления 
ω-совместимых  под-
множеств для заданной пары (A,
ω), основанный на выполнении шагов 
двух  типов  для  некоторого  текущего  множества  В:  первый  тип –
 расширение,  если  это  возможно,  построенного  на  данный  момент 
множества В, за счет добавления очередного элемента из рюкзачного 
вектора, и, если условия расширения не выполняются, то второй тип –
 удаление последнего добавленного элемента.  
Шаги расширения и возврата могут быть наглядно представлены с 
помощью дерева поиска, которое строится следующим образом. Вер-
шинам дерева сопоставляются подмножества множества А, а ребрам –
 его элементы. Корню дерева (вершине нулевого яруса) ставится в со-
ответствие само множество А. Пусть построено ярусов дерева поиска. 
Рассмотрим вершину v i-го яруса (i>0), сопоставим ей множество, эле-
менты  которого  могут  быть  использованы  для  построения 
ω-
совместимого  множества  без  нарушения  условия  расширения.  Если 
это множество пусто, то является концевой вершиной, в противном 
случае  ветвям  дерева,  исходящим  из  данной  вершины,  сопоставим 
элементы данного множества. Построение заканчивается, когда на не-
котором ярусе все вершины дерева оказываются концевыми. 
Изложенный  выше  алгоритм  перечисления  всех 
ω-совместимых 
подмножеств  множества  А  можно  представить  в  виде  специальной 
процедуры  обхода  дерева,  которая  состоит  из  двух  операций –
 операции спуска (переход с i-го яруса на i+1), соответствующей рас-
ширению  строящегося  множества,  и  операции  подъема,  соответст-
вующей  шагу  возврата.  Данная  процедура  обеспечивает  левый  обход 
дерева в глубину. Если сумма элементов, сопоставленных ребрам пу-
ти, ведущего от корня к концевой вершине, в точности равна 
ω, то эти 
элементы образуют 
ω-совместимое множество.  


Достарыңызбен бөлісу:
1   ...   12   13   14   15   16   17   18   19   ...   151




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет