非再帰的0/1幅優先探索を使用したナップザックアルゴリズム

Question

ナップサックと呼ばれる興味深い問題が発生しました。あなたはすべて値と体重を持っているアイテムのリストを持っています。次に、合計されたオブジェクトの価値を最大化するアイテムの組み合わせを見つけ、一定の限度内に留まらなければなりません。私はどこか別の検索アルゴリズムを使うことができる検索問題だと見ました。今私はそれを幅優先で実装しようとしています。次のように

BFS用の擬似アルゴリズムはウィキペディアで発見がある：

Breadth-First-Search(Graph, root): 

create empty set S 
create empty queue Q  

root.parent = NIL 
Q.enqueue(root)      

while Q is not empty: 
    current = Q.dequeue() 
    if current is the goal 
     return current 
    for each node n that is adjacent to current: 
     if n is not in S: 
      add n to S 
      n.parent = current 
      Q.enqueue(n) 

私は本当にナップザック問題にこれを適用する方法を理解しようとしてきました。

私が理解する限り、それは木を作ることです。私は一度に1つのレベルの各ノードを展開して探索する必要があります。 BFSの場合、FIFOキューが必要です。選択された各アイテムについて、私は2つの選択肢があります：アイテムを取るかどうか。具体的にはとにかく 、：私は理解していない何を、私の状況では、上記の擬似コードでは、次のとおりです。

• 私は項目を選択すると、私はキューに二回、それを押すととしてそれらのいずれかをマークします1つは使用されていませんか？
• 現在が目標かどうかはどのようにわかりますか？私は葉のノードにいることを意味する探索するノードがもうないときのようなものを仮定します。しかし、葉のノードがたくさんあるので、どのノードを選択するのですか？
• 現在と隣接しているとはどういう意味ですか？リストやアイテムの配列（アイテムにID、重み、値がある）しかない場合、どのアイテムが隣接しているかをどのように知ることができますか？

Answer 1

4種類のアイテムがあるとします。そして、あなたが探しているグラフは、このようなハイパーキューブ（Yury Chebiryakによる画像）です：

ノードでの進数は0のn番目場所の意味で、可能ナップザックのすべてですアイテムnはナップザックにはなく、1はそれを意味するので、例えば0000は空のナップザックを意味し、1001は最初のアイテムと4番目のアイテムを含むナップザックを意味し、以下同様である。

各ステップで現在のノードをキューから削除し、それが目標でない場合は、すでに訪問していない1つずつのアイテムとは異なるすべてのナップザックを見つけることによって隣接ノードを構築します。たとえば、現在のノードが1001の場合は、ノード0001、1101、1011、および1000を作成します。次に、これらのノードをキューに追加します。

最高の解決策ではなく「十分に良い」解決策を探している場合にのみ、目標は意味を持ちます。現在のノードが目標かどうかを確認するには、現在のナップザックの値を計算し、目標値と比較するだけです。

ベストのソリューションをご希望の場合は、グラフ内のすべてのノードを探索する必要があるため、最初の幅広い検索が役に立ちません。 Dynamic programmingまたはbacktracking（これは種類がDepth First Search）検索スペースを縮小できます。

「十分に良い」ソリューションをご希望の場合は、幅優先探索を使用する有効な方法は、FIFO branch-and-boundまたはhill climbing（ランダムナップザックから開始）です。