0

学校のプロジェクト用のゲームを作成しています。プレーヤーがかわす必要のあるオブジェクトのAIの一部として、ダイクストラのアルゴリズムを使用したいと思います。

グラフ（隣接行列）があり、ダイクストラを使用して各オブジェクトからプレーヤーまでのパスを取得したいのですが、現時点でアルゴリズムを呼び出すと、プレーヤーがオブジェクトの後に来る場合、プレーヤーが見つかりません。

私の理解では、ダイクストラのアルゴリズムは、宛先が見つかるまですべてのノードにアクセスする必要がありますが、私の場合はそうではありません。

これまでの私のアルゴリズムは次のようになります。

Node* Graph::DijkstrasAlgorithm(Node* sNode, Node* dNode){
    std::cout<<"Hello Dijkstra!!"<<std::endl;
    for(unsigned int i = 0; i < this->nodeList.size(); ++i){
        nodeList.at(i)->setDistance(INT_MAX);
        nodeList.at(i)->setVisited(false);
    }
    std::cout<<"everything is set"<<std::endl;
    sNode->setDistance(0);
    int numberVisited = 0;
    Node* u = new Node();
    std::cout<<"before while lus"<<std::endl;
    while(numberVisited < numberOfNodes){
        u->setDistance(INT_MAX);
        for(unsigned int j = 0; j < this->nodeList.size(); ++j){
            if((u->getDistance() > this->nodeList.at(j)->getDistance()) && !this->nodeList.at(j)->isVisited() ){
                u = this->nodeList.at(j);
                u->setVisited(true);
                numberVisited++;
            }
        }

    std::cout<<u->getNodeName()<<"=="<<dNode->getNodeName()<<std::endl;
        if((u == dNode) || (u->getDistance() == INT_MAX)){
            std::cout<<"true"<<std::endl;
            break;
        }


        for(int k = 0; k < u->numberOfneighbors(); ++k){
            if(!u->getNeighbors(k)->isVisited())
            {
            //  std::cout<<u->getDistance()<<std::endl;
                int alt = u->getDistance() + 1;
                if( alt < u->getNeighbors(k)->getDistance()){
                     u->getNeighbors(k)->setDistance(alt);
                     u->getNeighbors(k)->setPrevious(u);
                }
            }
        }

    }
    std::vector<Node* > stack;
    u = dNode;
    while(u->getPrevious() != NULL){
        stack.insert(stack.begin(), u);
        u = u->getPrevious();
    }
    if(!stack.empty())
        return stack.at(0);
    else
        return sNode;


}

この場合、dNodeは宛先ノードであり、sNodeは開始ノードです。

誰かが私が間違っていることを知っていますか？

4

2 に答える 2

3

ダイクストラ アルゴリズムでは、最短の拡張パスが指すノードのみを訪問済みとしてマークします。ここであなたが犯したエラーを見ることができます：

u = this->nodeList.at(j);
u->setVisited(true);

ノードをすぐに訪問済みとしてマークしないでください。

uサイクル後にノードのみがポイントする訪問済みとしてマーク

for(unsigned int j = 0; j < this->nodeList.size(); ++j){

そうしないと、改善のたびにノードを訪問済みとしてマークし、それらすべてを処理することさえしません。

于 2013-01-03T09:29:00.103 に答える
1

ダイクストラ アルゴリズムのようにも見えません。

ダイクストラ アルゴリズムを実装するには、ノードの 2 つのリストを維持する必要があります。

  • 検索されたノードのリスト
  • エッジ ノードのソートされたリスト。
    このリストの各ノードには、この場所に到達するためのコストがあります。

あなたのコードにはこれらのリストのどちらもありません。

コストもノードに保存しています。ノードに到達するためのコストはルートに依存するため、これは機能しません (ノードに関連付けられた複数のコストを保存できない場合)。

コードは次のようになると思います。

 // pseudo code.
 // Note all features used are strictly available
 //
 Node* Graph::DijkstrasAlgorithm(Node* sNode, Node* dNode)
 {
     std::list<Node*>                    searchedNodes;
     std::list<std::pair<Node*, cost>>   edgeNodes;

     edgeNodes.push_sorted(sNode, 0);

     while(!edgeNodes.empty())
     {
          std::pair<Node*, cost>  next = edgeNodes.pop_front();
          searchedNodes.push_back(next.first);

          if (next.first == dnode)
          {   // We found the route
              return STUFF;
          }

          for(Edge* edge, next.first->getEdges())
          {
              if (searchedNodes.find(edge->dst) != searchedNodes.end())
              {   continue;
              }

              edgeNodes.push_sorted(dest.dst, next.second + edge->cost);
          }
     }
 }
于 2013-01-03T09:44:24.397 に答える