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

Question

你得原谅我，我的语法技巧不太好。我目前正在尝试使用一个AStar方法创建一个unique_ptr算法，为了匹配这个方法的伪代码，我需要能够在我的开放列表中找到一个具有最低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());的代码上标记)是我希望在打开的列表中找到f_cost最低的节点的地方。

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

谢谢你的帮助。

编辑伪码图像

我正试图按照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; 
        });