自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

Java版A星算法實現(xiàn)步驟

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

A星算法步驟：

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

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

判斷此節(jié)點是否是目標(biāo)點，是則找到了，跳出，

根據(jù)此節(jié)點取得八個方向的節(jié)點，求出G，H，F(xiàn)值，

判斷每個節(jié)點在地圖中是否能通過，不能通過則加入關(guān)閉列表中，跳出判斷每個節(jié)點是否在關(guān)閉列表中，在則跳出，

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

3.把此節(jié)點從開啟列表中刪除，再添加到關(guān)閉列表中。

4.把開啟列表中按照F值最小的節(jié)點進(jìn)行排序，最小的F值在***個。

5.重復(fù)2，3，4步驟，

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

  1. //A*算法public class AStar {  
  2.     private int[][] map;//地圖(1可通過 0不可通過)  
  3.     private List<Node> openList;//開啟列表  
  4.     private List<Node> closeList;//關(guān)閉列表  
  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.         //查找坐標(biāo)（-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.             //判斷是否找到目標(biāo)點  
  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.             //添加到關(guān)閉列表中  
  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.         //查找關(guān)閉列表中是否存在  
  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(xiàn)值  
  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.     }//節(jié)點類class Node {  
  156.     private int x;//X坐標(biāo)  
  157.     private int y;//Y坐標(biāo)  
  158.     private Node parentNode;//父類節(jié)點  
  159.     private int g;//當(dāng)前點到起點的移動耗費  
  160.     private int h;//當(dāng)前點到終點的移動耗費，即曼哈頓距離|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.     }}//節(jié)點比較類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. // 地圖數(shù)組
  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("傳輸數(shù)據(jù)有誤！");  
  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內(nèi)存溢出總結(jié)
  2. Java NIO如何處理慢速的連接
  3. Java數(shù)據(jù)緩存實現(xiàn)的核心機制
  4. Java與Cobol對決：Cobol軟件質(zhì)量最過硬
  5. Java NIO類庫關(guān)系圖解
責(zé)任編輯：林師授 來源： 塵鋒的博客
java
相關(guān)推薦

2020-05-19 14:27:10

GitHubPythonAI算法

2011-04-20 10:58:34

Java

2023-06-13 06:51:09

Spark機器學(xué)習(xí)回歸

2020-08-21 13:41:04

代碼開發(fā)工具

2019-08-12 08:43:53

GitHub代碼開發(fā)者

2011-10-17 10:15:12

iMessageChatON三星

2010-06-08 10:34:23

opensuse 10

2018-03-07 15:27:57

三星筆記本

2010-06-09 11:05:48

Opensuse安裝m

2010-06-04 16:47:49

實現(xiàn)Hadoop

2010-06-09 09:33:41

Opensuse硬盤

2017-02-09 16:16:24

Java負(fù)載均衡算法

2015-07-29 10:31:16

Java緩存算法

2023-06-25 07:42:02

2020-04-14 15:00:04

PyTorchGitHub檢測

2014-11-28 20:05:13

星環(huán)Hadoop發(fā)行版

2010-09-09 08:52:19

JavascriptDIV

2010-07-22 13:23:46

telnet SMTP

2020-07-30 07:52:13

JavaLRU算法
點贊
收藏

51CTO技術(shù)棧公眾號