a星算法详解_matlab优化算法

a星算法详解_matlab优化算法概述基于上一篇文章提到的DFS算法和BFS算法A星算法属于图这种数据结构的搜索算法,对比于树的遍历搜索,需要考虑到的问题是:同一个节点的重复访问,所以需要对于已经访问过的节点进行标记。曼哈顿距离:在几何度量空间中,用以标明两个点在标准坐标系上的绝对轴距总和。图1中绿色代表欧氏距离(直线距离),蓝色和黄色代表等价的曼哈顿距离。d(i,j)=|Xi-Xj|+|Yi-…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

概述

基于上一篇文章提到的DFS算法和BFS算法
A星算法属于图这种数据结构的搜索算法,对比于树的遍历搜索,需要考虑到的问题是:同一个节点的重复访问,所以需要对于已经访问过的节点进行标记。

曼哈顿距离:
在几何度量空间中,用以标明两个点在标准坐标系上的绝对轴距总和。
图 1
图1中绿色代表欧氏距离(直线距离),蓝色和黄色代表等价的曼哈顿距离。
d( i , j ) = |Xi – Xj| + |Yi – Yj|
优势:计算机图形学中,欧氏距离需要进行浮点运算,曼哈顿距离只涉及到加减法,运算速度大大提高。

我们假设无人车需要从A点(左下侧浅绿色)移动到B点(右上侧浅黄色),但是两点之间被障碍物隔开,我们使用矩阵的形式来构建地图,其中元素为0的矩阵坐标视为可走的,值为1的视为不可走的。


clear;
clc;
clf;
figure(1);
map =[
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
0	0	0	.3	0	0	0	1	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	1	0	0	.7	0	0	0	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	1	1	1	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
];
pcolor(map)
colormap summer
[row,col] = size(map);
[start_px,start_py] = find(map == .3);
[end_px,end_py] = find(map == .7);

close = struct([]); 
closelen = 0;
open = struct([]); 
openlen = 0;

%% 将起点添加到open列表
open(1).row = start_px;
open(1).col = start_py;
open(1).g = 0;
open(1).h = abs(end_py - start_py) + abs(end_px - start_px);
openlen = openlen + 1;
%% 四种运动格式
sport = [0,1;0,-1;-1,0;1,0];
backNum = 0;
prev = [];
while openlen > 0
    %% 获取代价最小的值
    for i = 1:openlen
        f(i,:) = [i,open(i).g + open(i).h];       
    end
    f1 = sortrows(f,2);
    current = open(f1(1));
    choose = 0;
    chooseArr = [];
    %% 回溯将走过的点标记出来
     if current.row == end_px && current.col == end_py
         i = 1;
         while(i<=size(prev,1))
             if prev(i,3) == current.row && prev(i,4) == current.col
                 choose = choose +1;
                 chooseArr(choose,1) = prev(i,1);
                 chooseArr(choose,2) = prev(i,2);
                 current.row =  prev(i,1);
                 current.col =  prev(i,2);
                 i = 1;
             else
                 i = i + 1;
             end
         end      
         for j = 1: size(chooseArr,1)
                map(chooseArr(j,1),chooseArr(j,2)) = 0.5;
         end
         figure(2);
         pcolor(map);
         colormap winter;
         return;         
     end
     closelen = closelen + 1;
     close(closelen).row = open(f1(1)).row;
     close(closelen).col = open(f1(1)).col;
     close(closelen).g = open(f1(1)).g;
     close(closelen).h = open(f1(1)).h;   
     open(f1(1)) = [];
     openlen = openlen -1;     
    for i = 1:4
        dimNormal = all([current.row,current.col]+sport(i,:)>0) ...
            && current.row+sport(i,1)<=row && current.col+sport(i,2)<=col;
        neighbor.row = current.row + sport(i,1);
        neighbor.col = current.col + sport(i,2);
        neighbor.g = abs(start_px - neighbor.row) + abs(start_py - neighbor.col);
        neighbor.h = abs(end_px - neighbor.row) + abs(end_py - neighbor.col);
    
    
        if dimNormal
            inCloseFlag = 0; 
            if closelen ==0
            else
                for j = 1:closelen
                    if close(j).row == neighbor.row && close(j).col ==neighbor.col
                        inCloseFlag = 1;
                        break;
                    end
                end
            end
        
            if inCloseFlag
                continue;
            end
            
            temp_g = current.g + abs(current.row - neighbor.row) + abs(current.col - neighbor.col);
            inOpenFlag = 0;
            for j =1:openlen
                if open(j).row == neighbor.row && open(j).col ==neighbor.col
                    inOpenFlag = 1;
                    break;
                end
            end        
            if ~inOpenFlag && map(neighbor.row,neighbor.col) ~= 1
                openlen = openlen + 1;
                open(openlen).row = neighbor.row;
                open(openlen).col = neighbor.col;
                open(openlen).g = abs(start_px - neighbor.row) + abs(start_py - neighbor.col);
                open(openlen).h = abs(end_px - neighbor.row) + abs(end_py - neighbor.col);               
            elseif temp_g >= neighbor.g
                continue;
            end
                backNum = backNum +1;
                prev(backNum,:) = [current.row ,current.col,neighbor.row ,neighbor.col];
                neighbor.g = temp_g;            
        else
            continue;
        end
    end     
