与原始代码相比，上面的并行代码花费了更多的时间。我用bfs方法解决了这个问题。我得到了正确的输出，但花了太多时间。
(x，y(表示矩阵单元坐标，并且dist表示它们与源的最小距离
struct Node
{
int x, y, dist;
};
\Below arrays detail all four possible movements from a cell
int row[] = { -1, 0, 0, 1 };
int col[] = { 0, -1, 1, 0 };
用于检查是否可以转到位置(行、列(的功能从当前位置。函数返回false if(row，col(不是有效的职位，或者值为0，或者已经访问过。
bool isValid(vector<vector<int>> const &mat, vector<vector<bool>> &visited, int row, int col)
{
return (row >= 0 && row < mat.size()) && (col >= 0 && col < mat[0].size())
&& mat[row][col] && !visited[row][col];
}
从源查找矩阵mat中可能的最短路径信元(i，j(到目的信元(x，y(
int findShortestPathLength(vector<vector<int>> const &mat, pair<int, int> &src,
pair<int, int> &dest)
{
if (mat.size() == 0 || mat[src.first][src.second] == 0 ||
mat[dest.first][dest.second] == 0) {
return -1;
}
// `M × N` matrix
int M = mat.size();
int N = mat[0].size();
// construct a `M × N` matrix to keep track of visited cells
vector<vector<bool>> visited;
visited.resize(M, vector<bool>(N));
// create an empty queue
queue<Node> q;
// get source cell (i, j)
int i = src.first;
int j = src.second;
// mark the source cell as visited and enqueue the source node
visited[i][j] = true;
q.push({i, j, 0});
// stores length of the longest path from source to destination
int min_dist = INT_MAX;
// loop till queue is empty
while (!q.empty())
{
// dequeue front node and process it
Node node = q.front();
q.pop();
// (i, j) represents a current cell, and `dist` stores its
// minimum distance from the source
int i = node.x, j = node.y, dist = node.dist;
// if the destination is found, update `min_dist` and stop
if (i == dest.first && j == dest.second)
{
min_dist = dist;
break;
}
// check for all four possible movements from the current cell
// and enqueue each valid movement
#pragma omp parallel for
for (int k = 0; k < 4; k++)
{
// check if it is possible to go to position
// (i + row[k], j + col[k]) from current position
#pragma omp task shared(i,visited,j)
{
if (isValid(mat, visited, i + row[k], j + col[k]))
{
// mark next cell as visited and enqueue it
visited[i + row[k]][j + col[k]] = true;
q.push({ i + row[k], j + col[k], dist + 1 });
}
}
}
}
if (min_dist != INT_MAX) {
return min_dist;
}
return -1;
}
代码的主要部分只包含一个矩阵和源和目的地坐标
int main()
{
vector<vector<int>> mat =
{
{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
{ 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
{ 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 },
};
pair<int, int> src = make_pair(0, 0);
pair<int, int> dest = make_pair(7, 5);
int min_dist = findShortestPathLength(mat, src, dest);
if (min_dist != -1)
{
cout << min_dist<<endl;
}
else {
cout << "Destination cannot be reached from a given source"<<endl;
}
return 0;
}
我使用了共享变量，但它花费了太多时间。有人能帮我吗
正如人们所说，您只能在4个方向上获得并行性；一个更好的方法是保留一组点：首先是起点，然后是一步到位的所有点，然后是两步到位的点。
通过这种方法，您可以获得更多的并行性：您正在构建所谓的"；"波前"；并且可以同时处理所有的点。
auto last_level = reachable.back();
vector<int> newly_reachable;
for ( auto n : last_level ) {
const auto& row = graph.row(n);
for ( auto j : row ) {
if ( not reachable.has(j)
and not any_of
( newly_reachable.begin(),newly_reachable.end(),
[j] (int i) { return i==j; } ) )
newly_reachable.push_back(j);
}
}
if (newly_reachable.size()>0)
reachable.push_back(newly_reachable);
(我是为一个普通的DAG写这篇文章的；把你的迷宫写成DAG对读者来说是一种练习。(
然而，这种方法仍然存在很大的问题：如果当前波前上的两个点决定添加相同的新点，你必须解决这个问题。
对于一种非常相似的方法，您需要放弃"；"推"；完全添加新点的模型；"拉"；型号：在每个"；距离"；迭代时，你在所有点上循环，然后问，如果我不可达，我的一个邻居可达吗？如果是，请将我标记为比那个邻居更容易到达。
如果你想一想最后一种方法，你会发现你本质上是在做一系列矩阵向量乘积，包括邻接矩阵和当前可达集。除了替换标量"+"通过"；min"；并且标量"*"通过"+1〃；。阅读任何关于将图运算解释为线性代数的教程。除了它不是真正的线性。