無法創建由「父」鏈接的元素列表

Question

我試圖創建一個方法（使用* A **算法），它解決了一個謎題並將步驟返回給該解決方案。解決方案很簡單..但我無法返回到那個路徑。

我使用了一個節點列表，然後每次推回一個新的節點時，我都設置了父指向節點的新節點;

list<Node> opened; 
list<Node> closed; 

Node current; 

opened.push_back(start); 

while(opened.size() !=0) 
{ 
    current = getLowestCostPath(opened); 


    if(IsSolution(current) == true) 
     return opened; 

    opened.remove(current); 

    if(!Has(closed, current)) 
      closed.push_back(current); 


    for(int i = 0; i < static_cast<int>(current.GetBoard().capacity()); i++) 
    { 
    xx = current.GetBoard()[i].X(); 
    yy = current.GetBoard()[i].Y(); 

     for(int j = 0; j < static_cast<int>(current.GetBoard().capacity()); j++) 
     { 
      if(isMovable(current)) 
      { 
       //if found a new node 
       Node newNode = Node(newBoard); 
       Node *t = &current; 

       if(!Has(opened, newNode) && !Has(closed, newNode)) 
       { 
        newNode.SetParent(t); 
        opened.push_back(newPath); 
       } 
      } 
     } 
    } 
} 

(..) 

類節點，它只是這個

class Node{ 

public: 
    std::vector<Point> board; 
    Path *parent; 

    Node(); 
    Node(std::vector<Point> board) 

    virtual std::vector<Point> GetBoard() const; 
    virtual Path* GetParent() const; 
    virtual void SetParent(Node *p); 

---

Node::Node(): board(),parent(NULL) 
{ 
} 

std::vector<Point> Node::GetBoard() const 
{ 
return board; 
} 

void Path::SetParent(Node *p) 
{ 
    this->parent = p; 
} 

Path* Path::GetParent() const 
{ 
    return parent; 
} 

但後來我意識到，我不能建立的路徑，解決難題......

我甚至不能看到單個主板...

for(list<Node>::iterator it = goal.begin(); it != goal.end(); it++) 
{ 
    if((*it).GetParent() != NULL){ 
     cout << "writing a board" << endl; 
     mas::WriteLine((*it).GetParent()->GetBoard() , "\n"); 
    } 
} 

我已經找遍了互聯網，我無法實現我在做什麼錯:(

---

我也試過，但它讓VS2005崩潰。

//目標是

for(std::list<Node>::iterator it = goal.end(); it->GetParent() != NULL; t->GetParent()) 
{ 

    std::cout << "step" << std::endl; 
    mas::WriteLine((*it).GetBoard(), "\n"); 
} 

---

我試圖更清晰，客觀的說，解決返回的方法打開的列表......。所以......看到這部分

current = getLowestCostPath(opened); 

由getLowestCostPath來到該方法返回的值從：

Node Solution::getLowestCostPath(std::list<Node> l) 
{ 
    std::list<Node>::reverse_iterator min = l.rbegin(); 
    int value = 0; 
    for(std::list<Node>::reverse_iterator it = l.rbegin(); it != l.rend(); it++) 
    { 
     if(value < (*it).GetStep()) 
     { 
      min = it; 
      value = (*it).GetStep(); 
     } 
    } 
    return *min; 
} 

後...在方法解決..還有就是代碼

的這部分

//if found a new node 
Node newNode = Node(newBoard); 
Node *t = &current; 

newPath.SetParent(t); 

我認爲這是對這個部分的錯誤，NEWPATH它指向噸時，它應該是指向列表上的節點打開

這是真的嗎？如果是......我該如何解決這個問題？

Answer 1

你的代碼量需要深入調查，但基本上我看到你錯誤地追溯你的方式。假設n是你的最終節點。然後恢復這樣

for (; n->GetParent() != NULL; n = n->GetParent()) 
    //do something on each node 

在此之後，執行n將被初始節點