end

生成初始图:
在这里插入图片描述

开始搜索

我们已经完成地图搜寻区域的准备工作,下面我们基于可以移动的四个动作(上、下、左、右)来进行搜索,我们使用openList来维护需要展开的待搜索的节点,在最开始的时候,只有起点这一项。之后,openList里面的元素可能是会经过的,也有可能是不经过的,但是经过的点都应该在openList中存在或者曾经存在。另外,对于我们已经访问过的点,我们使用closeList来进行记录,避免多次访问。

代价函数:
f(v) = g(v) + h(v)
g(v)表示由起始点到当前节点的最小cost;
h(v)表示由当前结点到目标节点的最小cost的估计值;
这里,为方便计算,笔者统一选取了曼哈顿距离用来计算g(v)和h(v)的cost值。

算法伪码:

function AStar_Routing(Gragh(V,E),src,dst)
	create vertex List openList
	create vertex List closeList
	create prev_map
	insert src into openList
	while(openList.isNotEmpty)
		current = the node v in openList s.t.  min(f[v]) in openList
		if current = dst
			return  reconstruction_route(prev_map,current)
		endif
		remove current from openList
		insert current into closeList
		for each neighbor u of current
			if u in closeList
				continue;
			endif
			temp_u = g[current] + h(current,u)
			if u not in openList
				insert u into openList
			elseif temp_u >= g[u]
				continue;
			endif
			prev_map[u] = current			
			g[u] = temp_cost
			f[u] = g[u] + h(current,dst)
	endwhile

回溯后,整体PATH效果如下:
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188079.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 简要说明continue命令和break命令的不同_continue的用法

    简要说明continue命令和break命令的不同_continue的用法break命令可以带一个参数,一个不带参数的break循环只能退出最内层的循环,而breakN可以退出N层循环。continue命令也可以带一个参数,一个不带参数的continue命令只去掉本次循环的剩余代码,而continueN将会把N层循环剩余的代码都去掉,但是循环的次数不变。#!/bin/shforiin”abcd”doech

  • 动态代理的两种方式以及优缺点

    动态代理的两种方式以及优缺点

  • matlab插值函数的作用,matlab 插值函数[通俗易懂]

    matlab插值函数的作用,matlab 插值函数[通俗易懂]MATLAB中的插值函数为interp1,其调用格式为:yi=interp1(x,y,xi,’method’)其中x,y为插值点,yi为在被插值点xi处的插值结果;x,y为向量,’method’表示采用的插值方法,MATLAB提供的插值方法有几种:’method’是最邻近插值,’linear’线性插值;’spline’三次样条插值;’cubic’立方插值.缺省时表示线性插值注意:所…

  • 网络爬虫必备知识之concurrent.futures库

    1.concurrent.futures库简介python标准库为我们提供了threading和mutiprocessing模块实现异步多线程/多进程功能。从python3.2版本开始,标准库又为

    2021年12月29日
  • Word 在试图打开文件时遇到错误 文档可能已损坏 解决方法

    Word 在试图打开文件时遇到错误 文档可能已损坏 解决方法我使用的是Office2019的Word打开后缀名为doc的文件。错误信息:有多种原因可导致显示此错误消息。文档可能已损坏。请使用“恢复文本”转换器或“打开并修复”功能。这两种功能都可在“打开”对话框中找到。注意:如果打开的文件是电子邮件的附件,建议先将该文件保存到本地硬盘,然后再尝试恢复或修复该文件。可在“打开”对话框中使用“打开并修复”功能。若要打开并尝试修复,请单击“文件”选项卡,再单击“打开”,然后定位到损坏的文件并单击该文件。此时不要单击对话框右下部的“打开”按钮,而

  • Word在试图打开文件时遇到错误请尝试下列方法 *检查文档或驱动器的文件权限*确保有足够的内存和磁盘空间,…[通俗易懂]

    Word在试图打开文件时遇到错误请尝试下列方法 *检查文档或驱动器的文件权限*确保有足够的内存和磁盘空间,…[通俗易懂]可能存在两种可能:下载保存过程中,该文件损坏,导致无法打开;文件安全性问题,可以打开Word2013或Excel2013,依次点击“文件→选项→信任中心→信任中心设置→受保护的视图”,取消受保护的视图标签下的三个复选框的勾选,或者通过简单的操作解除某个文件的锁定。右键点击您的Word文档并点击属性,在文件的属性窗口中,点击“解除锁定。 转载于:https://b…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号