C++ A* 算法查找成员值在 <deque> openlist 中最低的结构实例

Question

你将不得不原谅我，我的语法能力不是很好。我目前正在尝试使用 unique_ptr 方法创建一个 AStar algoirthm，并且为了匹配它的伪代码，我需要能够在我的 openlist 中找到一个最低 f_cost 的对象，但我不能找出语法。

关于网格你需要知道的它是一个 10x10 的网格，其中包含一系列模型，这些模型也是 10x10 链接到结构的。

该结构由此处未提供的某些布尔值组成，因此我可以计算 f_cost，即启发式成本 + 曼哈顿距离

struct node
{
//Code by RRNewell Uclan 20618255 -- I have to put this here because my 
//university uses refworks, so this is to confirm on submission it is my work. 

 public:
 int Loc_X;
 int Loc_y;

 int manhattandistance; 
 int f_cost

};

void AStarFindPath(IModel* NodeCubeModels[10][10], node NodeArray[10][10], int storeStartLoc_X, int storeStartLoc_y, int storedestLoc_x, int storedestLoc_y)
{
    deque <unique_ptr < node > > openList; 
    deque <unique_ptr < node > > closeList;  
    deque <unique_ptr <node> >::iterator p;

    unique_ptr <node> currentNode(new node); 
    unique_ptr <node> tmpNode(new node); 



    findstartnode(ANodeCubeModels, SNodeArray); 
    tmpNode->Loc_X = storeStartLoc_X; 
    tmpNode->Loc_y = storeStartLoc_y; 
    cout << "Pushing start node onto list, Node:" << storeLoc_X << ":" << storeLoc_y << endl;

    openList.push_back(move(tmpNode));


    while (currentNode->Loc_X != storedestLoc_x && currentNode->Loc_y != storedestLoc_y)
    {
        deque<node>min_element(openList.begin(), openList.end());<<--- <<HERE>>
        // Is where I want to find node on the open list with the lowest f_cost
    }
}

<<Here>>（代码上标示为deque<node>min_element(openList.begin(), openList.end());）是我要在open list上找到最低的节点f_cost.

有人知道这个的语法操作吗？或者如果可能的话，还是我必须换一种方式？

感谢您的帮助。

编辑 Pseudocode Image

我正在尝试按照 sebastian lague 在突出显示的第 5 步/第 5 行中编写的伪代码

编辑原因：更清楚一点。

Answer 1

min_element 是 std 命名空间中的一个方法。所以：

deque <unique_ptr <node> >::iterator current_it = 
                                        std::min_element(openList.begin(), openList.end());
std::unique_ptr<node> current = std::move(*current_it);

请注意，您的 node 结构应该实现 operator< 或者您应该提供一个比较器。后者可能更干净，因为比较特定于算法：

auto current_it = 
    std::min_element(openList.begin(), openList.end(), 
        [&](const std::unique_ptr < node > & lhs, const std::unique_ptr < node > & rhs) 
        {
            return lhs->f_cost < rhs->f_cost; 
        });

C++ A* 算法查找成员值在 <deque> openlist 中最低的结构实例

C++ A* Algorithm finding struct instance with member value that is lowest in <deque> openlist

c++

algorithm

syntax

iterator

deque