0

ウィキペディアの疑似コードに基づいて A* パスファインディング アルゴリズムの実装を行っており、パフォーマンスを最適化しようとしています。「オープン」なノード セット (基本的には調べるノード) 内のノードの処理にほとんどの時間が浪費されていることに気付いたので、処理を高速化するために最善を尽くしてきました。

(バックグラウンド、コードに進んでください) 基本的に、一連のノードがあり、それを使用して次のことを行います。

  • スコアが最も低いノードを見つける
  • ノードがセット内に含まれているかどうかを確認します
  • セットからノードを削除する
  • セットにノードを追加する

並べ替えられたリンク リストを使用すると、すべての要素のチェックから最初の要素の取得まで、最低スコアを見つけることができます。ノードの追加はより複雑になりますが、通常はリスト全体をトラバースする必要がないため、時間を節約できます。削除しても同じです。ノードがセット内にあるかどうかを確認するために、直接アクセスできる配列マップを使用して、追加のメモリをいくらか犠牲にしてすばやく実行できるようにします。

class OpenNodeSet
{
public:
    OpenNodeSet(void);
    ~OpenNodeSet(void);

    void add(GraphNode *n);
    void remove(GraphNode *n);
    void reinsert(GraphNode *n);
    bool contains(GraphNode *n);
    GraphNode* top(void);

    int size(void)          {   return elements;    }
    bool empty(void)        {   return (elements == 0); }

private:
    typedef struct listNode {
        GraphNode *node;
        struct listNode *next;
    } listNode_t;

    listNode_t *root;
    int elements;
    unsigned __int8 map[1024][1024];
};

OpenNodeSet::OpenNodeSet(void)
{
    root = NULL;
    elements = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
            map[i][j] = 0;
}

OpenNodeSet::~OpenNodeSet(void)
{
    while (root != NULL) {
        listNode_t *tmp = root->next;
        free(root);
        root = tmp;
    }
}

void OpenNodeSet::add(GraphNode *n)
{
    listNode_t **head;
    for (head = &root; *head != NULL; head = &(*head)->next)
        if ((*head)->node->f_score > n->f_score)
            break;

    listNode_t *newNode = (listNode_t*)malloc(sizeof(listNode_t));
    newNode->node = n;
    newNode->next = *head;
    *head = newNode;
    map[n->x][n->y] = 1;
    elements++;
}

void OpenNodeSet::remove(GraphNode *n)
{
    listNode_t **head;
    for (head = &root; *head != NULL; head = &(*head)->next)
        if ((*head)->node == n) {
            listNode_t *tmp = *head;
            *head = (*head)->next;
            free(tmp);
            map[n->x][n->y] = 0;
            elements--;
            return;
        }
}

void OpenNodeSet::reinsert(GraphNode *n)
{
    listNode_t **head, **bookmark = NULL;
    listNode_t *ln = NULL;
    int pos = 0;
    for (head = &root; *head != NULL; head = &(*head)->next, pos++) {
        if (bookmark == NULL && (*head)->node->f_score > n->f_score)
            bookmark = head;
        if (ln == NULL && (*head)->node == n) {
            ln = *head;
            *head = (*head)->next;
        }
        if (bookmark && ln)
            break;
    }

    ln->next = (*bookmark)->next;
    *bookmark = ln;
}

bool OpenNodeSet::contains(GraphNode *n)
{
    return map[n->x][n->y]==1;
}

GraphNode* OpenNodeSet::top(void)
{
    return root->node;
}

コードは、あるべき場所ほどクリーン/効率的ではありません。現在、私はただ作業モードに入っています。問題は、それが機能しないことです。

多くの場合、ノードのスコアを変更する必要があり、リスト内の位置も変更する必要があるため、再挿入機能があります。1 つのリスト トラバーサルを使用して削除し、別のリスト トラバーサルを挿入する代わりに、1 つのトラバーサルを使用して、ノードを再挿入する位置と、メモリの割り当てと別のトラバーサルを節約するノード自体の両方を見つけます。問題は、再挿入機能が再挿入するノードを見つけられない場合があることです。つまり、ノードが存在しません (存在しません。手動で確認しました)。しかし、これは起こるべきではありません。それを無視すると、最終的にはセグメンテーション エラー (または Visual Studio の同等のエラー) が発生しますが、それが単に無視した結果なのかどうかはわかりません。パスを見つけるための関数は次のとおりです。

