A*搜索算法实现实例（城市最短路径）

迈不过友情╰ 2023-07-17 04:47 73阅读 0赞

## A\*搜索算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 4]

## 实例：城市最短路径代码实现 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 5]

public class InformedSearch {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		
    		String[] cities = {
    				"1号","2号","3号","4号","5号","6号","7号","8号"	
    		};
    		// 数组模拟图,数组下标为城市对应下标，如distance[0][1]对应cities[0],cities[1],数组值为城市间直线距离
    		int[][] distance =  {
    			{0,3,7,9,1,4,3,8},
    			{3,0,5,7,4,6,5,7},
    			{7,5,0,4,7,10,8,9},
    			{9,7,4,0,5,7,9,9},
    			{1,4,7,5,0,4,1,7},
    			{4,6,10,7,4,0,2,4},
    			{3,5,8,9,1,4,0,6},
    			{8,7,9,9,7,4,6,0}
    		};
    		// 表示城市间是否相连
    		boolean[][] isconnect = {
    				{true,true,false,false,true,false,false,false},
    				{true,true,true,true,false,false,false,false},
    				{false,true,true,false,false,false,false,true},
    				{false,true,false,true,false,false,false,true},
    				{true,false,false,false,true,true,true,false},
    				{false,false,false,false,true,true,false,true},
    				{false,false,false,false,true,false,true,true},
    				{false,false,true,true,false,true,true,true}
    		};
    		
    		FindRoad find = new FindRoad("4号","5号"); // 起始城市，目标城市
    		find.setroad(cities, distance, isconnect);
    		find.print();
    	}
    
    }
    
    class FindRoad{
    	
    	private String startcity; 
    	private String endcity; // 目标城市
    	private City root; // 链表模拟路径
    	private int endnum; // 目标城市下标
    	private int sumlong = 0;
    	
    	// 构造器
    	public FindRoad(String startcity,String endcity)
    	{
    		this.startcity = startcity;
    		this.endcity = endcity;
    	}
    	
    	// 打印
    	public void print()
    	{
    		City temp = root;
    		while(temp!=null)
    		{
    			temp.print();
    			temp = temp.next;
    		}
    		System.out.println("总里程 ="+sumlong+"km");
    	}
    	
    	// 设置路径
    	public void setroad(String[] cities,int[][] distance,boolean[][] isconnect)
    	{
    		root = new City(startcity); // 建立头节点
    		this.endnum = findend(cities); // 找到目标城市对应下标
    		if(endnum == -1) // 若为 -1 则为找到相应城市
    		{
    			return;
    		}
    		City temp = root; // 临时节点
    		while(true)
    		{
    			int n = findcity(cities,distance,isconnect); // 找到下一个要到达城市下标
    			City t = new City(cities[n]); // 创建城市节点
    			temp.next = t; // 连接节点
    			temp = t; // 移动临时节点
    			this.startcity = cities[n]; // 改变下一个节点为新的起始节点
    			if(cities[n].equals(this.endcity)) // 是否到达目标城市
    			{
    				break;
    			}
    		}
    		
    	}
    	
    	// 查找目标城市下标
    	private int findend(String[] cities)
    	{
    		for(int i=0;i<cities.length;i++)
    		{
    			if(cities[i].equals(this.endcity))
    			{
    				return i;
    			}
    		}
    		return -1;
    	}
    	
    	// 根据评价函数查找最优节点
    	private int findcity(String[] cities,int[][] distance,boolean[][] isconnect)
    	{
    		int k = 0;
    		int n = 0;
    		int sum = Integer.MAX_VALUE;
    		//查找起始节点下标
    		for(int i=0;i<cities.length;i++)
    		{
    			if(cities[i].equals(this.startcity))
    			{
    				k = i;
    			}
    		}
    		// 评价函数实现
    		for(int i=0;i<distance[k].length;i++)
    		{
    			// g(n)=distance[k][i]，h(n)=distance[this.endnum][i]
    			if(distance[k][i]!=0 && isconnect[k][i] == true && (distance[k][i]+distance[this.endnum][i])<sum)
    			{
    				n = i;
    				// f(n) = sum
    				sum = distance[k][i]+distance[this.endnum][i];
    			}
    		}
    		
    		this.sumlong += distance[k][n]; // 里程数
    		
    		return n;
    	}
    	
    }
    // 城市节点类
    class City{
    	private String name;
    	public City next;
    	public City(String name)
    	{
    		this.name = name;
    	}
    	public void print()
    	{
    		System.out.print(name+"->");
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70]: /images/20230528/557fc541b0fe401ca2b5aca24735b00d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 1]: /images/20230528/84f30300c19a443dbce3b3071ca2f0ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 2]: /images/20230528/e94a72a6f7fd496285934de4ce315541.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 3]: /images/20230528/acdb457d5da2420593f85933016728d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 4]: /images/20230528/5b5b868f53f14b2d8e7d4929536f6acd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70 5]: /images/20230528/3321b6ec7dcb417594dddb658cb95f7f.png