成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

Java版A星算法實現步驟

作者：塵鋒
開發 后端 算法
A星算法步驟：1.起點先添加到開啟列表中；2.開啟列表中有節點的話，取出第一個節點，即最小F值的節點……

A星算法步驟：

1.起點先添加到開啟列表中。

2.開啟列表中有節點的話，取出***個節點，即最小F值的節點，

判斷此節點是否是目標點，是則找到了，跳出，

根據此節點取得八個方向的節點，求出G，H，F值，

判斷每個節點在地圖中是否能通過，不能通過則加入關閉列表中，跳出判斷每個節點是否在關閉列表中，在則跳出，

判斷每個節點是否在開啟列表中，在則更新G值，F值，還更新其父節點；不在則將其添加到開啟列表中，計算G值，H值，F值，添加其節點。

3.把此節點從開啟列表中刪除，再添加到關閉列表中。

4.把開啟列表中按照F值最小的節點進行排序，最小的F值在***個。

5.重復2，3，4步驟，

直到目標點在開啟列表中，即找到了；目標點不在開啟列表中，開啟列表為空，即沒找到。

  1. //A*算法public class AStar {  
  2.     private int[][] map;//地圖(1可通過 0不可通過)  
  3.     private List<Node> openList;//開啟列表  
  4.     private List<Node> closeList;//關閉列表  
  5.     private final int COST_STRAIGHT = 10;//垂直方向或水平方向移動的路徑評分  
  6.     private final int COST_DIAGONAL = 14;//斜方向移動的路徑評分  
  7.     private int row;//行  
  8.     private int column;//列  
  9.         public AStar(int[][] map,int row,int column){  
  10.         this.map=map;  
  11.         this.row=row;  
  12.         this.column=column;  
  13.         openList=new ArrayList<Node>();  
  14.         closeList=new ArrayList<Node>();  
  15.     }  
  16.         //查找坐標（-1：錯誤，0：沒找到，1：找到了）  
  17.     public int search(int x1,int y1,int x2,int y2){  
  18.         if(x1<0||x1>=row||x2<0||x2>=row||y1<0||y1>=column||y2<0||y2>=column){  
  19.               
  20. return -1;  
  21.         }  
  22.         if(map[x1][y1]==0||map[x2][y2]==0){            return -1;  
  23.         }  
  24.         Node sNode=new Node(x1,y1,null);  
  25.         Node eNode=new Node(x2,y2,null);        openList.add(sNode);  
  26.         List<Node> resultList=search(sNode, eNode);  
  27.         if(resultList.size()==0){  
  28.             return 0;  
  29.         }  
  30.         for(Node node:resultList){  
  31.             map[node.getX()][node.getY()]=-1;  
  32.         }  
  33.         return 1;  
  34.     }  
  35.         //查找核心算法  
  36.     private List<Node> search(Node sNode,Node eNode){  
  37.         List<Node> resultList=new ArrayList<Node>();  
  38.         boolean isFind=false;  
  39.         Node node=null;  
  40.         while(openList.size()>0){  
  41.             //取出開啟列表中***F值，即***個存儲的值的F為***的  
  42.             node=openList.get(0);  
  43.             //判斷是否找到目標點  
  44.             if(node.getX()==eNode.getX()&&node.getY()==eNode.getY()){  
  45.                 isFind=true;  
  46.                 break;  
  47.             }  
  48.             //上  
  49.             if((node.getY()-1)>=0){                checkPath(node.getX(),node.getY()-1,node, eNode, COST_STRAIGHT);  
  50.             }  
  51.             //下  
  52.             if((node.getY()+1)<column){  
  53.                 checkPath(node.getX(),node.getY()+1,node, eNode, COST_STRAIGHT);  
  54.             }  
  55.             //左  
  56.             if((node.getX()-1)>=0){  
  57.                 checkPath(node.getX()-1,node.getY(),node, eNode, COST_STRAIGHT);  
  58.             }  
  59.             //右  
  60.             if((node.getX()+1)<row){  
  61.                 checkPath(node.getX()+1,node.getY(),node, eNode, COST_STRAIGHT);  
  62.             }  
  63.             //左上  
  64.             if((node.getX()-1)>=0&&(node.getY()-1)>=0){  
  65.                 checkPath(node.getX()-1,node.getY()-1,node, eNode, COST_DIAGONAL);  
  66.             }  
  67.             //左下  
  68.             if((node.getX()-1)>=0&&(node.getY()+1)<column){  
  69.                 checkPath(node.getX()-1,node.getY()+1,node, eNode,COST_DIAGONAL);  
  70.             }  
  71.             //右上  
  72.             if((node.getX()+1)<row&&(node.getY()-1)>=0){                checkPath(node.getX()+1,node.getY()-1,node, eNode, COST_DIAGONAL);  
  73.             }  
  74.             //右下  
  75.             if((node.getX()+1)<row&&(node.getY()+1)<column){  
  76.                 checkPath(node.getX()+1,node.getY()+1,node, eNode, COST_DIAGONAL);  
  77.             }  
  78.             //從開啟列表中刪除  
  79.             //添加到關閉列表中  
  80.             closeList.add(openList.remove(0));  
  81.             //開啟列表中排序，把F值***的放到***端            Collections.sort(openList, new NodeFComparator());  
  82.         }  
  83.         if(isFind){  
  84.             getPath(resultList, node);  
  85.         }  
  86.         return resultList;  
  87.     }  
  88.         //查詢此路是否能走通  
  89.     private boolean checkPath(int x,int y,Node parentNode,Node eNode,int cost){  
  90.         Node node=new Node(x, y, parentNode);  
  91.         //查找地圖中是否能通過  
  92.         if(map[x][y]==0){  
  93.             closeList.add(node);  
  94.             return false;  
  95.         }  
  96.         //查找關閉列表中是否存在  
  97.         if(isListContains(closeList, x, y)!=-1){  
  98.             return false;  
  99.         }  
  100.         //查找開啟列表中是否存在  
  101.         int index=-1;  
  102.         if((index=isListContains(openList, x, y))!=-1){  
  103.             //G值是否更小，即是否更新G，F值  
  104.             if((parentNode.getG()+cost)<openList.get(index).getG()){  
  105.                 node.setParentNode(parentNode);  
  106.                 countG(node, eNode, cost);  
  107.                 countF(node);  
  108.                 openList.set(index, node);  
  109.             }  
  110.         }else{  
  111.             //添加到開啟列表中  
  112.             node.setParentNode(parentNode);            count(node, eNode, cost);  
  113.             openList.add(node);  
  114.         }  
  115.         return true;  
  116.     }  
  117.         //集合中是否包含某個元素(-1：沒有找到，否則返回所在的索引)  
  118.     private int isListContains(List<Node> list,int x,int y){  
  119.         for(int i=0;i<list.size();i++){  
  120.             Node node=list.get(i);  
  121.             if(node.getX()==x&&node.getY()==y){  
  122.                 return i;  
  123.             }  
  124.         }  
  125.         return -1;  
  126.     }  
  127.         //從終點往返回到起點  
  128.     private void getPath(List<Node> resultList,Node node){  
  129.         if(node.getParentNode()!=null){            getPath(resultList, node.getParentNode());  
  130.         }  
  131.         resultList.add(node);  
  132.     }  
  133.         //計算G,H,F值  
  134.     private void count(Node node,Node eNode,int cost){  
  135.         countG(node, eNode, cost);  
  136.         countH(node, eNode);  
  137.         countF(eNode);  
  138.     }  
  139.     //計算G值  
  140.     private void countG(Node node,Node eNode,int cost){  
  141.         if(node.getParentNode()==null){  
  142.             node.setG(cost);  
  143.         }else{  
  144.             node.setG(node.getParentNode().getG()+cost);  
  145.         }  
  146.     }  
  147.     //計算H值  
  148.     private void countH(Node node,Node eNode){  
  149.         node.setF(Math.abs(node.getX()-eNode.getX())+Math.abs(node.getY()-eNode.getY()));  
  150.     }  
  151.     //計算F值  
  152.     private void countF(Node node){  
  153.         node.setF(node.getG()+node.getF());  
  154.     }  
  155.     }//節點類class Node {  
  156.     private int x;//X坐標  
  157.     private int y;//Y坐標  
  158.     private Node parentNode;//父類節點  
  159.     private int g;//當前點到起點的移動耗費  
  160.     private int h;//當前點到終點的移動耗費，即曼哈頓距離|x1-x2|+|y1-y2|(忽略障礙物)  
  161.     private int f;//f=g+h  
  162.         public Node(int x,int y,Node parentNode){        this.x=x;  
  163.         this.y=y;  
  164.         this.parentNode=parentNode;  
  165.     }  
  166.         public int getX() {  
  167.         return x;  
  168.     }  
  169.     public void setX(int x) {  
  170.         this.x = x;  
  171.     }  
  172.     public int getY() {  
  173.         return y;  
  174.     }  
  175.     public void setY(int y) {  
  176.         this.y = y;  
  177.     }  
  178.     public Node getParentNode() {  
  179.         return parentNode;  
  180.     }  
  181.     public void setParentNode(Node parentNode) {  
  182.         this.parentNode = parentNode;  
  183.     }  
  184.     public int getG() {  
  185.         return g;  
  186.     }  
  187.     public void setG(int g) {  
  188.         this.g = g;  
  189.     }  
  190.     public int getH() {  
  191.         return h;  
  192.     }  
  193.     public void setH(int h) {  
  194.         this.h = h;  
  195.     }  
  196.     public int getF() {  
  197.         return f;  
  198.     }  
  199.     public void setF(int f) {  
  200.         this.f = f;  
  201.     }}//節點比較類class NodeFComparator implements Comparator<Node>{  
  202.     @Override 
  203.     public int compare(Node o1, Node o2) {  
  204.         return o1.getF()-o2.getF();  
  205.     }  
  206.     }  

 測試類：

  1. public class Test {  
  2.         public static void main(String[] args){
  3.         int[][] map=new int[][]{
  4. // 地圖數組
  5.                 {1,1,1,1,1,1,1,1,1,1},
  6.                 {1,1,1,1,0,1,1,1,1,1},
  7.                 {1,1,1,1,0,1,1,1,1,1},
  8.                 {1,1,1,1,0,1,1,1,1,1},
  9.                 {1,1,1,1,0,1,1,1,1,1},
  10.                 {1,1,1,1,0,1,1,1,1,1}  
  11.         };  
  12.         AStar aStar=new AStar(map, 6, 10);  
  13.         int flag=aStar.search(4, 0, 3, 8);  
  14.         if(flag==-1){  
  15.             System.out.println("傳輸數據有誤！");  
  16.         }else if(flag==0){  
  17.             System.out.println("沒找到！");  
  18.         }else{  
  19.             for(int x=0;x<6;x++){  
  20.                 for(int y=0;y<10;y++){
  21.                     if(map[x][y]==1){
  22.                         System.out.print("　");
  23.                     }else if(map[x][y]==0){
  24.                         System.out.print("〓");
  25.                     }else if(map[x][y]==-1){
  26.                         System.out.print("※");  
  27.                     }  
  28.                 }  
  29.                 System.out.println();  
  30.             }  
  31.         }  
  32.     }} 

