Java 统一成本搜索实施
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20635394/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-08-13 03:15:57 来源:igfitidea点击:
Uniform Cost Search Implementation
提问by Ray.R.Chua
I am trying to implement the Uniform Cost Search after watching the "Intro to AI" course in Udacity. However, my algorithm is not getting the correct path. Have been trying the whole day before posting here. I have added a map to help to visualize the scene. The algorithm should find the shortest weighted path from Arad to Bucharest
在观看了 Udacity 中的“AI 简介”课程后，我正在尝试实施统一成本搜索。但是，我的算法没有得到正确的路径。在这里发帖之前一直在尝试一整天。我添加了一张地图来帮助可视化场景。该算法应该找到从 Arad 到 Bucharest 的最短加权路径
import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Set;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
//diff between uniform cost search and dijkstra algo is that UCS has a goal
public class UniformCostSearchAlgo{
public static void main(String[] args){
//initialize the graph base on the Romania map
Node n1 = new Node("Arad");
Node n2 = new Node("Zerind");
Node n3 = new Node("Oradea");
Node n4 = new Node("Sibiu");
Node n5 = new Node("Fagaras");
Node n6 = new Node("Rimnicu Vilcea");
Node n7 = new Node("Pitesti");
Node n8 = new Node("Timisoara");
Node n9 = new Node("Lugoj");
Node n10 = new Node("Mehadia");
Node n11 = new Node("Drobeta");
Node n12 = new Node("Craiova");
Node n13 = new Node("Bucharest");
Node n14 = new Node("Giurgiu");
//initialize the edges
n1.adjacencies = new Edge[]{
new Edge(n2,75),
new Edge(n4,140),
new Edge(n8,118)
};
n2.adjacencies = new Edge[]{
new Edge(n1,75),
new Edge(n3,71)
};
n3.adjacencies = new Edge[]{
new Edge(n2,71),
new Edge(n4,151)
};
n4.adjacencies = new Edge[]{
new Edge(n1,140),
new Edge(n5,99),
new Edge(n3,151),
new Edge(n6,80),
};
n5.adjacencies = new Edge[]{
new Edge(n4,99),
new Edge(n13,211)
};
n6.adjacencies = new Edge[]{
new Edge(n4,80),
new Edge(n7,97),
new Edge(n12,146)
};
n7.adjacencies = new Edge[]{
new Edge(n6,97),
new Edge(n13,101),
new Edge(n12,138)
};
n8.adjacencies = new Edge[]{
new Edge(n1,118),
new Edge(n9,111)
};
n9.adjacencies = new Edge[]{
new Edge(n8,111),
new Edge(n10,70)
};
n10.adjacencies = new Edge[]{
new Edge(n9,70),
new Edge(n11,75)
};
n11.adjacencies = new Edge[]{
new Edge(n10,75),
new Edge(n12,120)
};
n12.adjacencies = new Edge[]{
new Edge(n11,120),
new Edge(n6,146),
new Edge(n7,138)
};
n13.adjacencies = new Edge[]{
new Edge(n7,101),
new Edge(n14,90),
new Edge(n5,211)
};
n14.adjacencies = new Edge[]{
new Edge(n13,90)
};
UniformCostSearch(n1,n13);
List<Node> path = printPath(n13);
System.out.println("Path: " + path);
}
public static void UniformCostSearch(Node source, Node goal){
source.pathCost = 0;
PriorityQueue<Node> queue = new PriorityQueue<Node>(20,
new Comparator<Node>(){
//override compare method
public int compare(Node i, Node j){
if(i.pathCost > j.pathCost){
return 1;
}
else if (i.pathCost < j.pathCost){
return -1;
}
else{
return 0;
}
}
}
);
queue.add(source);
Set<Node> explored = new HashSet<Node>();
boolean found = false;
//while frontier is not empty
do{
Node current = queue.poll();
explored.add(current);
if(current.value.equals(goal.value)){
found = true;
}
for(Edge e: current.adjacencies){
Node child = e.target;
double cost = e.cost;
child.pathCost = current.pathCost + cost;
if(!explored.contains(child) && !queue.contains(child)){
child.parent = current;
queue.add(child);
System.out.println(child);
System.out.println(queue);
System.out.println();
}
else if((queue.contains(child))&&(child.pathCost>current.pathCost)){
child.parent=current;
current = child;
}
}
}while(!queue.isEmpty());
}
public static List<Node> printPath(Node target){
List<Node> path = new ArrayList<Node>();
for(Node node = target; node!=null; node = node.parent){
path.add(node);
}
Collections.reverse(path);
return path;
}
}
class Node{
public final String value;
public double pathCost;
public Edge[] adjacencies;
public Node parent;
public Node(String val){
value = val;
}
public String toString(){
return value;
}
}
class Edge{
public final double cost;
public final Node target;
public Edge(Node targetNode, double costVal){
cost = costVal;
target = targetNode;
}
}
回答by Ray.R.Chua
Wow. I manage to figure out! Apparently, I added a 2-way edges instead of just 1-way edges. Instead of having Edge e1 going from Node A to Node B and Edge e2 going from Node B to Node A, I remove e2, such that it becomes a single directed graph. Thus, the algorithm works!
哇。我设法弄清楚了！显然，我添加了 2 向边，而不仅仅是 1 向边。我没有让边 e1 从节点 A 到节点 B 和边 e2 从节点 B 到节点 A，而是删除 e2，使其成为一个单一的有向图。因此，该算法有效！
回答by Viktor Seifert
The problem with your algorith is the part when you find a new shorter path to a node that is already in the queue. You should not set currentoutside the call to pollas this breaks the algorithms scheme. Instead you should decrease the key/priority/current-shortest-path-cost of the node.
你的算法的问题在于当你找到一个新的更短路径到一个已经在队列中的节点时。您不应current在调用之外设置，poll因为这会破坏算法方案。相反，您应该降低节点的键/优先级/当前最短路径成本。
I've updated your code to do this. It provides the expected result. But like I said in a comment, when it comes to asymptotic complexity this is not the most efficient solution. The best option is to find or write a PriorityQueuethat supports dynamically keys efficiently.
我已经更新了你的代码来做到这一点。它提供了预期的结果。但是就像我在评论中所说的那样，当涉及到渐近复杂性时，这不是最有效的解决方案。最好的选择是找到或编写一个PriorityQueue有效地支持动态键的方法。
But here is the updated code:
但这里是更新的代码：
import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Set;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
//diff between uniform cost search and dijkstra algo is that UCS has a goal
public class UniformCostSearchAlgo{
public static void main(String[] args){
//initialize the graph base on the Romania map
Node n1 = new Node("Arad");
Node n2 = new Node("Zerind");
Node n3 = new Node("Oradea");
Node n4 = new Node("Sibiu");
Node n5 = new Node("Fagaras");
Node n6 = new Node("Rimnicu Vilcea");
Node n7 = new Node("Pitesti");
Node n8 = new Node("Timisoara");
Node n9 = new Node("Lugoj");
Node n10 = new Node("Mehadia");
Node n11 = new Node("Drobeta");
Node n12 = new Node("Craiova");
Node n13 = new Node("Bucharest");
Node n14 = new Node("Giurgiu");
//initialize the edges
n1.adjacencies = new Edge[]{
new Edge(n2,75),
new Edge(n4,140),
new Edge(n8,118)
};
n2.adjacencies = new Edge[]{
new Edge(n1,75),
new Edge(n3,71)
};
n3.adjacencies = new Edge[]{
new Edge(n2,71),
new Edge(n4,151)
};
n4.adjacencies = new Edge[]{
new Edge(n1,140),
new Edge(n5,99),
new Edge(n3,151),
new Edge(n6,80),
};
n5.adjacencies = new Edge[]{
new Edge(n4,99),
new Edge(n13,211)
};
n6.adjacencies = new Edge[]{
new Edge(n4,80),
new Edge(n7,97),
new Edge(n12,146)
};
n7.adjacencies = new Edge[]{
new Edge(n6,97),
new Edge(n13,101),
new Edge(n12,138)
};
n8.adjacencies = new Edge[]{
new Edge(n1,118),
new Edge(n9,111)
};
n9.adjacencies = new Edge[]{
new Edge(n8,111),
new Edge(n10,70)
};
n10.adjacencies = new Edge[]{
new Edge(n9,70),
new Edge(n11,75)
};
n11.adjacencies = new Edge[]{
new Edge(n10,75),
new Edge(n12,120)
};
n12.adjacencies = new Edge[]{
new Edge(n11,120),
new Edge(n6,146),
new Edge(n7,138)
};
n13.adjacencies = new Edge[]{
new Edge(n7,101),
new Edge(n14,90),
new Edge(n5,211)
};
n14.adjacencies = new Edge[]{
new Edge(n13,90)
};
UniformCostSearch(n1,n13);
List<Node> path = printPath(n13);
System.out.println("Path: " + path);
}
public static void UniformCostSearch(Node source, Node goal){
source.pathCost = 0;
PriorityQueue<Node> queue = new PriorityQueue<Node>(20,
new Comparator<Node>(){
//override compare method
public int compare(Node i, Node j){
if(i.pathCost > j.pathCost){
return 1;
}
else if (i.pathCost < j.pathCost){
return -1;
}
else{
return 0;
}
}
}
);
queue.add(source);
Set<Node> explored = new HashSet<Node>();
boolean found = false;
//while frontier is not empty
do{
Node current = queue.poll();
explored.add(current);
if(current.value.equals(goal.value)){
found = true;
}
for(Edge e: current.adjacencies){
Node child = e.target;
double cost = e.cost;
child.pathCost = current.pathCost + cost;
if(!explored.contains(child) && !queue.contains(child)){
child.parent = current;
queue.add(child);
System.out.println(child);
System.out.println(queue);
System.out.println();
}
else if((queue.contains(child))&&(child.pathCost>current.pathCost)){
child.parent=current;
// the next two calls decrease the key of the node in the queue
queue.remove(child);
queue.add(child);
}
}
}while(!queue.isEmpty());
}
public static List<Node> printPath(Node target){
List<Node> path = new ArrayList<Node>();
for(Node node = target; node!=null; node = node.parent){
path.add(node);
}
Collections.reverse(path);
return path;
}
}
class Node{
public final String value;
public double pathCost;
public Edge[] adjacencies;
public Node parent;
public Node(String val){
value = val;
}
public String toString(){
return value;
}
}
class Edge{
public final double cost;
public final Node target;
public Edge(Node targetNode, double costVal){
cost = costVal;
target = targetNode;
}
}
回答by user3198383
This is solved problem of Uniform Cost Search with added path, what is wrong in your algorithm.
这是解决了添加路径的统一成本搜索问题，您的算法有什么问题。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
public class UniformCostSearchAlgo {
public static void main(String[] args) {
Node n1 = new Node("Arad");
Node n2 = new Node("Zerind");
Node n3 = new Node("Oradea");
Node n4 = new Node("Sibiu");
Node n5 = new Node("Fagaras");
Node n6 = new Node("Rimnicu Vilcea");
Node n7 = new Node("Pitesti");
Node n8 = new Node("Timisoara");
Node n9 = new Node("Lugoj");
Node n10 = new Node("Mehadia");
Node n11 = new Node("Drobeta");
Node n12 = new Node("Craiova");
Node n13 = new Node("Bucharest");
Node n14 = new Node("Giurgiu");
// initialize the edges
n1.adjacencies = new Edge[] { new Edge(n2, 75), new Edge(n4, 140),
new Edge(n8, 118) };
n2.adjacencies = new Edge[] { new Edge(n1, 75), new Edge(n3, 71) };
n3.adjacencies = new Edge[] { new Edge(n2, 71), new Edge(n4, 151) };
n4.adjacencies = new Edge[] { new Edge(n1, 140), new Edge(n5, 99),
new Edge(n3, 151), new Edge(n6, 80), };
n5.adjacencies = new Edge[] { new Edge(n4, 99), new Edge(n13, 211) };
n6.adjacencies = new Edge[] { new Edge(n4, 80), new Edge(n7, 97),
new Edge(n12, 146) };
n7.adjacencies = new Edge[] { new Edge(n6, 97), new Edge(n13, 101),
new Edge(n12, 138) };
n8.adjacencies = new Edge[] { new Edge(n1, 118), new Edge(n9, 111) };
n9.adjacencies = new Edge[] { new Edge(n8, 111), new Edge(n10, 70) };
n10.adjacencies = new Edge[] { new Edge(n9, 70), new Edge(n11, 75) };
n11.adjacencies = new Edge[] { new Edge(n10, 75), new Edge(n12, 120) };
n12.adjacencies = new Edge[] { new Edge(n11, 120), new Edge(n6, 146),
new Edge(n7, 138) };
n13.adjacencies = new Edge[] { new Edge(n7, 101), new Edge(n14, 90),
new Edge(n5, 211) };
n14.adjacencies = new Edge[] { new Edge(n13, 90) };
UniformCostSearch(n1, n13);
List<Node> path = printPath(n13);
System.out.println("Path: " + path);
}
public static void UniformCostSearch(Node source, Node goal) {
List<Node> list = new ArrayList<Node>();
source.pathCost = 0;
PriorityQueue<Node> queue = new PriorityQueue<Node>(20,
new Comparator<Node>() {
// override compare method
public int compare(Node i, Node j) {
if ((i.pathCost > j.pathCost)) {
return 1;
}
else if (i.pathCost < j.pathCost) {
return -1;
}
else {
return 0;
}
}
}
);
queue.add(source);
Set<Node> explored = new HashSet<Node>();
List<Node> path = new ArrayList<Node>();
// while frontier is not empty
do {
path.clear();
Node current = queue.poll();
explored.add(current);
for (Node node = current; node != null; node = node.parent) {
path.add(node);
}
if (current.value.equals(goal.value)) {
goal.parent = current.parent;
goal.pathCost = current.pathCost;
break;
}
for (Edge e : current.adjacencies) {
Node child = e.target;
double cost = e.cost;
if ((queue.contains(child) || explored.contains(child))
&& !path.contains(child)) {
Node n = new Node(child);
list.add(n);
list.get(list.size() - 1).pathCost = current.pathCost
+ cost;
list.get(list.size() - 1).parent = current;
queue.add(list.get(list.size() - 1));
System.out.println(list.get(list.size() - 1));
System.out.println(queue);
} else if (!path.contains(child)) {
child.pathCost = current.pathCost + cost;
child.parent = current;
queue.add(child);
System.out.println(child);
System.out.println(queue);
}
}
} while (!queue.isEmpty());
}
public static List<Node> printPath(Node target) {
List<Node> path = new ArrayList<Node>();
for (Node node = target; node != null; node = node.parent) {
path.add(node);
}
Collections.reverse(path);
return path;
}
}
class Node {
public final String value;
public double pathCost;
public Edge[] adjacencies;
public Node parent;
public Node(String val) {
value = val;
}
public Node(Node node) {
int i = 0;
adjacencies = new Edge[node.adjacencies.length];
value = node.value;
pathCost = node.pathCost;
for (Edge e : node.adjacencies) {
adjacencies[i++] = e;
}
parent = node.parent;
}
public String toString() {
return value + pathCost + " ";
}
}
class Edge {
public final double cost;
public final Node target;
public Edge(Node targetNode, double costVal) {
cost = costVal;
target = targetNode;
}
}
回答by Erfan Eghterafi
Change this part of code
更改这部分代码
else if((queue.contains(child))&&(child.pathCost>current.pathCost)){
child.parent=current;
current = child;
}
to
到
else if((queue.contains(child))&&(child.pathCost>current.pathCost+cost)){
child.parent=current;
child.pathCost = current.pathCost+cost;
queue.remove(child);
queue.add(child);
}
