자바 구현 A * 알고리즘
9801 단어 자바 클래스
우 리 는 아래 의 그림 을 지도 로 설명 할 것 입 니 다. 그림 에서 각 칸 에 대해 번 호 를 매 겼 습 니 다. 그 중에서 녹색 칸 은 출발점 을 대표 하고 빨간색 칸 은 종점 을 대표 하 며 파란색 칸 은 장 애 를 대표 합 니 다. 우 리 는 A 성 알고리즘 으로 출발점 에서 종점 까지 가장 좋 은 길 을 찾 을 것 입 니 다. 설명 하기 위해 본 지 도 는 상하 좌우 4 방향 만 걸 을 수 있 도록 규정 하고 있 습 니 다. A 성 알고리즘 을 이해 하면8 개 방향 도 자 연 스 럽 게 알 아 요.
지도 에서 모든 격자 는 가장 기본 적 으로 두 개의 속성 치 를 가 져 야 한다. 하 나 는 격자 가 원활 한 것 인지 장애 인지, 다른 하 나 는 그의 아버지 격자 를 가리 키 는 지침 (양 방향 링크 구조 중의 아버지 결점 지침 에 해당 함) 이다. 우 리 는 격자 값 이 0 일 때 원활 하고 값 이 1 일 때 장애 라 고 가정 한다.
A 성 알고리즘 에는 상당히 중요 한 요소 가 2 개 있 는데 첫 번 째 는 아버지의 결점 을 가리 키 는 지침 이 고 두 번 째 는 OPEN 표 이 며 세 번 째 는 바로 CLOSE 표 입 니 다. 이 두 장의 표 의 구체 적 인 역할 은 저희 가 뒤에서 소개 하 겠 습 니 다. 네 번 째 는 각 결점 의 F 값 (F 값 이 그림 구조 에 해당 하 는 가중치) 입 니 다.
F = H + G;그 중에서 H 값 은 격자 에서 현재 격자 에서 종점 으로 이동 하 는 예상 이동 비용 입 니 다.이것 은 자주 계발 식 이 라 고 불 리 며 당신 을 좀 현혹 시 킬 수 있 습 니 다.이렇게 부 르 는 이 유 는 그것 이 단지 추측 일 뿐 이기 때문이다.우 리 는 도로 에 각종 장애 (벽, 물, 등등) 가 존재 할 수 있 기 때문에 경로 의 길 이 를 미리 알 수 없다.비록 본 고 는 H 를 계산 하 는 방법 만 제 공 했 지만 인터넷 에서 많은 다른 방법 을 찾 을 수 있 습 니 다. 우 리 는 H 값 을 종점 에 있 는 줄 에서 현재 칸 에 있 는 절대 치 를 빼 기 ... 과 종점 이 있 는 열 은 현재 칸 이 있 는 열의 절대 값 의 합 을 빼 고 G 값 은 현재 칸 의 아버지 칸 에서 현재 칸 으로 이동 하 는 예상 이동 비용 입 니 다. 여기 서 우 리 는 기수 10 을 설정 합 니 다. 모든 H 와 G 는 10 을 곱 해 야 합 니 다. 이렇게 하면 관찰 하기 편리 합 니 다.
자, 지 도 를 검색 해 보 겠 습 니 다.
먼저, 우 리 는 출발점 의 아버지 결산 점 을 NULL 로 설정 한 다음 에 출발점 의 G 값 을 0 으로 설정 한 다음 에 open 표 에 넣 은 다음 에 출발점 을 아버지 결산 점 의 주위 4 개 점 20, 28, 30, 38 (우리 지 도 는 4 개 방향 만 갈 수 있 기 때문에 8 방향 이 라면 점 을 넣 어야 한다) 을 모두 open 목록 에 넣 고 각 결산 점 의 H 값 을 계산 한 다음 에 출발점 을 open 목록 에서 삭제 합 니 다.close 표 에 넣 으 면 close 표 의 모든 칸 을 옅 은 파란색 라인 으로 상자 변 처 리 를 할 것 입 니 다. 그래서 이번 검색 후 그림 은 다음 과 같은 형식 으로 바 뀌 었 습 니 다. 그 중에서 화살 표 는 아버지 결점 을 대표 합 니 다.
그 중에서 각 칸 의 왼쪽 아래 는 G 값 이 고 오른쪽 아래 는 H 값 이 며 왼쪽 위 는 H 값 입 니 다. 우 리 는 28 번 칸 을 예 로 들 어 F 값 을 쓰 는 알고리즘 을 설명 합 니 다. 먼저 종점 33 은 4 행 7 열 에 있 고 28 은 4 행 2 열 에 있 으 면 행 수 차 이 는 0 이 고 열 수 차 이 는 5 이 며 총 화 는 5 입 니 다. 그리고 우리 가 이전에 정 한 기수 10 을 곱 하기 때문에 H 값 은 50 이 고 28 의 아버지 결점 29 에서 28 로 이동 하기 때문에 길 이 는 1 칸 이 고 29 번 은 기점 입 니 다.G 값 이 0 이기 때문에 아버지 결점 29 에서 28 로 이동 하 는 데 소모 되 는 G 값 은 (0 + 1) * 10 = 10, 0 은 아버지 결점 의 G 값 이 고 1 은 29 에서 28 까지 소모 된다.
현재 OPEN 표 의 값: 20, 28, 30, 38 현재 CLOSE 표 의 값: 29
이제 우 리 는 OPEN 목록 에서 F 값 이 가장 낮은 것 을 찾 아 결산 점 30 의 F 값 이 가장 낮 고 40 이라는 것 을 얻 은 다음 에 결산 점 30 을 OPEN 표 에서 삭제 한 다음 에 CLOSE 표 에 가입 한 다음 에 결산 점 30 주위 4 개의 결산 점 을 판단 한다. 결산 점 31 은 장애 이 고 결산 점 29 는 CLOSE 표 에 존재 하기 때문에 우 리 는 이 두 가 지 를 처리 하지 않 고 21 과 39 번 결산 점 만 OPEN 표 에 넣 을 것 이다.추가 후 맵 이 다음 스타일 로 변 경 됩 니 다.
현재 OPEN 표 의 값: 20, 28, 38, 21, 39 현재 CLOSE 표 의 값: 29, 30
이어서 우 리 는 위의 과정 을 반복 해서 OPEN 표 의 F 값 이 낮은 값 을 찾 았 다. 우 리 는 OPEN 표 의 모든 결점 의 F 값 이 60 이라는 것 을 발견 했다. 우 리 는 즉시 결점 을 찾 았 다. 여기 서 우 리 는 마지막 에 OPEN 표 에 추 가 된 결점 을 직접 찾 아서 접근 하기 편리 하 다. (이러한 상황 이 존재 하기 때문에 모든 점 에서 다른 점 까지 의 가장 짧 은 경 로 는 하나 가 아 닐 수 있다.) 우 리 는 결점 39 를 찾 았 다.그 를 OPEN 표 에서 삭제 하고 CLOSE 표 에 추가 한 다음 에 39 번 결점 주위 의 4 개의 결점 을 관찰 해 야 한다. 40 번 결점 이 장애 이기 때문에 우 리 는 그것 을 상관 하지 않 는 다. 30 번 결점 은 이미 OPEN 표 에 존재 하기 때문에 우 리 는 39 번 결점 이 30 번 결점 이 라 고 가정 하면 30 번 결점 의 G 값 이 더 작 지 않 을 까? 더 작 으 면 우 리 는 30 번 결점 의 아버지 결점 을 39 번 으로 바 꿔 야 한다.여기 서 우 리 는 39 번 결점 을 아버지 결점 으로 삼 아 30 번 결점 의 새로운 G 값 은 20 이 고 30 번 결점 의 원래 G 값 은 10 이 며 원래 의 것 보다 작 지 않다. 그래서 우 리 는 30 번 에 대해 어떠한 조작 도 하지 않 는 다. 똑 같이 38 번 결점 에 대해 상술 한 조작 을 한 후에 우 리 는 그것 에 대해 어떠한 조작 도 하지 않 는 다. 이어서 우 리 는 48 번 결점 을 OPEN 표 에 추가 하고 추 가 된 후에 지 도 를 다음 그림 스타일 로 바 꾸 었 다.
현재 OPEN 표 의 값: 20, 28, 38, 21, 48 현재 CLOSE 표 의 값: 29, 30, 39
다음은 자바 코드 구현
public class Point {
public int x;
public int y;
public Point parent;
public boolean equal(Point p){
return x == p.x&&y==p.y;
}
public Point(int x,int y){
this.x = x;
this.y = y;
}
public String toString(){
return "("+x+","+y+")";
}
}
public class Map2D {
private int points[][];
public Map2D(int[][] p){
points = p;
}
public int getPointData(int x,int y){
return points[y][x];
}
public int getPointData(Point p){
return points[p.y][p.x];
}
public int getXLength(){
return points[0].length;
}
public int getYLength(){
return points.length;
}
public void setPoints(int ps[][]){
points = ps;
}
}public class AStart {
private Point startLoca; //
private Point dest; //
private Map2D map; //
private List openTable = new LinkedList(); //open ，
private List closeTable = new LinkedList(); //close ，
private Point cur ; //
public AStart(Map2D map){
this.map = map;
}
public static void main(String[] args){
Map2D m = new Map2D(new int[][]{
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,1,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0},
{0,0,1,1,1,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0}
});
AStart as = new AStart(m);
as.setStartLoca(new Point(2,4));
as.setDest(new Point(8,4));
System.out.println(as.findBestPath());
}
/**
*
* l p,
*
* @param l
* @param p
* @author YitianC
* @history
* YitianC Apr 24, 2012 3:27:21 PM
*/
public void addPath(List l,Point p){
if(p.parent!= null){
addPath(l,p.parent);
}
l.add(p);
}
/**
*
*
*
* @return
* @author YitianC
* @history
* YitianC Apr 24, 2012 3:29:21 PM
*/
public List findBestPath(){
cur = startLoca;
closeTable.add(startLoca);
while(!cur.equal(dest)){
Point sur[] = this.getSurroundPoints(cur) ;
if(sur.length==0){
this.removePoint(openTable, cur.x, cur.y);
cur = this.getBestPoint();
}
else{
for(Point c:sur){
// f_func;
openTable.add(c);
c.parent = cur;
}
openTable.remove(cur);
closeTable.add(cur);
cur = this.getBestPoint();
}
}
List rt = new ArrayList();
this.addPath(rt, cur);
clearMemory();
return rt;
}
/**
*
*
*
* @author YitianC
* @history
* YitianC Apr 24, 2012 3:29:52 PM
*/
public void clearMemory(){
for(Point p:openTable){
p.parent = null;
}
openTable.clear();
openTable = null;
for(Point p:closeTable){
p.parent = null;
}
closeTable.clear();
closeTable = null;
}
/**
*
* (open)
*
* @return
* @author YitianC
* @history
* YitianC Apr 24, 2012 3:30:20 PM
*/
public Point getBestPoint(){
Point rt = null;
int k = 0;
for(Point p:openTable){
if(k == 0 &&f_func(p)>=0){
rt = p;
k++;
}
if(f_func(p)>= 0 &&map.getPointData(p) l,int x,int y){
for(Point p:l){
if(p.x == x&&p.y==y){
p.parent = null;
l.remove(p);
return;
}
}
}
/**
*
* l (x,y)
*
* @param l
* @param x
* @param y
* @return
* @author YitianC
* @history
* YitianC Apr 24, 2012 3:31:43 PM
*/
public boolean hasPoint(List l,int x,int y){
for(Point p:l){
if(p.x == x&&p.y==y){
return true;
}
}
return false;
}
/**
*
* l (x,y) ，
*
* @param l
* @param x
* @param y
* @return
* @author YitianC
* @history
* YitianC Apr 24, 2012 3:32:09 PM
*/
public Point getPoint(List l,int x,int y){
for(Point p:l){
if(p.x == x&&p.y==y){
return p;
}
}
return null;
}
/**
*
* loc
*
* @param loc
* @return
* @author YitianC
* @history
* YitianC Apr 24, 2012 3:32:31 PM
*/
public Point[] getSurroundPoints(Point loc){
List l = new ArrayList();
int lx = map.getXLength();
int ly = map.getYLength();
int tx = loc.x+1;
int ty = loc.y;
/**
*
*/
if(tx=0){
if(map.getPointData(tx, ty)==0){
if(!this.hasPoint(openTable, tx, ty) && !this.hasPoint(closeTable, tx, ty)){
l.add(new Point(tx,ty));
}
}
}
tx = loc.x;
ty = loc.y+1;
if(ty=0){
if(!this.hasPoint(openTable, tx, ty) && map.getPointData(tx, ty)==0){
if(!this.hasPoint(closeTable, tx, ty)){
l.add(new Point(tx,ty));
}
}
}
Point[] rt = new Point[l.size()];
return l.toArray(rt);
}
public Point getStartLoca() {
return startLoca;
}
public int h_func(Point p){
return h_func(p.x,p.y);
}
public int f_func(Point p){
return h_func(p)+g_func(p);
}
public int g_func(Point p){
return g_func(p.x,p.y);
}
public int h_func(int x,int y){
return (int)Math.sqrt((x-dest.x)*(x-dest.x)+(y-dest.y)*(y-dest.y))*10;
}
/**
*
* f
*
* @param x
* @param y
* @return
* @author YitianC
* @history
* YitianC Apr 24, 2012 3:33:04 PM
*/
public int f_func(int x,int y){
return h_func(x,y)+g_func(x,y);
}
public int g_func(int x,int y){
return (int)Math.sqrt((x-cur.x)*(x-cur.x)+(y-cur.y)*(y-cur.y))*10;
}
public void setStartLoca(Point startLoca) {
this.startLoca = startLoca;
}
public Point getDest() {
return dest;
}
public void setDest(Point dest) {
this.dest = dest;
}
public Map2D getMap() {
return map;
}
public void setMap(Map2D map) {
this.map = map;
}
}
출력
[(2,4), (1,4), (1,5), (1,6), (1,7), (2,7), (3,7), (4,7), (5,7), (6,7), (7,7), (8,7), (8,6), (8,5), (8,4)]
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
자바 에서 클래스 의 실례 화 방법자바 에서 클래스 의 실례 화 방법 은 네 가지 경로 가 있다. 1) new 연산 자 사용 2) Class 대상 을 호출 하 는 new Instance () 방법 3) 클론 () 방법 을 호출 하여 기 존 인 스 턴...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