原文鏈接：http://www.cnblogs.com/xmmdream/archive/2011/12/12/2284627.html

【編輯推薦】

  1. Tomcat運行Java Web內存溢出總結
  2. Java NIO如何處理慢速的連接
  3. Java數據緩存實現的核心機制
  4. Java與Cobol對決：Cobol軟件質量最過硬
  5. Java NIO類庫關系圖解
責任編輯：林師授 來源： 塵鋒的博客
java
相關推薦

2020-05-19 14:27:10

GitHubPythonAI算法

2020-08-21 13:41:04

代碼開發工具

2011-04-20 10:58:34

Java

2019-08-12 08:43:53

GitHub代碼開發者

2011-10-17 10:15:12

iMessageChatON三星

2010-06-08 10:34:23

opensuse 10

2018-03-07 15:27:57

三星筆記本

2023-06-13 06:51:09

Spark機器學習回歸

2023-06-25 07:42:02

2010-06-09 11:05:48

Opensuse安裝m

2010-06-04 16:47:49

實現Hadoop

2010-06-09 09:33:41

Opensuse硬盤

2020-04-14 15:00:04

PyTorchGitHub檢測

2014-11-28 20:05:13

星環Hadoop發行版

2015-07-29 10:31:16

Java緩存算法

2017-02-09 16:16:24

