欲張最良優先探索GBFS

ゲームプログラミングc++の中で出てきたのでメモついでに残しておく.
初投稿なので不足する点があるのはご容赦いただきたい.

GBFSはヒューリスティック関数h(x)を用いることで次に評価すべきノードを決定していく.現在までの道のりを考慮せず,次に進むべき道の予想のみに頼って探索を進めて行くために最適とは言い難いらしい. しかし場合によってはよく働く探索法にもなりうるとのこと.個人的にはA*アルゴリズムへの拡張も考えて,腰を据えて取り組んだ.

GBFS.h

#ifndef GBFS_hpp
#define GBFS_hpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>

struct WeightedEdge
{
    //エッジにつながっているノード
    struct WeightedGraphNode* mFrom;
    struct WeightedGraphNode* mTo;
    
    //エッジの重み
    float mWeight;
};

struct WeightedGraphNode
{
    //このノードから出て行くエッジを格納
    std::vector<WeightedEdge*> mEdges;
};


struct GBFSScrach
{
    const WeightedEdge* mParentEdge = nullptr;
    float mHueristic = 0.0f;
    bool mInOpenSet = false;
    bool mInCloseSet = false;
};


double ComputeHeuristic(int *edge);

using GBFSMap =
std::unordered_map<const WeightedGraphNode*, GBFSScrach>;

#endif /* GBFS_hpp */

###注意点としては

• ここで使用している連想配列は使うにはunorderd_mapのインクルードが必要になる.
• "WeightedEdge","WeightedGraphNode"については定義が必要.

GBFS.cpp

#include "GBFS.h"
#include <algorithm>

bool GBFS(const WeightedEdge& g, const WeightedGraphNode* start, const WeightedGraphNode* goal, GBFSMap& outMap)
{
    std::vector<const WeightedGraphNode*> openSet;
    
    const WeightedGraphNode* current = start;
    outMap[current].mInCloseSet=true;
    do {
        for(const WeightedEdge* edge : current -> mEdges)
        {
            GBFSScrach& data = outMap[edge -> mTo];
            
            if(!data.mInCloseSet)
            {
                data.mParentEdge = edge;
                if(!data.mInOpenSet)
                {
                    //ヒューリスティックを計算してオープンセットに追加する.
                    data.mHueristic = ComputeHeuristic(edge -> mTo, goal);
                    data.mInOpenSet = true;
                    openSet.emplace_back(edge->mTo);
                }
            }
        }
        
        if(openSet.empty())
        {break;}
        
        //最もコストの低いノードをオープンセットから探す.
        auto iter = std::min_element(openSet.begin(), openSet.end(), [&outMap](const WeightedGraphNode a, const WeightedGraphNode* b)
                                     {return outMap[&a].mHueristic< outMap[b].mHueristic;
                                         
                                     });
        
        //それをカレントノードにして,オープンセットからクローズドセットに移す.
        
        current = *iter;
        openSet.erase(iter);
        outMap[current].mInOpenSet = false;
        outMap[current].mInCloseSet= true;
    }while(current == goal);
    
    //経路を見つけたか？
    return (current == goal) ? true : false; 
}

注意点としては

• のインクルードが必要
• ComputeHeuristicに関しては書籍では省略されているので自分で定義する必要がある.

GBFS.cpp

//ヒューリスティックを計算してオープンセットに追加する.
               data.mHueristic = ComputeHeuristic(edge -> mTo, goal);

この部分については下の図のような解釈でいいかと思われる.
現在見ているノードに接続された子ノードからgoalノードまでのヒューリスティックを計算している.

参考文献

ゲームプログラミングC++ 著:Sanjay Madhav, 訳:吉川邦夫, 監修:今給黎　隆