1、問題

用A*搜尋算法實作路徑搜尋，并将路徑搜尋的最終結果儲存至檔案中

2、算法标簽

1、A*搜尋

3、實作代碼

1>接口類

package ai;

import java.io.File;
import java.util.List;

class Status{
	public char mp[][];
	public int tempx,tempy;
	public int fromx,fromy;
	public int tox,toy;
	public Status parent;
	public int distance;
	Status(){
		mp=new char[30][70];
	}
}

public interface A_start {
	public void getInitStatus();        // 擷取初始狀态
	public void showStatus(char mp[][]);    //輸出目前狀态内部表示
	public int getFValue(Status statu);     //擷取目前節點啟發函數值
	public boolean isExist(Status now);     //是否狀态s與目前狀态相同
	public void saveAnswer(char mp1[][],char mp2[][],int flag);
}

2>接口實作類

package ai;


import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.security.CodeSource;
import java.security.ProtectionDomain;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class PathSearch implements A_start{
	public List<Status> used = new ArrayList<Status>();
	public List<Status> unused = new ArrayList<Status>();
	public Status start = new Status();
		
	public void copy(Status newone,Status oldone) {
		for(int i=0;i<30;i++) { 
			for(int j=0;j<70;j++) {
				newone.mp[i][j]=oldone.mp[i][j];
			}
		}
		newone.tempx=oldone.tempx;
		newone.tempy=oldone.tempy;
		newone.fromx=oldone.fromx;
		newone.fromy=oldone.fromy;
		newone.tox=oldone.tox;
		newone.toy=oldone.toy;
	}
	
	public void getInitStatus() {
		Random random = new Random();
		for(int i=0;i<30;i++) {
			for(int j=0;j<70;j++) {
				this.start.mp[i][j]='=';
			}
		}
		Scanner input=new Scanner(System.in);
		System.out.print("請自定義障礙數（0-29998）:");
		int obstacles=input.nextInt(); 
		if(0>obstacles||obstacles>29998) {
			System.out.println("錯誤輸入,自定義為200！");
			obstacles=200;
		}
		for(int t=0;t<obstacles;t++) {
			int rx = random.nextInt(30);
			int ry = random.nextInt(70);
			this.start.mp[rx][ry]='O';
		}
		this.start.fromx = random.nextInt(30);
		this.start.tempx = this.start.fromx;
		this.start.fromy = random.nextInt(70);
		this.start.tempy = this.start.fromy;
		this.start.mp[this.start.fromx][this.start.fromy]='F';
		this.start.tox = random.nextInt(30);
		this.start.toy = random.nextInt(70);
		this.start.mp[this.start.tox][this.start.toy]='T';
		this.start.distance=getFValue(this.start);
		this.start.parent=this.start;
	}
	
	public int getFValue(Status statu) {
		return Math.abs(statu.tempx-statu.tox)+Math.abs(statu.tempy-statu.toy);
	}
	
	public void showStatus(char mp[][]) {
		System.out.println("===============================目前狀态===============================");
		System.out.println("                   X:障礙,F:起點,T:終點,V:路徑,O:道路");
		for(int i=0;i<30;i++) { 
			for(int j=0;j<70;j++) {
				System.out.print(mp[i][j]);
			}
			System.out.println("");
		}
	}

	public boolean isExist(Status now) {
		for(int i=0;i<this.used.size();i++) {
			Status temp=this.used.get(i);
			int j=0;
			for(;j<2100;j++) {
				int r=j/70;
				int c=j%70;
				if(now.mp[r][c]!=temp.mp[r][c]) {
					break;
				}
			}
			if(j==2100&&now.tempx==temp.tempx&&now.tempy==temp.tempy) {
				return true;
			}
		}
		for(int i=0;i<this.unused.size();i++) {
			Status temp=this.unused.get(i);
			int j=0;
			for(;j<2100;j++) {
				int r=j/70;
				int c=j%70;
				if(now.mp[r][c]!=temp.mp[r][c]) {
					break;
				}
			}
			if(j==2100&&now.tempx==temp.tempx&&now.tempy==temp.tempy) {
				return true;
			}
		}
		return false;
	}
	
	public void saveAnswer(char mp1[][],char mp2[][],int flag) {
		 try { 
			String name="E:/Astar路徑搜尋問題解決方案.txt";  
            BufferedWriter out = new BufferedWriter(new FileWriter(name));
            out.write("路徑搜尋問題：");
            out.newLine();
            out.write("X:障礙,F:起點,T:終點,V:路徑,O:道路");
            out.newLine();
            for(int i=0;i<30;i++) {
            	String q="";
            	for(int j=0;j<70;j++) {
            		q=q+mp1[i][j];
            	}
            	out.write(q);
                out.newLine();
            }
            out.write("解決方案：");
            out.newLine();
            if(flag==0) {
            	out.write("此題在移動最大99999999步數内無解");
            }
            else {
            	for(int i=0;i<30;i++) {
                	String q="";
                	for(int j=0;j<70;j++) {
                		q=q+mp2[i][j];
                	}
                	out.write(q);
                    out.newLine();
                }
            }
            out.close();
            System.out.println("問題解決方案寫入成功,檔案儲存在E盤根目錄");
        } catch (IOException e) {
        	System.out.println("問題解決方案寫入或儲存失敗");
        }
	}
	
	public static void main(String[] args) {
		System.out.println("A* 路徑搜尋算法實作 ————made by 張玉想（計科一班 | 202820240106）");
		PathSearch ps = new PathSearch();
        ps.getInitStatus();
        ps.unused.add(ps.start);
        int step=0;
        int flag=0;
        while(step<99999999&&ps.unused.size()>0) {
        	Status temp=ps.unused.get(0);
        	ps.showStatus(temp.mp);
        	ps.unused.remove(0);
        	ps.used.add(temp);
        	if(temp.tempx-1>=0) {
        		Status news=new Status();
        		ps.copy(news,temp);
        		if(news.mp[temp.tempx-1][temp.tempy]=='=') {
        			news.mp[temp.tempx-1][temp.tempy]='V';
        			news.tempx=temp.tempx-1;
        			news.distance=ps.getFValue(news);
        			ps.showStatus(news.mp);
        			if(!ps.isExist(news)) {
        				news.parent=temp;
        				ps.unused.add(news);
        				step++;
        			}
        		}
        		else if(news.mp[news.tempx-1][news.tempy]=='T') {
        			news.tempx=news.tempx-1;
        			ps.showStatus(news.mp);
        			ps.unused.clear();
        			flag=1;
        			ps.saveAnswer(temp.mp,news.mp,flag);
        			break;
        		}
        	}
        	if(temp.tempx+1<30) {
        		Status news=new Status();
        		ps.copy(news,temp);
        		if(news.mp[news.tempx+1][news.tempy]=='=') {
        			news.mp[news.tempx+1][news.tempy]='V';
        			news.tempx=news.tempx+1;
        			news.distance=ps.getFValue(news);
        			if(!ps.isExist(news)) {
        				news.parent=temp;
        				ps.unused.add(news);
        				step++;
        			}
        		}
        		else if(news.mp[news.tempx+1][news.tempy]=='T') {
        			news.tempx=news.tempx+1;
        			ps.showStatus(news.mp);
        			ps.unused.clear();
        			flag=1;
        			ps.saveAnswer(temp.mp,news.mp,flag);
        			break;
        		}
        	}
        	if(temp.tempy-1>=0) {
        		Status news=new Status();
        		ps.copy(news,temp);
        		if(news.mp[news.tempx][news.tempy-1]=='=') {
        			news.mp[news.tempx][news.tempy-1]='V';
        			news.tempy=news.tempy-1;
        			news.distance=ps.getFValue(news);
        			if(!ps.isExist(news)) {
        				news.parent=temp;
        				ps.unused.add(news);
        				step++;
        			}
        		}
        		else if(news.mp[news.tempx][news.tempy-1]=='T') {
        			news.tempy=news.tempy-1;
        			ps.showStatus(news.mp);
        			ps.unused.clear();
        			flag=1;
        			ps.saveAnswer(temp.mp,news.mp,flag);
        			break;
        		}
        	}
        	if(temp.tempy+1<70) {
        		Status news=new Status();
        		ps.copy(news,temp);
        		if(news.mp[news.tempx][news.tempy+1]=='=') {
        			news.mp[news.tempx][news.tempy+1]='V';
        			news.tempy=news.tempy+1;
        			news.distance=ps.getFValue(news);
        			if(!ps.isExist(news)) {
        				news.parent=temp;
        				ps.unused.add(news);
        				step++;
        			}
        		}
        		else if(news.mp[news.tempx][news.tempy+1]=='T') {
        			news.tempy=news.tempy+1;
        			ps.showStatus(news.mp);
        			ps.unused.clear();
        			flag=1;
        			ps.saveAnswer(temp.mp,news.mp,flag);
        			break;
        		}
        	}
        	Collections.sort(ps.unused, new Comparator<Status>() {
        		public int compare(Status u1, Status u2) {
        			int diff = u1.distance-u2.distance;
        			if (diff > 0) {
        				return 1;
        			}
        			else if (diff < 0) {
        				return -1;
        			}
        			return 0;
        		}
        	});
        }
        System.out.println("                   --------------------------------");
        System.out.println("                   ----       A*模拟搜尋結束        ----");
        System.out.println("                   ----       made by 張玉想       ----");
        System.out.println("                   --------------------------------");
        if(flag==0) {
        	ps.saveAnswer(ps.used.get(0).mp,ps.used.get(0).mp,flag);
        }
    }
}

