1.算法描述
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止(BFS、prime算法都有类似思想)。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
算法描述
(1)S为已经找到的从v出发的最短路径的终点集合,它的初始状态为空集,将源点加入S中。 其余顶点构成集合U。
(2)构建源点到其余顶点的距离列表,与源点不相连的顶点距离记为∞。
(3)广度遍历与源点相连的顶点,找到距离最近的顶点,则到这个顶点的最短路径就确定了,最短距离就是当前距离,将这个顶点从U中拿出,放入S中。
(4)用当前的顶点作为中间点,对其进行广度遍历,对遍历到的顶点距离进行更新。
(5)在U中搜索最短距离的顶点,将其放入S。
(6)以这个节点作为中间点广度搜索,更新距离。
(7)重复这个过程,直至U为空。
Astar算法是一种图形搜索算法,常用于寻路。它是个以广度优先搜索为基础,集Dijkstra算法与最佳优先(best fit)算法特点于一身的一种 算法。AStar(又称 A*),它结合了 Dijkstra 算法的节点信息(倾向于距离起点较近的节点)和贪心算法的最好优先搜索算法信息(倾向于距离目标较近的节点)。可以像 Dijkstra 算法一样保证找到最短路径,同时也像贪心最好优先搜索算法一样使用启发值对算法进行引导。AStar的核心在于将游戏背景分为一个又一个格子,每个格子有自己的靠谱值,然后通过遍历起点的格子去找到周围靠谱的格子,接着继续遍历周围…… 最终找到终点。
2.仿真效果预览
matlab2022a仿真结果如下:
3.MATLAB核心程序
% --- Executes on button press in pushbutton1. function pushbutton1_Callback(hObject, eventdata, handles) % hObject handle to pushbutton1 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) isshow = 0; if get(handles.checkbox1,'Value')==1 isshow = 1;%是否显示动态过程 else isshow = 0; end isshow2 = 0; if get(handles.checkbox2,'Value')==1 isshow2 = 1;%是否显示搜索区域 else isshow2 = 0; end isrigid = 0; if get(handles.checkbox3,'Value')==1 isrigid = 1;%是否为刚体机器人 else isrigid = 0; end algsel = 0; if get(handles.checkbox4,'Value')==1 algsel = 1;%算法选择 else algsel = 0; end X = 250; Y = 150; % Resolution / Grid Size for the Map_updata %网格化处理,转换为矩阵 step = str2num(get(handles.edit1,'string'));;%定义精度越小,精度越高 tmps1 = str2num(get(handles.edit2,'string')); tmps2 = str2num(get(handles.edit3,'string')); tmps3 = str2num(get(handles.edit4,'string')); tmps4 = str2num(get(handles.edit5,'string')); % Start point Starts = floor([tmps1(1),tmps1(2)]/step) % Robot radius Rad = floor(tmps3/step); % Clearance Clearance = floor(tmps4/step); % Goal point Ends = floor([tmps2(1),tmps2(2)]/step); Map = func_map(X,Y,step); Mapr = func_map_rigid(X,Y,step,Clearance); [R,C] = size(Map); axes(handles.axes1); Color_Map = [1,1,1;0,0,0;1,1,0;1,1,0;0,1,1;1,0,1;1,0,0]; Map_updata1 = Map; Map_updata2 = Mapr; Map_updata1(Starts(2),Starts(1)) = 5;%起点 Map_updata1(Ends(2) ,Ends(1)) = 6;%终点 Map_updata2(Starts(2),Starts(1)) = 5;%起点 Map_updata2(Ends(2) ,Ends(1)) = 6;%终点 colormap(Color_Map); image(Map_updata1); axis image; if algsel == 0 [Map_updata,route]=func_Dijkstra(Map_updata1,Map_updata2,Starts,Ends,R,C,isshow,isshow2,isrigid); else [Map_updata,route]=func_Astar(Map_updata1,Map_updata2,Starts,Ends,R,C,isshow,isshow2,isrigid); end Map_updata_=Map_updata; for k = 2:length(route)-1 Map_updata(route(k)) = 7; tmps = Map_updata_(route(k)); Map_updata_(route(k))= 7; image(Map_updata); %显示机器人 [x,y]=find(Map_updata_==7); hold on if isrigid==0 plot(y(1),x(1),'bo','MarkerSize',2); else [xrr,yrr] = rigid_robot(Rad,y(1),x(1)); plot(xrr,yrr,'b-'); end hold off; axis image; Map_updata_(route(k))= tmps; pause(0.00002); end 02_064m
标签:Dijkstra,Map,get,updata,GUI,handles,Astar,算法 From: https://www.cnblogs.com/51matlab/p/17105495.html