*、统一成本和贪婪的最佳优先搜索实现

Question

我正在为A*、统一成本搜索和Java中贪婪的最佳优先搜索算法编写代码。我已经完成了运行良好的代码，但是我在编写这段代码时使用了一些不同的设计策略，我希望这段代码尽可能的高效和干净，这样我就可以真正地使用您的帮助了。

我使用的基本思想是，所有3种算法都是最好的优先搜索算法，不同之处在于它们将节点放入队列的方式。对于A*，队列优先级基于距离加上启发式值，而对于贪婪的队列则是启发式值，因此我为BestFirstSearch编写了代码，并为每个算法编写了不同的队列。下面是我的代码

BestFirstSearch.Java

import java.util.Collections;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class BestFirstSearch {
    Graph g;
    /* Dont set infinity to Integer.MAX_VALUE it will result 
       into integer overflow when you add heuristics cost
       into it */    
    int INFINITY = 100000007;

    /* Priority queue for holding pairs of vertex id */
    BestFirstSearchQueue queue;

    /* Previous node in path */
    int previousNode[];

    /* Distance of this node from source */
    int shortestDistance[];

    /* Debugging related data */
    ArrayList<Integer> exploredCities;

    public BestFirstSearch(Graph g, BestFirstSearchQueue queue) {
        this.g = g;
        this.queue = queue;
        previousNode = new int[g.getV()];
        shortestDistance = new int[g.getV()];
        for (int i = 0; i < g.getV(); i++) {
            previousNode[i] = -1;
            shortestDistance[i] = INFINITY;
        }
        exploredCities = new ArrayList<>();
    }


    private void explore(int currNode, ArrayList<Integer> adjList) {
        for (int succesor : adjList) {
            int currDist = shortestDistance[currNode] + 
                g.getEdgeCost(currNode, succesor);            
            if (shortestDistance[succesor] > currDist) {
                // Distance should never contain heuristic cost
                shortestDistance[succesor] = currDist;
                /* Update if already exitst else add*/
                queue.add(succesor, currDist);
                previousNode[succesor] = currNode;
            }
        }
        exploredCities.add(currNode);
    }

    public SearchData getPathData(int src, int dst) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        int curr = dst;
        while (curr != src && previousNode[curr] != -1) {
            path.add(curr);
            curr = previousNode[curr];
        }
        path.add(src);
        Collections.reverse(path);
        SearchData sData = new SearchData(shortestDistance[dst],
                                          path,
                                          exploredCities);
        return sData;
    }

    public SearchData search(int src, int dst) {
        shortestDistance[src] = 0;
        queue.add(src, 0);
        while (!queue.isEmpty() &&
               queue.peek() != dst) {
            int currNode = queue.poll();
            ArrayList<Integer> adjList = g.getAdjVertices(currNode);
            explore(currNode, adjList);
        }
        return getPathData(src, dst);
    }

}

BestFirstSearchQueue.java - API

接口

import java.util.PriorityQueue;
public interface BestFirstSearchQueue {
    /* Provides a common interface for all best first search graph
       queues. Implement this interface according to search 
       strategy (viz. A*, Uniform cost, Greedy) and pass this queue
       to BestFirstSearch Class. */
    /* This queue interface works on vertex id of each node, basically
       it can store a particular vertex with its cost and retrieve these
       values as per request from search function. The heuristic calculations
       happen inside this class - search function doesn't need to 
       know about these heuristics */

    /* This is the Priority queue used by all classes, comparator will 
       change */

    int initialCapacity = 512;
    /* Adds a new vertex into queue with given cost if its not already
       present, if it is already present in queue then replace it with 
       this value */
    public void add(int vertex, int cost);

    /* returns vertex id of top element of queue */
    public int poll();

    /* removes and returns topmost element of queue */
    public int peek();

    /* checks if queue is empty */
    public boolean isEmpty();
}

AStarSearchQueue.java

import java.util.HashMap;
import java.util.Comparator;
import java.util.PriorityQueue;

class AStarSearchQueue implements BestFirstSearchQueue {
    PriorityQueue<Integer> queue = null;
    /* Hashmap for storing path distance to a node */
    HashMap<Integer, Integer> distanceMap;
    /* Hashmap for storing heuristic value for a node */
    HashMap<Integer, Double> heuristicsMap;

    public AStarSearchQueue() {
        queue = new PriorityQueue<>(initialCapacity,
                                    new AStarCostComparator());
        distanceMap = new HashMap<>();
    }

    public AStarSearchQueue(HashMap<Integer, Double> heuristics) {
        this();
        heuristicsMap = heuristics;
    }

    public AStarSearchQueue(double heuristics[]) {
        this();
        heuristicsMap = new HashMap<>();
        int vertex = 0;
        for(double cost : heuristics) {
            heuristicsMap.put(vertex++, cost);
        }
    }

    public void add(int vertex, int value) {
        if (queue.contains(vertex)) {
            queue.remove(vertex);
            distanceMap.remove(vertex);
        }         
        distanceMap.put(vertex, value);
        queue.add(vertex);
    }

    public int poll() {
        return queue.poll();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public int peek() {
        return queue.peek();
    }

    /* Comparator for A* search strategy */
    class AStarCostComparator implements Comparator<Integer> {
        public int compare(Integer o1, Integer o2) {
            double cost1 = distanceMap.get(o1);
            double cost2 = distanceMap.get(o2);
            cost1 += heuristicsMap.get(o1);
            cost2 += heuristicsMap.get(o2);
            if (cost1 > cost2)
                return 1;
            else if (cost1 == cost2)
                return 0;
            return -1;
        }
    }
}

UniformSearchQueue.java和GreedySearchQueue.java的代码几乎与AStarSearchQueue.java相同，只不过它有不同的比较器类，比较启发式(贪婪)和成本距离(统一)。

我为BestFirstSearch创建了如下对象：

    BestFirstSearch bfs = new BestFirstSearch(usa.getGraph(),
                                              new AStarSearchQueue(usa.getHeuristics(src)));

Answer 1

缺失类

这不是一个完整的代码。它缺少了Graph和SearchData。请提供这些。特别是，我不知道Graph.getV()做了什么，所以即使我相信BestFirstSearch中有一个与它相关的弱点，我也不会研究。

AStarSearchQueue不是Queue

但也有可能。为什么要让它有一个委托PriorityQueue字段，而不是简单地扩展PriorityQueue<Integer>？如果您不打算改变实现，这将是更自然的，并减少对象的计数。

别担心，对您的BestFirstSearch类来说，这些队列将不是PriorityQueues，而是BestFirstSearchQueues，所以不必害怕暴露在许多方法中。

BestFirstSearchQueue接口有一个常量的initialCapacity字段

这被认为是不良做法。如果您是一个接口，您就不知道实现是什么。你怎么会事先知道什么样的初始尺寸是好的？它不仅依赖于实现，而且依赖于实例(如果我的问题很小，为什么要512？)如果我的问题很大，为什么限制在512?)。这是武断的，应该走了。

单元

为什么您的距离存储为Integers，而您的启发式允许Double？让所有的商店Doubles。

声明类型

始终将对象声明为您可以处理的最高级别的类。例如：

ArrayList<Integer> exploredCities;

必须成为：

List<Integer> exploredCities;

这样，您以后就可以轻松地切换实现。