2
클래스 유형 BBNode의 우선 순위 대기열을 구현하려고하지만 예상대로 새 노드를 분류하지 않는 것 같습니다. 가장 작은 큐를 대기열의 헤드 (현재의 작동 방식)보다 오히려 가장 큰 큐에 넣고 싶지만이 작업을 수행하는 방법을 알 수는 없습니다. 여기 내 BBNode 클래스가 있습니다.Java 우선 순위 대기열이 제대로 정렬되지 않음
public class BBNode implements Comparable<BBNode>{
public int level; //level on the tree
public int value; //value up to that node
public int weight; //weight up to that node
public double bound; //bound of that node
//...constructors
public int compareTo(BBNode node){
if(this.bound > node.bound) return -1;
if(this.bound < node.bound) return 1;
return 0;
}
}
그리고 여기에 PQ를 사용합니다.
PriorityQueue<BBNode> pq = new PriorityQueue<BBNode>();
//..other variables
while(pq.peek() != null){
v = pq.poll();
//System.out.println(v.weight + " " + v.value + " " + v.bound);
if(v.bound >= bestVal && v.level < sortedItems.length-1){
//left branch: take the next item
u.level = v.level+1;
u.weight = v.weight + sortedItems[u.level].weight;
u.value = v.value + sortedItems[u.level].value;
u.bound = bound(u);
//System.out.println(u.bound);
if(u.bound > bestVal){
pq.add(u);
System.out.println("adding " + u.bound);
System.out.println("top of pq is " + pq.peek().bound);
}
if(u.weight <= maxWt && u.value > bestVal){
bestVal = u.value;
bestWt = u.weight;
//System.out.println(bestVal + " " + bestWt);
takeList[arrIdx++] = sortedItems[u.level].item+1;
}
//right branch: don't take the next item
u.weight = v.weight;
u.value = v.value;
u.bound = bound(u);
if(u.bound > bestVal){
pq.add(u);
System.out.println("adding " + u.bound);
System.out.println("top of pq is " + pq.peek().bound);
}
}
}
마지막 서식을 죄송합니다. 마지막 괄호는 while 루프에 해당합니다.
또한 비교 방법에서 -1과 1 주위를 전환 해 보았습니다. 또한 비교기를 구현하려고했지만 동일한 결과를 얻었습니다.
어떤 도움에 감사드립니다 :)
귀하의 BBNode가 정확하며 우선 순위 대기열에 그것들을 삽입하면 가장 잘 작동합니다 (가장 큰 바운드가 먼저 발생 함). 그런데 왜 잘못 생각하나요? 삽입 한 값의 일부가 올바르게 삽입되지 않은 것은 무엇입니까? – greedybuddha
'u'를 설정 한 코드 섹션을 추가 할 수 있습니까? – sharakan
인용 된 코드에서 각 반복에서 다른 객체를 가리 키도록 u를 지정하지 않고 u 참조하는 객체의 필드 만 변경합니다. 이것이 실제 코드의 경우라면 오직 하나의 객체 만 추가되고 그 값은 최신 v를 기준으로 변경됩니다. –