2

両方のポイントが同じ平面上にない（化合物の異なるフロア/レベルにある-化合物の異なるフロア/レベルにある-ポイントAからポイントBへのパスを見つけるという特定の問題を解決するためにどのアルゴリズムまたはアプローチを検討するかについてこの問題があります-そうではないかもしれません同じ建物にあります）。

A*とダイクストラの両方のアルゴリズムを検討しています。しかし、このアルゴリズムに基づくのはこれだけです（私が間違っている場合は訂正してください）。単一のマッププロットにのみ焦点を当てます。（多くのフロアと多くの建物のために）異なるマッププロットを持つことは、前述のアルゴリズムの両方に対して異なるストーリーを持つ可能性があります。

難しさに合わせて、データの一貫性を保つために、すべてのマップの形式を考案しました。各マップには、建物名、フロア番号、および各フロアが持つ可能性のあるセクションとフロアプラン（2次元の単一文字配列に変換）のデータがあります。例（両方のマップは異なるファイルにあります）：

//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

A *、BFS、およびその他はすべて、グラフで機能するアルゴリズムです。問題は、2つのノード（頂点）が隣接していて同じフロアにある場合、またはそれらが同じエレベータを表しているが異なるフロアにある場合に、2つのノード（頂点）の間にエッジがあるグラフと見なすことができます。

グラフはメモリ内に明示的に作成できますが、必ずしもそうする必要はありません。パスファインダーの観点からは、グラフをグラフのように扱うことができます。

于 2013-03-23T18:11:01.233 に答える
2 
// X is the path from Point A to Point B

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

これは、単一のフロアでのみ機能するソリューションです。

ロボットは4方向にしか動かない..

提案された解決策は、タブー リストを使用した BFS (Breadth-First Search) です。

これらのクラスの使用: 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 に答える
1

実装によっては、複数のマップを 1 つのグラフに結合し、特定のポイントで相互接続できるようにする必要があります。それが、BlueRaja が説明しようとしてきた考えだと思います。

A* アルゴリズム (および Djkstra も同様) は、グラフのノードを離れるエッジとそれぞれの重みのクエリに基づいています。ほとんどの言語では、このグラフ オブジェクトは、不透明な型と、その内容をクエリする操作のセットに抽象化できます。たとえば、Java では、一連の操作がインターフェイスを構成し、インターフェイスを実装するクラスがキャスト バックされた不透明な型になります。そのインターフェイスに。他の言語では、構造、シグネチャ、およびファンクターを備えた ML の方言など、このメカニズムが異なる場合があります。

アルゴリズムがこのインターフェイスを中心に構築されている場合、グラフ インターフェイスを実装するフロア マップ クラスを、コンテンツが複数のフロア マップである別のタイプに置き換えるのは非常に簡単であり、必要な関数またはメソッドは、フロア内で均一に規則的なエッジを伝達します。フロア間の特別なエッジ。その新しい建物クラスを使用して、建物のいくつかのインスタンスを (同じパターンに従って) カプセル化し、アドホック コードを使用して建物の内部接続と外部接続をグラフ エッジとして提供することを想像できます。

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とほぼ同じコードを複製します。WorldBuildingRoom

もちろん、コンテナのような「ロシア人形」のパターンを見ることができます。これは確かに何らかの方法で抽象化できますが、この例の目的は、モデル化する世界のさまざまな部分で同じインターフェースを実装する方法を示すことです。 .

于 2013-03-24T01:43:52.567 に答える