线上赛这里我并没有直接使用他们提供的代码，而是选择了重头到尾书写一边，先是A*
#include <stdio.h> #include <iomanip> #include <queue> #include <string> #include <cstring> #include <iostream> using namespace std; #define N 400 #define R 4 bool closelist[N][N]; int path[N][N], G[N][N], F[N][N]; short map[N][N]; int n, m, stx, sty, edx, edy; struct Astar { int x, y, G, F; }openlist[N*N]; struct F { int x, y; }fa[N][N]; struct cmp { int operator()(Astar a, Astar b) { if (a.F != b.F) return a.F > b.F; else return a.G < b.G; } }; int abs(int x) { return x > 0 ? x : -x; } int get(int x, int y) { return (abs(x - edx) + abs(y - edy)) * 10; } int check(int x, int y) { for (int i = max(x - R, 1); i <= min(x + R, m); i++) { if (map[i][y] < 10) return 0; } for (int i = max(y - R, 1); i <= min(y + R, m); i++) { if (map[x][i] < 10) return 0; } return 1; } void A_star() { priority_queue<Astar, vector<Astar>, cmp > openlist; Astar st = {stx, sty, 0, 0}; G[stx][sty] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) G[i][j] = 0x7fffffff; openlist.push(st); closelist[stx][sty] = 1; while (!openlist.empty()) { Astar now = openlist.top(); closelist[now.x][now.y] = 1; openlist.pop(); for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) if ((i != 0 || j != 0) && (now.x + i) <= n && (now.x + i) >= 1 && (now.y + j) <= m && (now.y + j) >= 1) { if ((i == 0 || j == 0) && closelist[now.x + i][now.y + j] != 1 && G[now.x + i][now.y + j] > now.G + 10 && map[now.x + i][now.y + j] > 10 && check(now.x, now.y)) { Astar next = { now.x + i, now.y + j, now.G + 10,now.G + 10 + get(now.x + i, now.y + j) }; fa[now.x + i][now.y + j] = { now.x, now.y }; G[now.x + i][now.y + j] = now.G + 10; F[now.x + i][now.y + j] = next.F; if (now.x + i == edx && now.y + j == edy) return; openlist.push(next); } else if (i != 0 && j != 0 && closelist[now.x + i][now.y + j] != 1 && G[now.x + i][now.y + j] > now.G + 14 && map[now.x + i][now.y + j] > 10 && map[now.x + i][now.y] > 10 && map[now.x][now.y + j] > 10 && check(now.x, now.y)) { Astar next = { now.x + i, now.y + j, now.G + 14,now.G + 14 + get(now.x + i, now.y + j) }; fa[now.x + i][now.y + j] = { now.x, now.y }; G[now.x + i][now.y + j] = now.G + 14; F[now.x + i][now.y + j] = next.F; if (now.x + i == edx && now.y + j == edy) return; openlist.push(next); } } } } int main() { n = 314; m = 332; FILE* stream1; freopen_s(&stream1, "1.in", "r", stdin); freopen_s(&stream1, "1.out", "w", stdout); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> map[i][j]; path[i][j] = map[i][j]; } cin >> stx >> sty >> edx >> edy; memset(fa, -1, sizeof(fa)); A_star(); int i = edx, j = edy; path[i][j] = 0; do { path[fa[i][j].x][fa[i][j].y] = 0; int t1 = fa[i][j].x, t2 = fa[i][j].y; i = t1; j = t2; } while (fa[i][j].x != -1); for (int i = 1; i <= n; i++) { for (int j = 1; j < m; j++) cout << path[i][j] << ','; cout << path[i][m]; cout << ';' <<endl; } fclose(stdin); fclose(stdout); }
然后是Dij
#include <iostream> #include <stdio.h> #include <cstring> #include <string> #include <queue> #include <stack> using namespace std; #define N 205 #define M 1005 #define fill(x, y) memset(x, y, sizeof(x)) #define LL long long #define min(x, y) ((x) < (y) ? (x) : (y)) const LL INF = 1e+18; LL state[N]; int ls[M], n, m, k, st, ed, path[N]; int vexnum, edge; bool exits[N]; struct dis { int to, w, next; }e[M]; int l = 0; struct cmp { int operator()(int a, int b) { return state[a] > state[b]; } }; bool check(int Vexnum, int edge) { if (Vexnum <= 0 || edge <= 0 || ((Vexnum * (Vexnum - 1)) / 2) < edge) return false; return true; } inline int read() { int x = 0, p = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') p = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * p; } void print(int s) { stack<int> q; for(int i = 1;i <= vexnum; i++) { int p = i; while( path[p] != -1) { q.push(p); p = path[p]; } q.push(p); cout << s << "-->" << i << " "; cout << "dis" << ":" << state[i] << " " << s; q.pop(); while(!q.empty()) { cout<<"-->"<<q.top(); q.pop(); } cout<<endl; } } void creadGrath() { printf("输入各条边:\n"); for (int i = 1; i <= edge; i++) { int x = read(), y = read(), w = read(); e[++l] = dis {y, w, ls[x]}; ls[x] = l; e[++l] = dis{ x, w, ls[y] }; ls[y] = l; } } void Dij(int st) { memset(path, -1, sizeof(path)); priority_queue<int, vector<int>, cmp > t; for (int i = 1; i <= vexnum; i++) state[i] = INF; exits[st] = 1; t.push(st); state[st] = 0; while (!t.empty()) { int now = t.top(); t.pop(); for (int i = ls[now]; i; i = e[i].next) { if (state[e[i].to] > state[now] + e[i].w) { path[e[i].to] = now; state[e[i].to] = state[now] + e[i].w; if (!exits[e[i].to]) { exits[e[i].to] = 1; t.push(e[i].to); } } } exits[now] = 0; } } int main() { printf("输入图的顶点个数和边的条数：\n"); vexnum = read(); edge = read(); while (!check(vexnum, edge)) { printf("输入的数值不合法，请重新输入\n"); vexnum = read(); edge = read(); } creadGrath(); for (int i = 1; i <= vexnum; i++) { Dij(i); print(i); } }
方案的核心目标是实现在给定空间中的最短路计算，同时需要满足可调试性，即在实际的计算中，需要能够避免车辆与障碍物的碰撞。
其技术难点在于将通过slam构建出来的地图应用于最短路算法中，即将理论算法和实际应用相结合。
首先用于理论计算的Dijkstra算法，基础思想通过n次循环，每次更新没有找到最短路的节点t，再使用t来更新其他节点的最短路。其最显著的特征是搜索区域是沿着起点的四周，直到找到终点为止。
朴素的Dijkstra的时间复杂度为O(n^2)，而我们的方案采用了堆优化的方案来提升计算速度，其思路为在更新其他节点的最短路时，将枚举改为了取出堆中的小值，堆优化后的时间复杂度为O(mlogn)。在实现上采用了stl优先队列，考虑到标准库的常数问题，在最后的实际方案中可能会使用自己编写的堆来降低常数以提升运行速度。
将Dijkstra算法和实际slam所建图形结合起来的时候，我们考虑每一个节点，都存在连向周围节点的边，水平竖直边权为10，斜角边权为14。进行搜索时不采用邻接表的方式存储，而是仅仅采用传统的Dijkstra算法，如果是对于一个实际的搜索问题，采用堆优化是没有必要的，其地图的的边权是平均的，堆优化算法也退化为基础的Dij。
同时，在进行搜索的时候，需要预留出供车辆行驶的区域，以避免撞墙。
A* 算法则是一种启发式搜索，和经典搜索最根本的不同是其具有一个对于终点距离的估计函数H，通过对终点的有目标的路径估计来减少搜索所使用的时间。对比Dijkstra，其具有明显的速度优势
A* 采用的是将slam算法得出来的灰度图转化为0~255的灰度二维数组，设定一定的阈值将一定灰度的像素作为墙壁，再对这个地图进行A * 寻路。在寻路的过程中，为了保证车辆不会和墙壁发生碰撞，加入了一些可以方便在实际中进行微调的判断函数，表现在输出图中的形式为最短路径不会完全贴着墙壁，也不会紧贴转角进行转弯
但是这个方案仍然需要等拿到实物后再多次进行调试。对于距离的读取，目前的计算方案为一格像素等效为边长为10，对角线长为14的理想图形，以降低对于浮点数计算时的用时。
同时对比dij和A* 算法，dij是广度优先的算法，其找到的最短路径一定为最优的路径，而A* 由于加入了启发函数，找到的路径并不一定是最短的路径。相应的，dij算法所消耗的时间比A* 多，具体采用哪一种算法需要根据实际的需求和计算能力来决定。
另外考虑到在实际操作中，slam算法的建图可能需要实时的动态最短路径算法的支持，在保留原A* 算法基础之上可能会视具体情况采用D* 算法[3] 以实现一边搜索一边更新地图的目的。简单来说，D* 算法先应用Dijkstra算法再在动态更新的过程中使用A*，恰好能够用上已有的两种算法。
Comments NOTHING