한 걸음 한 걸음 쓰기 알고리즘 (의 A * 알고리즘)

【 성명: 판권 소유, 전재 환영, 상업 용도 로 사용 하지 마 십시오. 연락처: feixiaoxixing @ 163. com]
    앞의 블 로그 에서 사실 우 리 는 이미 길 을 찾 는 알고리즘 을 토론 한 적 이 있다.그러나 당시 예제 그림 에서 선택 할 수 있 는 경 로 는 유일 했다.우 리 는 알고리즘 을 하나 골 랐 다. 즉, 이 유일한 경 로 를 골 라 야 하 는데 어떻게 골 라 야 합 니까?당시 에 우 리 는 끝 없 이 돌아 가 는 알고리즘 을 채택 했다.그러나 오늘 의 상황 은 좀 다르다.어디 있 지?그것 은 바로 오늘 의 경로 가 n 개 입 니 다. 이 경 로 는 모두 목적지 에 도달 할 수 있 습 니 다. 그러나 우 리 는 선택 하 는 과정 에서 요구 가 있 습 니 다. 그것 이 바로 선택 한 경로 의 거리 가 가장 짧 습 니까?방법 이 없 을까요?
    그렇다면 이 럴 때 는 A * 알고리즘 이 필요 하 다.A * 알고리즘 과 일반적인 알고리즘 은 어떤 차이 가 있 습 니까?우 리 는 하나의 예시 로 설명 할 수 있다.

/*
*       0  0  0  0  0
*       1  1  1  1  1
*       1  0  0  0  1  
*       1  0  0  0  1   
*       A  1  1  1  1
*/

    이것 은 5 * 5 의 배열 이다.만약 에 우리 가 array [1] [0] 에서 출발 하면 목 표 는 A 점 이다.우 리 는 그림 에서 목적지 에 도착 할 수 있 는 두 가지 방법 이 있 지만, 아래로 직행 하 는 방법 이 가장 짧다 는 것 을 발견 했다.그럼 이 가장 짧 은 알고리즘 을 어떻게 찾 습 니까?여러분, 잘 생각해 보 세 요.
    우 리 는 시간 을 도착 하기 몇 단계 로 돌아 갈 수 있 습 니까?우 리 는 왜 수평 방향의 점 보 다 는 방향 을 아래로 향 하 는 점 을 선택해 야 합 니까?원인 이 복잡 하지 않 은 것 은 모든 점 중에서 우리 가 선택해 야 할 이 점 과 목표 점 사이 의 거리 가 가장 짧 기 때문이다.그렇다면 이 가운데 경로 선택 이 바 뀌 었 을 까?사실은 가능 합 니 다. 길 을 선택 하 는 과정 에서 본 성 은 pk 의 과정 이기 때문에 우리 가 할 수 있 는 일 은 그 당시 의 목표 에서 가장 가 까 운 점 을 찾 는 것 입 니 다. 이 점 은 항상 변화 하 는 것 이기 때문에 마지막 으로 선택 한 길 은 이 렇 습 니 다.

/*
*       0  0  0  0  0
*       1  0  0  0  0
*       1  0  0  0  0  
*       1  0  0  0  0   
*       A  0  0  0  0
*/

    알고리즘 프로 그래 밍 알고리즘 을 어떻게 수정 해 야 합 니까?물론 데이터 구 조 를 먼저 정의 합 니까?

typedef struct _VALUE
{
	int x;
	int y;
}VALUE;

    그리고 목표 점 과 가장 짧 은 거 리 를 찾 았 다.

int find_most_nearest_neigh(VALUE data[], int length, int x, int y)
{
	int index;
	int number;
	int current;
	int median;

	if(NULL == data || 0 == length)
		return -1;

	current = 0;
	number = (int) sqrt((data[0].x - x) * (data[0].x - x)+ (data[0].y - y) *  (data[0].y - y));

	for(index = 1; index < length; index ++){
		median = (int) sqrt((data[index].x - x) * (data[index].x - x)+ (data[index].y - y) *  (data[index].y - y));
		
		if(median < number){
			number = median;
			current = index;
		}
	}

	return current;
}

    이 점 을 찾 으 면 모든 것 이 잘 될 것 입 니 다. 그러면 지금 우 리 는 data 를 다시 처리 해 야 합 니 다. 왜냐하면 팝 업 이 필요 하고 새로운 점 이 눌 러 서 처리 해 야 합 니 다.

VALUE* updata_data_for_queue(VALUE* data, int length, int* newLen)
{
	int index;
	int count;
	int max;
	VALUE* pData;

	if(NULL == data || 0 == length || NULL == newLen)
		return NULL;

	max = length << 2;
	pData = (VALUE*)malloc(max * sizeof(VALUE));
	memset(pData, 0, max * sizeof(VALUE));

	count = 0;
	for(index = 0; index < length; index ++){
		if(check_pos_valid(data[index].x, data[index].y - 1)){
			pData[count].x = data[index].x;
			pData[count].y = data[index].y -1;
			count ++;
		}

		if(check_pos_valid(data[index].x -1, data[index].y)){
			pData[count].x = data[index].x -1;
			pData[count].y = data[index].y;
			count ++; 
		}

		if(check_pos_valid(data[index].x, data[index].y + 1)){
			pData[count].x = data[index].x;
			pData[count].y = data[index].y +1;
			count ++;
		}

		if(check_pos_valid(data[index].x + 1, data[index].y)){
			pData[count].x = data[index].x + 1;
			pData[count].y = data[index].y;
			count ++; 
		}
	}

	*newLen = count;
	return pData;
}

    위의 함수 가 생기 면 findpath 는 아주 간단 합 니 다.

void find_path(int x, int y)
{
  while(/*       0 */){

	  /*      */

	  /*       */

  };
}

요약:
    (1) A * 의 중점 은 디자인 가중치 판단 함수 에 있 고 가장 좋 은 다음 점프 를 선택 하 는 것 이다.
    (2) A * 의 목 표 는 이미 알 고 있 는 것 이다.
    (3) A * 는 격자 형 경로 찾기 에 특히 적합 하 다.