머리말
A* 검색 알고리즘은 일반적으로 A-Star 알고리즘으로 알려져 있습니다. 이것은 가장 낮은 통과 비용을 찾기 위해 그래프 평면에 여러 노드가있는 알고리즘입니다. 게임에서 일반적으로 사용됩니다
2 차원 배열을 통해 구성된 미로, "%"는 벽을 나타내고, a는 시작점, B는 종점, "#"는 장애물을 나타내며, "*"는 알고리즘에 의해 계산 된 경로를 나타냅니다.
이 기사의 코드 구조 :
% % % % % % % % % oooo % oo % oo % % a o # o b % oo # oo % oo % oober % % % % % % =========================================================================================================== oo * oo % % o * # * o % % a o # o b % oo # oo % oo % oo % % % % % % % % <
알고리즘 이론
알고리즘의 핵심 공식은 다음과 같습니다. f = g+h
지도의 노드를 그리드로 생각하십시오.
g = 생성 된 경로를 따라 시작점 A에서 그리드의 지정된 노드로 이동하는 이동 소비. 이 예에서는 수평 또는 수직 이동 비용 10과 대각선 방향 비용 14를 만듭니다. 우리는 대각선을 따라 있기 때문에 이러한 값을 취합니다.
거리는 루트 번호 2 또는 수평 또는 수직으로 이동하는 데 걸리는 양의 약 1.414 배입니다. 단순화를 위해 10과 14를 사용하여 근사합니다.
우리는 특정 경로를 따라 제곱으로 이어지는 g 값을 계산하기 때문에 평가 방법은 모 노드의 G 값을 취한 다음 부모 노드에 비해 대각선 방향 또는 직각 (비 데일 기준)에 따라 각각 14 및 10을 추가하는 것입니다. 예에서는 이것입니다
시작 그리드 외부에서 하나 이상의 정사각형을 얻었 기 때문에 각 방법에 대한 수요는 더욱 커집니다.
h = 현재 그리드에서 엔드 포인트 B까지 추정 된 이동 소비. 왜 "추정"이라고 불리는 이유는 무엇입니까? 경로의 길이를 미리 알 수있는 방법이 없기 때문입니다. 여기서 우리는 현재 그리드에서 대상 그리드까지 수평 및 수직을 계산하는 맨해튼 방법을 사용합니다.
대각선 방향을 무시하고 사각형의 제곱 수의 합. 그런 다음 결과에 10을 곱하십시오.
F의 값은 G와 H의 합으로 우선 순위 경로를 판단하는 데 사용하는 표준입니다. F 값이 가장 작은 그리드는 우선 순위 경로 노드로 간주됩니다.
구현 단계
알고리즘은 Java로 작성되었으며 먼저 노드 클래스의 내용을보십시오.
패키지 a_star_search; / ** * 노드 클래스 * @author zx * */ public class node {private int x; // x 비공개 in y; // y 개인 문자열 값을 조정합니다. // 노드의 값 비공개 이중 fvalue = 0; // f 값 비공개 이중 gvalue = 0; // g 값 비공개 이중 hvalue = 0; // H 가치 개인 부울 도달 가능; // 도달 할 수 있습니까 (장애물입니까) 개인 노드 Pnode; // 상위 노드 공개 노드 (int x, int y, 문자열 값, 부울 도달 가능) {super (); this.x = x; this.y = y; this.value = value; 도달 가능 = 도달 가능; } public node () {super (); } public int getx () {return x; } public void setx (int x) {this.x = x; } public int gety () {return y; } public void sety (int y) {this.y = y; } public String getValue () {return 값; } public void setValue (문자열 값) {this.value = value; } public double getfvalue () {return fvalue; } public void setfvalue (double fvalue) {fvalue = fvalue; } public double getGvalue () {return gvalue; } public void setgvalue (double gvalue) {gvalue = gvalue; } public double gethvalue () {return hvalue; } public void sethvalue (double hvalue) {hvalue = hvalue; } public boolean isreachable () {리턴 도달 가능; } public void setreachable (부울 도달 가능) {도달 가능 = 도달 가능; } public node getPnode () {return pnode; } public void setpnode (노드 pnode) {pnode = pnode; }}또한지도 클래스가 필요합니다. MAP 구성 방법에서는 시작 및 엔드 포인트를 포함하는 2 차원 노드 배열을 만들어 미로 맵을 구현합니다.
패키지 a_star_search; public class map {private node [] [] map; // 노드 배열 비공개 노드 startNode; // 개인 노드 엔드 노드 시작; // end point public map () {map = new Node [7] [7]; for (int i = 0; i <7; i ++). 노드 (int d = 0; d <7; d ++) {map [0] [d] .setValue ( "%"); map [0] [d] .setReachable (false); map [d] [0] .setValue ( "%"); map [d] [0] .setReachable (fal se); map [6] [d] .setValue ( "%"); map [d] [6] .setValue ( "%"); map [d] [6] .setReachable (false);} map [3] [1] .setValue ( "a"); startNode = map [3] [1]; map [3] [5] .setValue ( "b"); endnode = map [3] [5]; for (int k = 1; k <= 3; k ++) {map [k+1] [3] .setValue ( "#"); map [k+1] [3] .setreachable (false); map public void showmap () {for (int i = 0; i <7; i ++) {for (int j = 0; setMap (node [] [] map) {this.map = map;} public node getStartNode () {return startNode;} public void setStartNode (node startNode) {this.startNode = startNode;} public node getEndNode () {return endnode;} public void setendNode (node endnode) {this.endnode). 엔드 노드;}}가장 중요한 아스타르 수업은 다음과 같습니다
작동 과정
1 시작점 A에서 시작하여 보류 지점을 "오픈리스트"로 저장하는데, 이는 확인할 제곱 목록입니다.
2 출발점 주변에서 접근 가능하거나 통과 가능한 사각형을 모두 찾아서 파악할 수없는 사각형을 건너 뜁니다. 오프닝 목록에 추가하십시오. 이 모든 그리드에 대한 포인트 A를 "부모 그리드"로 저장하십시오. 우리가 길을 설명하고 싶을 때, 부모 광장
재료는 매우 중요합니다. 구체적인 목적은 나중에 설명 될 것입니다.
3 개방 목록에서 시작점 A를 삭제하고 다시 확인할 필요가없는 모든 제곱을 저장하기 위해 "닫기 목록"에 추가하십시오.
위의 단계 후에, "오픈리스트"에는 장애물을 제외한 시작점 A 주변의 모든 노드가 포함됩니다. 부모 노드는 모두 A입니다. 앞에서 언급 한 공식 F = G+H를 통해 각 노드의 G, H 및 F 값을 계산하고 F의 값에 따라 작습니다.
큰 정렬. 그리고 가장 작은 F 값으로 노드에서 다음 작업을 수행하십시오.
4. ON 목록에서 제거하여 OFF 목록에 추가하십시오.
5. 인접한 그리드를 확인하십시오. 통과되지 않은 것을 건너 뛰고 (1. "닫기 목록"과 2. 장애물에서) 아직 안에 있지 않은 경우 열린 목록에 추가하십시오. 선택한 사각형을 새 정사각형의 부모 노드로 취하십시오.
6. 인접한 그리드가 이미 열린 목록에있는 경우 현재 경로가 더 나은지 확인하십시오. 다시 말해, 새로운 경로로 도달하면 g 값이 낮아질 지 확인하십시오. 그렇지 않다면 아무것도 없습니다
하다. (여기서 내 코드에는 판단이 없습니다)
7. 대상 그리드 (엔드 포인트 "B")가 "열린 목록"에 추가 될 때 까지이 프로세스를 반복하여 엔드 포인트 B가 이미 "닫기 목록"에 추가 된 이전 노드 주위에 있음을 나타냅니다. 엔드 포인트 B에 도달하기 위해 한 단계 만 수행하면됩니다.
8. 우리는 "닫기 목록"에 엔드 포인트 B를 추가합니다.
9. 마지막 단계에서는 출발점 A에서 종료점 B 로의 경로를 나타내야합니다. 모 노드의 역할이 표시됩니다. "목록 닫기"에서 엔드 포인트 노드의 상위 노드 값을 변경하면 단서를 따라 경로를 표시 할 수 있습니다.
코드를 확인하십시오
패키지 a_star_search; import java.util.arraylist; public class astar {/*** arraylist array를 "Open List"및 "cose list"및 "close list <node> Open = new ArrayList <Node> (); arraylist <node> close = new arraylist> ();/*** get h hale* @parocted : node : endnode : endpoint* @return*/public double gethvalue (노드 currentNode, node endnode) {return (return (math.getx () - endnode.getx ()) + math.abs (currentNode.gety () - endnode.gety ())* 10;}/*** get get* @param curtingnode : @param curtentnode : getGValue (node currentNode) {if (currentNode.getPnode ()! = null) {if (currentNode.getX () == currentNode.getPnode () getx () || currentNode.gety () == currentNode.getPnode (). gety ()) {// 현재 Node (HORIZONT) 사이의 위치 관계를 판단합니다. currentNode.getGValue ()+10;} return currentNode.getGValue ()+14;} return currentNode.getGvalue ();}/** * get f value : g+h * @param currentNode * @return */public double getfvalue (node currentNode) {return currentNode.getgValue ()+curtednode. * 선택된 노드 주변의 노드를 "열린 목록" * @param node * @param map */public void inopen (노드 노드, 맵 맵) {int x = node.getx (); int y = node.gety (); for (int i = 0; i <3; i ++) {for (int j = 0; 폐쇄 목록에있는 장애물이 아니며, 개방 목록이 포함되지 않으며 선택되지 않습니다. if (map.getMap () [x-1+i] [y-1+j] .isreachable () &&! open.contains (map.getMap () [x-1+i] [y-1+j]) & w 선택된 노드는 상위 노드 맵으로 사용됩니다. getMap () [x-1+i] [y-1 +j].setGValue(getGValue(map.getMap()[x-1+i][y-1+j]));map.getMap()[x-1+i][y-1+j].setHValue(getHValue(map.getMap()[x-1+i][y-1+j],map.ge tendnode ())); map.getMap () [x-1+i] [y-1+j] .setfvalue (getfvalue (map.getMap () [x-1+i] [y-1+j])); open.add (map.getMap () [x-1+i] [y-1+j]);}}}}}}}}}}}}}}}}}}}}} * 열린 목록의 노드를 f value에서 크게 value */public void sort (arraylist <node> arr) {for (int i = 0; i <arr.size () -1; i ++) {for (int j = i+1; arr.get (j) .getfvalue ()) {node tmp = new node (); tmp = arr.get (i); arr.set (i, arr.get (j)); arr.get (j, tmp);}}}/** * "닫기 목록" * @param node * @param open */public void inclose (node node) (node node). inpen) {if (open.contains (node)) {node.setReachable (false); // 세트 Uncleachable.remove (node); close.add (node);}} public void search (map map) {// 시작점 주위의 노드를 작동합니다. inopen (map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()], map); close.add (map.getMap () [map.getStart node (). getx ()] [map.getStartNode (). getx ()] [map.getStartNode (). gety ()); map.getMap () [map.getStartNode (). getx ()] [map.g etstartnode (). gety ()]. setreachable (false); map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()]. setPnode (map.getMap () [map.getStartNode () do {inopen (open.get (0), map); conceplose (Open.get (0), Open); Sort (Open);} while (! open.contains (map.getMap () [map.getendNode (). getx ()] [map.getEndnode (). gety ()]; // 오픈리스트에 포함되어 있음을 알면 10. clos (map.getMap () [map.getendNode (). getx ()] [) [map.getendNode (). node (); // <span style = "white space : pre"> </span> node = map.getmap () [map.getendNode ()] [map.getendNode (). gety ()]; == map.getStartNode ()) {// <span style = "white space : pre"> </span> node.getpnode ( "*"); "White"; 스타일 = "화이트 공간 : pre"> </span> map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()]. setValue ( "a");}}마지막으로 주요 방법을 작성하십시오
패키지 a_star_search; public class maintest {public static void main (String [] args) {map map = new map (); Astar astar = New Astar (); map.showmap (); astar.search (지도); System.out.println ( "============================================================================================= ============================================================================================================================================== ============================================================================================================================================== =========================================================================================================================================== map.showmap ()};맵을 수정하고 효과를 확인하도록 테스트하십시오.
% % % % % % % % % oooo % oo # oo % % a o # o b % oo # oo % oo % oober % % % % % % % ====================================================================================== % % % % % % % oo # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # o # OO # OO # OO # % % % % %
요약
가장 짧은 경로 (최적 솔루션)가 발견되도록하려면, 추정 함수 h (n)의 선택에 중요한 점 : 추정 값 h (n) <= n의 대상 노드에 대한 선택에 있습니다. 이 경우 많은 점을 검색하고 검색 범위가 크고 효율이 낮습니다. 그러나 얻을 수 있습니다
최적의 솔루션. 추정 값> 실제 값이라면 점수 검색 수가 작고 검색 범위가 작고 효율이 높지만 최적의 솔루션을 얻는 것을 보장 할 수는 없습니다.
가장 큰 느낌은 : 3 일, 이틀 동안 그물을 건조시키는 것에 대한 가장 금기 사항입니다. 금액은 크지 않지만 연속성이어야하며 키는 지속성입니다.
모든 프로그래머가 코드를 행복하게 입력하고 그가 좋아하는 일을 할 수 있기를 바랍니다.
위는 Java 프로그래밍 및 A* 알고리즘의 전체 코드를 구현하는 것에 대한이 기사의 모든 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오.