统一成本搜索实施

问题描述 投票：0回答：4

在观看 Udacity 的“人工智能简介”课程后，我正在尝试实施统一成本搜索。但是，我的算法没有得到正确的路径。在在这里发帖之前已经尝试了一整天。我添加了一张地图来帮助可视化场景。该算法应该找到从阿拉德到布加勒斯特的最短加权路径Romania Map 

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;

    }
}
java search
4个回答
0
投票

哇。我设法弄清楚了！显然，我添加了 2 向边，而不是仅 1 向边。我删除了 e2，而不是让边 e1 从节点 A 到节点 B，边 e2 从节点 B 到节点 A，从而使其成为单个有向图。因此，该算法有效！

0
投票

您的算法的问题在于当您找到到队列中已存在的节点的新的较短路径时。您不应在 

current
调用之外设置 
poll
，因为这会破坏算法方案。相反，您应该减少节点的键/优先级/当前最短路径成本。

我已经更新了您的代码来执行此操作。它提供了预期的结果。但正如我在评论中所说，当涉及渐近复杂性时，这不是最有效的解决方案。最好的选择是找到或编写一个能够有效支持动态键的

PriorityQueue
。

但这是更新后的代码：

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;

    }
}
0
投票

这解决了添加路径的统一成本搜索问题，您的算法有什么问题。 

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;

}

}
0
投票

更改这部分代码

else if((queue.contains(child))&&(child.pathCost>current.pathCost)){

                            child.parent=current;
                            current = child;

                    }

到

 else if((queue.contains(child))&&(child.pathCost>current.pathCost+cost)){

                            child.parent=current;
                            child.pathCost = current.pathCost+cost;
                            queue.remove(child);
                            queue.add(child);


                    }
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.