我正在尝试在 Java 中实现分支限界搜索算法。我知道它的概念(它是如何工作的),但我不确定如何实现它。
我在谷歌上找到了一些例子,但它们要复杂得多,我似乎无法理解它们。我想以一种简单的方式实现它。而且他们中的大多数都不在 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?
}
}
}
下面是存储文件信息的Node1类
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
访问数据> 类(存储文件数据的地方),然后程序进入 search
方法(上述方法)传递所有 nodes
、startNode
和节点长度(大小)
。
如果 startNode 与 node1[].getStartNode 中的任何一个相匹配,则将相应的扩展节点存储在 frontierNodes
中,并将其相应的成本存储在优先级队列中的 frontierCosts
中(选择成本最低)。
然后程序 peeks() 优先级队列并选择成本最低的节点(队列前面),然后再次搜索(递归调用上述搜索方法?)并将该特定节点作为 startNode 并继续搜索。
当程序到达新节点时,每个新节点的成本应该得到到目前为止访问的路径的累积成本,程序应该输出路径和成本。
最佳答案
PriorityQueue 需要实现 Comparable 接口(interface)的数据结构,除非您将 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);
}
}
请注意,如果您希望结果是确定的并且成本不是唯一的,您可能还需要使用开始/结束节点作为比较的一部分。
对于您的主要逻辑,有几处不太正确。
- 你的函数参数应该包括它是什么目标节点。
- 您的函数参数应包括您到目前为止使用了多少成本,以便在您想要使用递归函数时可以跟踪它。
- 你的函数应该返回到达节点的最小成本。
- 如果您的图可以有一个循环,请考虑一种机制来确保它不会重新访问它之前访问过的节点。
- 一旦您有了成本可接受的可能解决方案,您就需要将该成本用作上限,以确保如果成本高于迄今为止的最佳解决方案,您将不会继续访问更多节点。<
关于java - 分支 & 绑定(bind)错误 : Node1 cannot be cast to java. lang.Comparable,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30229990/