비 재귀 0/1 너비 우선 검색을 사용한 배낭 알고리즘

Question

재미있는 문제가있는 배낭이 나타났습니다. 모두 값과 무게가있는 항목 목록이 있습니다. 그런 다음 합계 된 오브젝트의 가치를 최대화하고 특정 한도 내에서 머물러야하는 항목의 조합을 찾아야합니다. 나는 이것이 다른 검색 알고리즘을 사용할 수있는 검색 문제라는 것을 보았다. 이제는 폭 넓게 구현하려고합니다. 정말 노력했다

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) 

는 배낭 문제에 이것을 적용하는 방법을 이해하기 위해 다음과 같이 BFS의 의사 알고리즘은 위키 피 디아에서 발견

이다.

제가 이해하는 한, 나무를 만드는 것입니다. 한 번에 한 레벨의 각 노드를 확장하고 탐색해야합니다. BFS의 경우 FIFO 대기열이 필요합니다. 선택한 각 항목에 대해 두 가지 선택 사항이 있습니다. 항목을 가져갈 지 여부. 어쨌든, 구체적으로 : 나는 위의 의사 코드로, 내 맥락에서 이해하지 못하는 어떤 것이있다 : 나는, 항목을 선택 할 때

• 내가 대기열에 두 번 밀어로 중 하나를 표시 하나는 사용되지 않았습니까?
• 현재 목표가 맞는지 어떻게 알 수 있습니까? 나는 우리가 잎 노드에 있다는 것을 의미하는 탐험 할 노드가 더 이상 없을 때와 같은 것으로 가정합니다. 그러나 많은 잎 노드가있을 것입니다. 그래서 어느 것이 선택합니까?
• 현재와 인접한 것은 무엇을 의미합니까? 목록이나 항목 배열 (항목에 ID, 가중치 및 값이 있음) 만있는 경우 인접한 항목을 어떻게 알 수 있습니까?

Answer 1

4 가지 항목이 있다고 가정 해보십시오. 노드에서

진수는 0 N 번째의 의미와 함께, 가능한 배낭의 모두 : 다음 검색 그래프 이런 하이퍼 큐브는 (Yury Chebiryak 의해 이미지) 인 아이템 n은 배낭에 없으며 1은 의미이므로 예를 들어 0000은 빈 배낭을, 1001은 첫 번째 아이템과 네 번째 아이템을 포함하는 배낭을 의미합니다.

각 단계에서 현재 노드를 대기열에서 제거하고 목표가 아닌 경우 이미 방문한 적이없는 1 개 항목과 다른 모든 배낭을 찾아 인접 노드를 구성합니다 . 예를 들어, 현재 노드가 1001이면 노드 0001, 1101, 1011 및 1000을 구성한 다음이 노드를 대기열에 추가합니다.

최상의 솔루션이 아닌 "충분한"솔루션을 찾고있는 경우에만 의미가 있습니다. 현재 노드가 목표인지 여부를 확인하려면 현재 배낭 값을 계산하여 목표 값과 비교하면됩니다.

최상의 솔루션을 원한다면 그래프의 모든 노드를 탐색해야하므로 너비가 큰 첫 번째 검색이 도움이되지 않습니다. Dynamic programming 또는 backtracking (종류는 Depth First Search) 검색 공간을 줄일 수 있습니다.

"좋은 해결책"을 원한다면, FIFO branch-and-bound 또는 hill climbing (무작위 배낭에서 시작)은 너비 우선 검색을 사용하는 효과적인 방법입니다.