4、代碼運作截圖

A*路徑搜尋算法1、問題2、算法标簽3、實作代碼4、代碼運作截圖

A*路徑搜尋算法1、問題2、算法标簽3、實作代碼4、代碼運作截圖

A*路徑搜尋算法

1、問題

2、算法标簽

3、實作代碼

1>接口類

2>接口實作類

4、代碼運作截圖

繼續閱讀

K-近鄰算法以及圖像分類應用

小i機器人受邀赴韓交流，CFO首爾亞洲金融論壇演講

吳恩達deeplearning

吳恩達logistic回歸實作

【人工智能行業大師訪談1】吳恩達采訪 Geoffery Hinton

吳恩達機器學習筆記（3）

吳恩達j機器學習之過拟合

吳恩達機器學習(一) 介紹

深度學習模型分析人類複雜疾病的準确性

疾病研究：重症肌無力

人工智能如何有效地運用于自然語言處理

新聞 | Mapbox 牽手阿裡，飛豬旅行上線六大城市地圖功能

[HTML5]自定義屬性 data-* 和 jQuery.data 詳解

2021-2025年中國運動療法（KT）帶行業市場供需與戰略研究報告

2021年危險化學品經營機關安全管理人員考試題庫及危險化學品經營機關安全管理人員考試技巧

無人機--飛控科普