algorithm - 我应该使用哪种算法来找到未加权网格中从 A 到 B 的最短路径？

Question

该场景是一种回合制情况，玩家必须从源位置 A 向位置 B 移动，但只能移动最大数量的单位。

例如，B 与 A 相距 24 个单位(使用 BFS 计算)，而我的得分为 12。如何找到仅相距 12 个移动单位的通往 B 的最佳路径？

注意事项:

• 不能沿对角线移动
• 有很大的障碍

编辑:这是一款类似于 Clue/Cluedo 的游戏，但它是纯文本的，因此玩家将选择一个“朝向”的方向。

这是我尝试过的:

示例网格:(◘ 是障碍物，○ 不是)

○○○○○○○○○○
○○○○○○○○◘◘
○○○◘◘◘○○◘◘
○○○◘◘◘○○B◘
○A○◘◘◘○○◘◘

算法:

if paces == 0, return
try moving col closer to dest.col:
    if col == dest.col, move row closer to dest.row
    else if adjacent is blocked, move row away from start

这在纸面上没问题，除了当我把自己逼到角落里的时候:

○A→◘◘○○◘◘◘
○○↓◘◘○○B◘◘
○○↓◘◘○○◘◘◘
○○↓◘◘○○↑◘◘
○○↓→→→→→◘◘

解决方案:

public ArrayList<Location> shortestPath(final Location start, final Location dest) {
    HashSet<Location> visits = new HashSet<>();
    HashMap<Location, Location> links = new HashMap<>();

    PriorityQueue<Location> queue = new PriorityQueue<>(Board.GRID_COLS * Board.GRID_ROWS,
            new Comparator<Location>() {

                @Override
                public int compare(Location a, Location b) {
                    return Integer.compare(getHeuristic(a, dest), getHeuristic(b, dest));
                }
            });

    queue.add(start);

    while (!queue.isEmpty()) {
        Location current = queue.remove();
        if (current.equals(dest)) {
            ArrayList<Location> path = reconstruct(current, new LinkedList<Location>(), links);
            path.add(dest);
            return path;
        }

        visits.add(current);
        for (Location neighbour : getNeighbours(current)) {
            if (!visits.contains(neighbour)) {
                queue.add(neighbour);
                visits.add(neighbour);
                links.put(neighbour, current);
            }
        }

    }
    return null; // failed
}

// Manhattan distance
private int getHeuristic(Location src, Location dest) {
    return Math.abs(dest.row - src.row) + Math.abs(dest.col - src.col);
}

private ArrayList<Location> reconstruct(Location current, LinkedList<Location> list, HashMap<Location, Location> links) {
    if (links.containsKey(current)) {
        list.addFirst(links.get(current));
        return reconstruct(links.get(current), list, links);
    } else {
        return new ArrayList<>(list);
    }
}

private ArrayList<Location> getNeighbours(Location current) {
    ArrayList<Location> neighbours = new ArrayList<>();

    if (current.row < GRID_ROWS - 1) {
        Location n = LOCATIONS[current.row + 1][current.col];
        if (isAccessible(n, current)) neighbours.add(n);
    }
    if (current.row > 0) {
        Location n = LOCATIONS[current.row - 1][current.col];
        if (isAccessible(n, current)) neighbours.add(n);
    }
    if (current.col < GRID_COLS - 1) {
        Location n = LOCATIONS[current.row][current.col + 1];
        if (isAccessible(n, current)) neighbours.add(n);
    }
    if (current.col > 0) {
        Location n = LOCATIONS[current.row][current.col - 1];
        if (isAccessible(n, current)) neighbours.add(n);

    }
    return neighbours;
}

Answer 1

对于 A* 来说，这听起来像是一份完美的工作.

在你的图表上，它基本上(在算法上)与广度优先搜索相同，但使用优先级队列(按f(x)排序) 而不是队列。