Java負載均衡算法

2020-07-30 07:52:13

JavaLRU算法

2010-09-09 08:52:19

JavascriptDIV

2010-07-22 13:23:46

telnet SMTP
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板： 北条麻妃一区二区三区在线视频 | 日韩精品一区二区三区 | 日韩a级片 | 国产日韩视频 | 欧美一级视频免费看 | 亚洲一区不卡 | 久久色视频 | 午夜丰满少妇一级毛片 | 美女视频一区 | www久久久 | 欧美一页 | 国产精品日韩欧美一区二区三区 | 日韩欧美三级 | 国产精品一区二区视频 | 精品国产乱码久久久久久图片 | 亚洲国产精品一区二区第一页 | 国产精品视频导航 | 免费福利视频一区二区三区 | 国产成人精品久久二区二区91 | 一级片网址 | 91精品国产综合久久久久蜜臀 | 国产精品视频久久 | 97超碰在线播放 | 99热首页 | 午夜免费av | 国产一级片一区二区三区 | 国产精品国产三级国产aⅴ无密码 | 91青青草视频 | 久久精品亚洲精品国产欧美 | 精品一区二区三区中文字幕 | 中文字幕第十五页 | 欧美成人手机视频 | 精品国产一区二区三区性色av | 少妇无套高潮一二三区 | 精品欧美一区免费观看α√ | 亚洲一区中文字幕 | 亚洲激情视频在线 | 欧美激情综合色综合啪啪五月 | 免费在线观看毛片 | 国产乱码高清区二区三区在线 | 欧美精品一区二区三区在线播放 |