branch & bound error : Node1 cannot be cast to java.lang.Comparable

Question

我正在尝试在 java 中实现分支限界搜索算法。我知道它的概念（它是如何工作的），但我不确定如何实现它。

我在 google 上找到了一些示例，但它们要复杂得多，我似乎无法理解它们。我想以一种简单的方式实现它。而且他们中的大多数都不在 java.

中

以下是我开始搜索的相关方法（这只是我的代码的一部分）。我认为我的 for 循环需要适当修改以存储边界节点和成本，然后获取成本最低的节点，然后再次执行搜索，直到找到目标节点添加累积成本。
所以我想递归方法最适合这个。但我不确定如何实施。

以下没有给我任何编译错误，但给我运行时间错误 Node1 cannot be cast to java.lang.Comparable。有人会调查这个问题吗？我几个小时以来一直在尝试这样做，但似乎找不到任何解决方案。

另外，任何能指导我正确路径的小代码都会很有帮助。

 public void Search(Node1[] nodes, String startNode, int size){

  List<String> frontierNodes = new ArrayList<String>();
  Queue<Node1> frontierCosts = new PriorityQueue<Node1>();

    for(int i=0; i<size;i++) {

        if(startNode.equals(nodes[i].getStartNode())) { // user enters the startNode and goalNode          

           frontierNodes.add(nodes[i].getEndNode());               
           frontierCosts.add(new Node1(nodes[i].getCost())); 
           frontierCosts.peek();
           System.out.println("Min cost" +frontierCosts.peek());
           int nodesLength = nodes.length - (frontierNodes.size()); 
           i--;
           System.out.println("remaining search nodes length" +nodesLength);

           //Search(nodes, frontierCosts.peek().getEndNode() ,nodesLength); // RECURSIVE CALL?
        } 
    }

}

下面是存放文件信息的Node1class

class Node1 {
   String start, end;
   double cost;

   public Node1(String start, String end, double cost){
       this.start = start;
       this.end = end;
       this.cost = cost;
   }

   public Node1(double cost) { // alternate constructor to store cost in   priority queue
      this.cost = cost;
   }

   public String getStartNode(){
      return start;
   }

   public String getEndNode(){
      return end;
   }

   public double getCost(){
      return cost;
   }
}

以下是文件格式（startNode endNode cost）

A B 10 
A C 12
B D 6
....

[编辑]：

我想实现分支定界搜索，其中程序要求用户输入 startNode 和 goalNode，然后从 Node1 class 访问数据（文件中数据的存储位置）然后程序进入 search 方法（上述方法）传递所有 nodes、startNode 和 length of nodes(size)。如果 startNode 与 node1[].getStartNode 中的任何一个相匹配，那么它会将相应的扩展节点存储在 frontierNodes 中，并将其相应的成本存储在优先队列中的 frontierCosts 中（以选择成本最低的）。然后程序 peeks() 优先队列并选择成本最低的节点（队列前面），然后再次搜索（递归调用上述搜索方法？）并将该特定节点作为 startNode 并继续搜索。
当程序到达新节点时，每个新节点的成本应该得到到目前为止访问的路径的累积成本，程序应该输出路径和成本。

Answer 1

PriorityQueue 需要实现 Comparable 接口的数据结构，除非您将 Comparator 作为 constructor.

传入

更改应该非常简单。

class Node1 implements Comparable<Node1> {
    String start, end;
    double cost;

    public Node1(String start, String end, double cost){
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    public Node1(double cost) { // alternate constructor to store cost in   priority queue
        this.cost = cost;
    }

    public String getStartNode(){
        return start;
    }

    public String getEndNode(){
        return end;
    }

    public double getCost(){
        return cost;
    }

    @Override
    public int compareTo(Node1 o) {
        return Double.compare(this.cost, o.cost);
    }
}

请注意，如果您希望结果是确定的并且成本不是唯一的，您可能还需要使用 start/end 节点作为比较的一部分。

对于您的主要逻辑，有几处不太正确。

你的函数参数应该包括它是什么目标节点。
您的函数参数应包括您到目前为止使用了多少成本，以便在您要使用递归函数时可以跟踪它。
您的函数应该return到达节点的最低成本。
如果你的图可以有一个循环，考虑一种机制来确保它不会重新访问它之前访问过的节点。
一旦您有了成本可接受的可能解决方案，您需要将该成本用作上限，以确保如果成本高于迄今为止的最佳解决方案，您将不会继续访问更多节点。

branch & bound error : Node1 cannot be cast to java.lang.Comparable

branch & bound error : Node1 cannot be cast to java.lang.Comparable

java

algorithm

comparable

comparator

branch-and-bound