void Graph::findPath(int start_x, int start_y, int goal_x, int goal_y)
{
    GraphNode *start = map[start_x][start_y];
    GraphNode *goal = map[goal_x][goal_y];
    OpenNodeSet open;
    NodeSet closed;

    open.add(start);
    start->g_score = 0;
    start->f_score = distance(start, goal);

    while (!open.empty()) {
        //FIND MIN F_SCORE NODE AND REMOVE NODE FROM OPEN LIST
        GraphNode *curr = open.top();
        open.remove(curr);

        //REACHED GOAL?
        if (curr == goal) {
            reconstructPath(curr);
            break;
        }

        //ADD MIN COST NODE TO CLOSED LIST
        closed.add(curr);

        //FOR EACH NEIGHBOR OF NODE
        for (int i = 0; i < curr->neighbor_count; i++) {
            GraphNode *neighbor = curr->neighbors[i].node;
            float cost = curr->neighbors[i].cost;

            float tmp_g = curr->g_score + cost;
            if (closed.contains(neighbor) && tmp_g >= neighbor->g_score)
                continue;

            bool inOpenSet = open.contains(neighbor);
            if (!inOpenSet || tmp_g < neighbor->g_score) {
                neighbor->parent = curr;
                neighbor->g_score = tmp_g;
                neighbor->f_score = tmp_g + distance(neighbor, goal);

                if (inOpenSet)
                    open.reinsert(neighbor);
                else
                    open.add(neighbor);
            }
        }
    }
}

リストの実装で明らかに何かが起こっていますが、何が原因かわかりません。他の値でテストしようとすると、本来のように動作します。reinsert()本来あるべきではない入力を取得するため、本来のように機能するかどうかはわかりません。興味深いことに、reinsert()/add()呼び出しの代わりに以下を使用すると:

        if (inOpenSet) {
            open.remove(neighbor);
        }
        open.add(neighbor);

・・・大丈夫そうです。ある時点で remove がそこにない要素を見つけたかどうかも確認しましたが、明らかにそうではありませんでした。これにより、機能が疑われreinsert()ますが、私が望むほど確実ではありません。私が知っている限りでは、代わりに削除/追加を使用すると、プログラムが機能するだけで、誤った結果が得られる可能性があります。いずれにせよ、私は自分自身を盲目的に見つめてきたので、別の視点が必要です.

誰かがここで何が起こっているかを見ることができますか? 問題はまれなので、ある種の特殊なケースのようですが、再現できません。人工的な値でテストしたところ、reinsert()不満なく期待どおりの結果が得られました。

PS。他の最適化のヒントや、ノード間の距離よりも優れたヒューリスティックなコスト見積もりも歓迎します。ほとんどの場合、この特定の部分は速度に関するもので、メモリ使用量に関するものではありませんが、どちらも優れています。ああ、スタックオーバーフローの処女はなくなりました。

編集：

素敵なディナーと、数時間の空き時間だけで十分でした。reinsert() の最後の 2 行は次のようになっているはずです。

ln->next = *bookmark;
*bookmark = ln;

テストしたときに正しく実行できたかどうかはわかりませんが、コードが一致していないことに気づきませんでした。通常の削除+追加操作と比較して、特定のテスト ケースで再スコアリングされたノードの修正に費やされる時間が 25% 短縮されました。

それでも、それをより良くする方法についてのより多くのアイデアはいつでも大歓迎です. 挿入位置を見つけるためにバイナリ検索を実行できるようにしたいのですが、巨大な固定サイズの配列または定数 realloc で大量のメモリをシャベルする必要がなく、それを行う良い方法が思いつきません() 呼び出します。

4

0 に答える 0