0

我有 n*n 矩阵，我想从矩阵中找到具有最小成本的元素，节点的成本意味着成本 = Manhattandistance(startingnode,node) + costof(node) 其中起始节点是哪个角度的节点我正在寻找！

我只使用了 4 个 for 循环，它可以工作，但我想优化它，我做了类似 bfs 的操作：我使用了一个队列并首先添加了起始节点，然后在一个 while 循环中我从队列中弹出了节点并使用Manhatttan 1将该节点周围的所有元素添加到队列中。我这样做的同时，我刚刚从队列中弹出的节点的距离+整个矩阵的最低价格（我从一开始就知道）更小比我刚刚找到的最低价格（我将我刚刚弹出的节点的价格与 min 进行比较）如果它更大，我停止搜索，因为我找到的最小节点是可能的最低值。问题是这个算法可能会因为我使用 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 非常相似，但有一个区别 - 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 回答