7

https://vimeo.com/70999946

再帰的なパス検索アルゴリズムを実装しました。この再帰アルゴリズムは、互いに接続されたノードの事前設定セットに基づいて機能します。各ノードには、上、ボタン、左、右の方向を含む 4 つのポインターがあります。再帰アルゴリズムは、単純に各ノードをウォークスルーし、最終目的地に到達するためにこれら 4 つの方向を 1 つずつ探します。例として、A、B、C、D、E、F、G、H の 7 つのノードを考えてみましょう。

    A (Button->D, Right->B)
    B (Right->C, Left->B)
    C (Left->B)
    D (Button->G, Right->E, Top->A)
    E (Right->F, Left->D)
    F (Left->E)
    G (Right->H, Top->D)
    H (Left->G)

これらのノードを全体的に見ると、次の図が表示されます。

A—B—C
|
D—E—F
|
G—H

この例では、ウォーカーが開始したノードがノード A であり、最終目的地としてノード H に行きたいとします。ノード A は、自身の右、ボタン、左、および上を順番に調べます。その権利は、ノード B に行くことを選択した結果、ノード B を指していました。同じパターンのノード B は、右側のノード C に移動することを選択します。右、上、ボタンがブロックされているため、ノード C はノード B に戻ります。同様に、ノード B はノード A に戻ります。ウォーカーは再び開始点に戻ります。次に、ノード A は、順序に基づいてボタン ノードに移動します。これは、ノード D に移動することを意味します。ノード D は、右側のノード E に移動し、次にノード F に移動します。ノード E とノード D に戻ります。その後、ノード D は、ウォーカーの順序に従って、そのボタンであるノード G に移動することを選択します。そこからノード G がノード H に移動します。最後に、ウォーカーは最終目的地に到達します。

Pseudocode: Recursive Path Finding Algorithm
ArrayList findPath(GameObject currentPoint , GameObject targetPoint , ArrayList InputArrayList)
{
1-Duplicate InputArrayList as tempArrayList

2-If the currentPoint equals to target Point return inputArrayList
//*** End Condition found target

3-If the Right side of the currentPoint is empty goto step 4
3.1- Add currentPoint to tempArrayList
//*** Call Right
3.2- tempArrayList = findPath(currentpoint.Right, targetPoint, tempArrayList);
3.3- If tempArrayList is not null return tempArrayList
4-If the Button side of the currentPoint is empty goto step 5
4.1- Add currentPoint to tempArrayList
//*** Call Button
4.2- tempArrayList = findPath(currentpoint.Button, targetPoint, tempArrayList);
4.3- If tempArrayList is not null return tempArrayList
5-If the Left side of the currentPoint is empty goto step 6
5.1- Add currentPoint to tempArrayList
//*** Call Left
5.2- tempArrayList = findPath(currentpoint.Left, targetPoint, tempArrayList);
5.3- If tempArrayList is not null return tempArrayList
6-If the Top side of the currentPoint is empty goto step 7
6.1- Add currentPoint to tempArrayList
//*** Call Top
6.2- tempArrayList = findPath(currentpoint.Top, targetPoint, tempArrayList);
6.3- If tempArrayList is not null return tempArrayList
7-Return null;
//*** End Condition does not found target
}

注: 実際のコードは C# です。このリンクからダウンロードできます。

ケーススタディでの問題の発生: このコードを理解すると; それを説明するために、それには弱点があります。以下のノードの全体像を考慮して、開始ノードがノード A であり、最終目的地がノード H であると仮定します。

A—B—C
|
D—E—F—I
|   | |
G—H—J—K

最適なパスの解は (A, D, G, H) ですが、説明した再帰的なパス検索アルゴリズムは、その解として (A, D, E, F, I, K, J, H) を見つけます。これは本当にロボットが愚かなロボットのようです :D !

図 1: 再帰的なパス検索アルゴリズム ここに画像の説明を入力

図 2: 学習機能を備えた再帰的経路探索アルゴリズム ここに画像の説明を入力

ノードに学習機能を追加することで問題を解決しました。このリンクから問題の詳細を確認できます。しかし、誰かが再帰アルゴリズムを修正して最短経路を見つけることができるかどうか疑問に思います。

ありがとうございました、

4

3 に答える 3

4

DijkstraやA* 検索と単純に比較してみませんか?

ループの代わりに再帰を使用すると、1025 回の再帰で StackOverflow が発生する可能性があります。

于 2013-07-25T11:33:18.167 に答える
1

これは、必要なものの深さ優先 (より迅速に記述できる) バージョンです。経路探索に対するこの回答はお勧めしません。BlueRaja と Geoffrey の回答は、はるかに一般化可能で、安定しており、経路探索のためのより優れたアルゴリズムです。しかし、OPの直接の質問に答えたかった.

私の例を単純化するために、エッジのコスト/重みは 1 です。最短パス == ターゲットに到達するノードの数が最小のパス (技術的length == |path| - 1には、エッジではなくノードをカウントしているため、考え方は同じです)。このコードはサイクルを処理しません。そのため、他のアルゴリズムを使用することをお勧めします。

public class PathNode {
    public string Id;
    public PathNode[] Children = new PathNode[4];
}

public class PathFinder : MonoBehaviour {
public List<PathNode> shortestPath = null;

/// <summary>
/// Sets shortest path to `candidatePath` if `candidatePath` is shorter
/// or no shortest path yet.
/// </summary>
public void SetShortestPath(List<PathNode> path){
    if(shortestPath == null){
        shortestPath = new List<PathNode>(path);
        return;
    }
    if(path.Count < shortestPath.Count)
        shortestPath = new List<PathNode>(path);
    }

/// <summary>
/// depth-first shortest path
/// </summary>
public void FindShortestPath(PathNode target, List<PathNode> path){
    PathNode next = path[path.Count-1]; //get next node from path
    if(target == next){
        SetShortestPath(path);
        return;
    }
    // dfs - iterate children
    foreach (PathNode node in next.Children){
        if(node!=null){
            path.Add(node);             
            FindShortestPath(target,path);
            path.Remove(node);          
        }
    }
}
public PathNode ExampleEdgeCreation(){
    PathNode a = new PathNode{Id="A"};
    a.Children[(int)Direction.Left] = new PathNode{Id="B"};
    return a;
}
}

などと仮定しPathNode.Children[0] == PathNode.Children[Left]ます。コードでそれらを列挙しましたが、この例を SO 用に小さくしたかったのです。

于 2013-07-25T19:10:41.133 に答える