Невозможно создать список элементов, связанных "Родителем"

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.

// цель - это открытый список, который вернул метод Solve ....

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;
}

после этого ... по методу Solve .. есть эта часть кода

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

newPath.SetParent(t);

Я думаю, что ОШИБКА именно в этой части, newPath указывает на t , когда она должна указывать на узел в списке открыт

Это правда? Если это .. как я могу это исправить?

Answer 1

ваш объем кода требует более глубокого изучения, но в основном я вижу, что вы неверно отслеживаете свой путь.Предположим, что n - ваш последний узел.затем вернитесь обратно, как это

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

, после этого n будет исходным узлом