0

私は n*n マトリックスを持っており、最小コストを持つマトリックスから要素を見つけたいと思っています。ノードのコストはコストを意味します = Manhattandistance(startingnode,node) + costof(node) ここで、開始ノードはどの視点のノードですか私は探しています！

私は4つのforループだけでそれを行いましたが、それは機能しますが、それを最適化したいので、bfsのようなことをしました:キューを使用し、最初に開始ノードを追加し、その後whileループでキューからノードをポップしましたマンハッタン1でそのノードの周りのすべての要素をキューに追加しました。キューからポップしたばかりのノードの距離+マトリックス全体からの最小価格（最初から知っている）が小さい間にこれを行います私が見つけた最小価格よりも（ポップしたばかりのノードの価格を最小値と比較します）それが大きい場合は、見つけた最小ノードが可能な限り低い値であるため、検索を停止します。問題は、おそらく std::queue を使用しているため、このアルゴリズムが遅くなることです。4 for ループ バージョンよりも長い時間動作します。(キューに追加するときに検査している要素が既に追加されているかどうかを確認するために、フラグ マトリックスも使用しました)。最も時間のかかるコード ブロックは、ノードを展開する部分です。要素が有効かどうかを検査する理由がわかりません。つまり、座標が n 未満で、0 より大きい場合は、要素をキューに追加します。

これを改善するにはどうすればよいか、または別の方法があるかどうかを知りたいです! 私が十分に明確であることを願っています。

これは、時間がかかるコードの一部です。

if((p1.dist + 1 + Pmin) < pretmincomp || (p1.dist + 1 + Pmin) < pretres){
                std::vector<PAIR> vec;  
                PAIR pa;
                int p1a=p1.a,p1b = p1.b,p1d = p1.dist;
                if(isok(p1a+1,p1b,n)){
                    pa.a = p1a + 1;
                    pa.b = p1b;
                    pa.dist = p1d + 1;

                    vec.push_back(pa);
                }
                if(isok(p1a-1,p1b,n)){
                    pa.a = p1a - 1;
                    pa.b = p1b;
                    pa.dist = p1d + 1;
                    vec.push_back(pa);
                }

                if(isok(p1a,p1b+1,n)){
                    pa.a = p1a;
                    pa.b = p1b + 1;
                    pa.dist = p1d + 1;
                    vec.push_back(pa);
                }
                if(isok(p1a,p1b -1 ,n)){
                    pa.a = p1.a;
                    pa.b = p1.b - 1;
                    pa.dist = p1d + 1;
                    vec.push_back(pa);
                }



                for(std::vector<PAIR>::iterator it = vec.begin();
                         it!=vec.end(); it++){
                    if(flags[(*it).a][(*it).b] !=1){
                        devazut.push(*it);
                        flags[(*it).a][(*it).b] = 1;
                    }
                }
4

1 に答える 1

1

最短経路の問題を扱っています。これは、 BFS (グラフが重み付けされていない場合) またはA* アルゴリズムで効率的に解決できます- グラフに関する「知識」があり、「コスト」がどれくらいかかるかを見積もることができる場合各ノードからターゲットを見つけます。

ソリューションは BFS と非常に似ていますが、1 つの違いがあります。BFS は、既にアクセスしたすべてのノードのセットも保持します。visitedこのvisitedセットの考え方は、すでに訪問したノードを再訪問する必要がないということです。これは、このノードを最初に訪問したときに見つけた最短パスよりも、そのノードを通過するパスが短くならないためです。 セットがないと、各ノードが何度も再訪されるため、アルゴリズムが非常に非効率になる
ことに注意してください。visited

BFS の疑似コード (訪問済みセットあり):

BFS(start):
  q <- new queue
  q.push(pair(start,0)) //0 indicates the distance from the start
  visited <- new set
  visited.add(start)
  while (not q.isEmpty()):
     curr <- q.pop()
     if (curr.first is target):
        return curr.second //the distance is indicated in the second element
     for each neighbor of curr.first:
        if (not set.contains(neighbor)): //add the element only if it is not in the set
           q.push(pair(neighbor,curr.second+1)) //add the new element to queue
           //and also add it to the visited set, so it won't be re-added to the queue.
           visited.add(neighbot) 
  //when here - no solution was found
  return infinity //exhausted all vertices and there is no path to a target
于 2012-11-05T07:42:39.087 に答える