8 야드 난제 (계발 식 검색)

8 야드 난제 --- 계발 식 검색 소
 
1. 시작 식 검색:
특징: OPEN 표를 다시 배열 하고 가장 희망 적 인 노드 를 선택 하여 확장 합 니 다.
종류: 질 서 있 는 검색 (A 알고리즘), A * 알고리즘 등
 
2. 견적 함수
노드 가 가장 좋 은 구 해 경로 에 있 는 희망 정 도 를 추산 하 는 함수
f(n) = g(n) + h(n)
 n - 검색 그림 의 현재 확 장 된 노드;
f (n) - 초기 상태 노드 s 에서 노드 n 을 통 해 목표 노드 ng 에 도착 하고 예상 하 는 최소 경로 대가;
g (n) - s 에서 n 까지 의 실제 경로 대가;
h (n) - n 에서 ng 까지 예상 되 는 최소 경로 대가.
 8 야드 난제 평가 함수: f (n) = d (n) + w (n)                     
그 중 d (n) 는 n 의 깊이           w (n) 는 재위 하지 않 은 바둑 알 수 이다.
 
3. 질서 있 는 검색:
OPEN 표 에 있 는 최소 f 값 의 노드 를 다음 확장 할 노드 로 선택 하 십시오.
8 야드 어 려 운 문 제 는 전역 에서 좋 은 검색 을 사용 합 니 다.
   OPEN 표 에서 가장 작은 f 값 을 가 진 노드 를 다음 확장 할 노드 로 선택 하 십시오. 즉, 항상 가장 희망 적 인 노드 를 다음 확장 할 노드 로 선택 합 니 다.
8 야드 어 려 운 문제 에서 평가 함수
       f(n)=d(n)+p(n)
계발 함수 h (n) = p (n), p (n) 는 위치 에 있 지 않 은 바둑 알 과 목표 위치의 거리의 합 이 고 p (n) ≤ h * (n) 가 있어 A * 알고리즘 의 제한 조건 을 만족시킨다.
w (n) - 자리 에 없 는 바둑돌 수 는 적절 하지 않 고 노드 를 잘못 선택 하여 확장 합 니 다.
p (n) - h * (n) 에 가 까 운 h (n) 의 값 은 노드 n 과 목표 상태 노드 를 비교 하 는 것 이다. 모든 잘못된 바둑 알 은 가설 이 막 히 지 않 는 상황 에서 목표 상태 에 해당 하 는 위치 로 이동 하 는 데 필요 한 걸음 걸 이 를 합 친 것 이다.
p (n) 는 w (n) 보다 h * (n) 에 가깝다. p (n) 는 잘못된 요 소 를 고려 했 을 뿐만 아니 라 잘못된 거리 (이동 횟수) 도 고려 했 기 때문이다.
데이터 구조의 구축: open, close 표 는 노드 를 추가 하 는 작업 을 삭제 하기 때문에 단일 체인 표를 사용 하 는 것 이 가장 좋다.
open 표 는 생 성 된 노드 와 처리 되 지 않 은 노드 를 저장 하고 처 리 된 노드 를 꺼 내 close 표 에 넣 습 니 다.
close 표 저장 처리 노드
status 표 는 생 성 된 모든 노드 를 저장 합 니 다.
전체 국면 에서 우수한 것 을 고 르 는 사상 을 채택 하 다.
 자바 코드 는 다음 과 같 습 니 다:

package      ;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;





public class Main {
	static int f[][]=new int[3][3];
	static int e[][]=new int[3][3];
	static int p=0;
	static int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};
	static Listopenlist=new LinkedList();
	static Listcloselist=new LinkedList();
	static int d=0;
	static Liststatus=new LinkedList();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1;//    
		String str2;//    
		str1="2831647.5";//   .  
		str2="1238.4765";
		for(int i=0;i=3||y<0||y>=3){
			return false;
		}
		return true;
	}
	public static boolean contains(List list,int a[][]){
		int flag=0;
		int a1[][] = new int[3][3];
		
		for(int i=0;i