图论·搜索最短路径

例题地址

搜索最短路径

• 在网格图中按照特定路线搜索，搜索方式基于bfs/dfs
• 需要搜索出一条源点与终点最短的路径

  核心思路

  • 无启发式函数：bfs/dfs+
  • 有启发式函数：dijsktra算法,A*(Astar)…

    个人理解

    • 启发式函数：相当于根据点的权重，对搜索的方向有一定判断，不会盲目的搜索，减少了绝大部分的无用功。
    • 启发式函数一般搭配优先级队列(堆)实现

      ---

      A*算法

      • 有启发式函数的搜索
      • 效率和准确程度很大程度取决于启发式函数

        常见启发式函数

        • 欧拉距离：就是平方和，两点距离之差(x1-x2)^2 + (y1-y2) ^2
        • 切比雪夫距离：没用过，有缘再更新
        • 曼哈顿距离：没用过，有缘再更新

          核心操作

          • 权值的计算：F=G+H
            • G:源点到当前点走过的距离(不是位移,而是路程),是一个真实值
            • H:利用启发式函数计算得到的距离,是一个期望值
            • 优先级队列：对于权值进行排序,同时实现基于BFS的搜索

              个人代码

              #include
              using namespace std;
              using ll = long long;
              int grid[1009][1009];
              int n,a1,a2,b1,b2;
              int dir[8][2] = { 2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1 };
              struct knight {
                  int x, y, g, h, f;//f=g+h,g起点到当前结点，h当前结点到终点
              };
              struct cmp {
                  bool operator()(const knight& a, const knight& b) {
                      return a.f > b.f;
                  }
              };
              priority_queueq;
              int getDist(const int &x,const int &y,const int &b1,const int &b2) {
                  return (x - b1) * (x - b1) + (y - b2) * (y - b2);
              }
              void bfs() {
                  q.push({ a1,a2,0,getDist(0,0,b1,b2),getDist(0,0,b1,b2)});
                  while (!q.empty()) {
                      knight cur = q.top();
                      q.pop();
                      if (cur.x == b1 && cur.y == b2) {
                          cout 
                          next.x = cur.x + dir[k][0];
                          next.y = cur.y + dir[k][1];
                          if (next.x  n;
                  while (n--) {
                      cin >> a1 >> a2 >> b1 >> b2;
                      memset(grid, 0, sizeof(grid));
                      bfs();
                      while (!q.empty()) {
                          q.pop();
                      }
                  }
              }
              int main() {
                  std::ios::sync_with_stdio(false);
                  std::cin.tie(0); std::cout.tie(0);
                  solve();
                  return 0;
              }
              

              注意事项

              • G是路程，利用next.g=getDist(next.x,next.y,a1,a2);计算与源点的距离是错误的
              • grid数组不建议使用vector数组，因为每次使用完都要memset
              • grid仍然需要标记：这里grid本身就可以起到标记作用
              • 题目的步数可以直接由grid统计得到

                A*算法空间优化-IDA

                蜀黍不会，有缘更新

                ---

                dijsktra作为启发式函数

                核心操作

                • 结构体:结构体的dist定义为源点与当前点的距离
                • 队列:根据结构体的dist排序
                • dist数组的定义:定义dist数组是为了比较二者距离，判断是否应该更新(个人觉得比较累赘，但是不得不定义)

                  using namespace std;
                  using ll = long long;
                  vectorgrid(1009, vector(1009, 0));
                  int n,a1,a2,b1,b2;
                  int dir[8][2] = { 2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1 };
                  struct knight {
                      int x, y, dist;
                  };
                  struct cmp {
                      bool operator()(const knight&a,const knight&b) {
                          return a.dist > b.dist;
                      }
                  };
                  priority_queueq;
                  vectordist(1009, vector(1009, INT_MAX));
                  void bfs(vectordist) {
                      dist[a1][a2] = 0;
                      q.push({ a1,a2,dist[a1][a2]});
                      while (!q.empty()) {
                          knight cur=q.top();
                          q.pop();
                          if (cur.x == b1 && cur.y == b2) { 
                              cout 
                          	//相当于选点操作
                              next.x = cur.x + dir[k][0];
                              next.y = cur.y + dir[k][1];
                              if (next.x  n;
                      while (n--) {
                          cin >> a1 >> a2 >> b1 >> b2;
                          bfs(dist);//传入dist数组作为形参
                          while (!q.empty()) {
                              q.pop();
                          }
                      }
                  }
                  int main() {
                      std::ios::sync_with_stdio(false);
                      std::cin.tie(0); std::cout.tie(0);
                      solve();
                      return 0;
                  }
                  

                  注意事项

                  • grid数组因为没有权值(权值为1)所以在dijsktra算法中属于无效部分，只起到存储网格作用
                  • dist数组作为形参，不能使用引用

                    时间复杂度：

                    • A*算法时间复杂度明显更优，但难以确定，取决于启发函数。但对比BFS/DFS/dijsktra算法是相当大的提升
                    • dijsktra算法在面对无权值(权值为1)的图时，退化为BFS
                    • BFS/DFS时间复杂度高

                      参考于代码随想录