2

我有这个问题，关于我将考虑使用什么算法或方法来解决从 A 点到 B 点的路径的特定问题，其中两个点不在同一平面上（位于复合的不同楼层/楼层 - 可能不是在同一栋楼上）。

我正在考虑A*和Dijkstra 的算法。然而，仅基于此算法（如果我错了，请纠正我）仅关注单个地图图。具有不同的地图图（由于许多楼层和许多建筑物）对于上述两种算法可能会有不同的故事。

根据困难，我为我的所有地图设计了一种格式，以遵循数据的一致性。在每张地图中，都有建筑物名称、楼层号和每层楼可能具有的部分以及平面图（转换为二维单字符数组）的数据。例如（两个地图都在不同的文件上）：

//MainFloor1             //MainFloor2
Main                    Main
1st                     2nd
1:Wall                  1:Wall
2:Door                  2:Door
3:Elevator              3:Elevator
#                       4:Room1
1111441111              5:Room2
1        1              #
1        1              1111441111
1        1              1552  2441
1111221111              1551  1441
#                       1551  1441
//End-MainFloor1        1111221111
                        #
                        //End-MainFloor2

从给定的地图中，如果我想考虑从 A 点（MainFloor1 的第一个“2”下方）到 B 点（MainFloor2 左上角的第一个“4”）将返回结果。


// X is the path from Point A to Point B
1111X41111 1111X41111
1   X    1 1552XXXB41 
1   X    1 1551  1441 
1   X    1 1551  1441 
1111A21111 1111221111

我将考虑或采取什么方法从给定的地图输入中产生这样的结果？

谢谢

4

3 回答 3

2 
// X is the path from Point A to Point B

1111B11111
1   X    1
1   X    1
1   X    1
1111A11111

这是一个仅适用于单层的解决方案，

机器人只能在 4 个方向移动..

建议的解决方案是使用禁忌列表的 BFS（广度优先搜索）

使用这些类：https ://stackoverflow.com/a/15549604/2128327

class Floor
{
    public ArrayList<Point> points;

    public int minX, minY, maxX, maxY;

    public Floor ()
    {
        p = new ArrayList<Point>();
    }
}

单层解决方案：

class PathFinder
{
    public static Floor floor;

    public static Point location;

    public static void search (Floor floor, Point dest, Point initial_location)
    {
        QueueSet<Point> fringe = new QueueSet<Point>();

        ArrayList<Point> taboo = new ArrayList<Point>();

        boolean solution_found = false;

        Point p = null;

        fringe.enqueue(initial_location);

        while (fringe.size() > 0)
        {
            p = fringe.dequeue();
            taboo.add(p);

            if (p.x == dest.x && p.y == dest.y)
            {
                    solution_found = true;
                    break;
            }

            if (p.x > floor.minX && !taboo.contains(new Point(p.x-1,p.y))
                fringe.enqueue(new Point(p.x-1,p.y));

            if (p.x < floor.maxX && !taboo.contains(new Point(p.x+1,p.y))
                fringe.enqueue(new Point(p.x+1,p.y));

            if (p.y > floor.minY && !taboo.contains(new Point(p.x,p.y-1))
                fringe.enqueue(new Point(p.x,p.y-1));

            if (p.y < floor.maxY && !taboo.contains(new Point(p.x,p.y+1))
                fringe.enqueue(new Point(p.x,p.y+1));
        }

        // taboo list represent the path taken so far

        fringe.clear();
    }
}
于 2013-03-23T17:35:08.903 回答
2

A*、BFS 等都是适用于图的算法。如果两个节点（顶点）相邻且位于同一楼层，或者它们代表同一电梯但位于不同楼层，则可以将您的问题视为一个图。

请注意，您可以在内存中显式构建图形，但您不必这样做 - 您可以简单地将其视为从探路者的角度来看的图形。

于 2013-03-23T18:11:01.233 回答
1

根据您的实施，应该可以将多个地图与特定点的互连组合在一个图形中。我认为这就是 BlueRaja 一直试图解释的想法。

A* 算法（以及 Djkstra）基于查询离开图节点的边及其各自的权重。在大多数语言中，这个图形对象可以被抽象为一个不透明类型和一组操作来查询它的内容：例如，在 Java 中，一组操作将构成一个接口，而不透明类型则将实现接口的类转换回到那个界面。其他语言可能会以不同的方式提供这种机制，例如在具有结构、签名和函子的机器学习方言中。

如果算法是围绕这个接口构建的，那么应该很容易将实现图形接口的楼层地图类替换为另一种类型，其内容将是几个楼层地图，以及在楼层内传达统一规则边缘的必要函数或方法，和地板之间的特殊边缘。有了这个新的建筑类，人们可以想象封装（遵循相同的模式）几个建筑实例，并使用 ad hoc 代码提供建筑内部和外部连接作为图形边缘。

A*算法的实现，如果抽象得好，应该与图、节点和边的实现细节完全正交，并且应该能够与任何支持图接口的对象一起执行。

例如，这里是一个可能的 Graph 接口：

interface Graph<Node, Scalar> {
    int compare(Node n1, Node n2);
    Collection<Node> getNeighbourgs(Node n);
    Scalar getCost(Node n1, Node n2);
}

其中Node是图中的一个节点，Scalar类型表示节点之间的成本（或距离）。

class Cell<Position extends Comparable<Position>> implements Comparable<Cell<Position>> {
    private Position position;
    public Cell(Position p){
         position = p;
    }
    Position getPosition(){
         return position;
    }
    int compareTo(Cell<Position> c){
         return position.compareTo(c.getPosition());
    }
}

abstract class WorldCell extends Cell<Position> {
    public WorldCell(Position p){
        super(p);
    }
}

abstract class World implements Graph<WorldCell, Integer> {
     private Building [] buildings;
     private HashMap<WorldCell, LinkedList<WorldCell>> gateways;
     int compare(WorldCell n1, WorldCell n2){
           return n1.compareTo(n2);
     }
     public Collection<WorldCell> getNeighbourgs(WorldCell c){
           // build the collections of cells from the building it belongs to
           // and the gateways (connections between buildings
     }
     Scalar getCost(Node n1, Node n2){
           // compute the cost based on the node positions in space
     }       
}


abstract class Building implements Graph<WorldCell, Integer> {
     private Floor [] floors;
     private HashMap<WorldCell, LinkedList<WorldCell>> gateways;
     int compare(WorldCell n1, WorldCell n2){
           return n1.compareTo(n2);
     }
     public Collection<WorldCell> getNeighbourgs(WorldCell c){
           // build the collections of cells from the floor it belongs to
           // and the gateways (connections between floors)
     }

这个部分类集提供了一个多重实现的初始草图Graph。该类Floor将复制或多或少与在类实例数组中World或Building与Room类实例数组中相同的代码。

当然，我们可以在这里看到类似容器的“俄罗斯娃娃”模式，当然可以以某种方式抽象出来，但这个例子的目的是展示相同的接口如何在你打算建模的世界的不同地方实现.

于 2013-03-24T01:43:52.567 回答