환형 연결리스트(Circular Linked List) -단순 연결리스트와 같은 구조를 가지지만 다른점은 제일 마지막 노드가 제일 처음 노드를 가리키고 있다. 그러므로 tail이라는 개념이 없다. 환형 연결리스트를 이용한 문제----요셉의 문제 예를 들어 A부터 J까지의 10명의 사람이 시계방향으로 순서대로 원을 지어 앉아 있다고 하자. 이때, A부터 시작하여 4명간격으로 사람을 그 원에서 뽑아낸다고 하면 그 순서는 어떻게 될것인가하는 문제이다. 이 경우는 A E I D J G F H C B 이런순이 될것이다. 이제 문제이다---> 프로그램은 사용자로부터 사람의 수 n과 간격 step을 입력받아 사람의 수 만큼 1부터 n까지의 정수를 키로 가지는 노드를 환형 연결리스트로 구성한다. 다음에 처음의 노드로부..
원문 priorityqueue Open list Closed AStarSearch s.g = 0 // s is the start node s.h = GoalDistEstimate( s ) s.f = s.g + s.h s.parent = null push s on Open while Open is not empty pop node n from Open // n has the lowest f if n is a goal node construct path return success for each successor n' of n newg = n.g + cost(n,n') if n' is in Open or Closed, and n'.g
[A* algorithm] 여기서는 실제 거리를 고려한 탐색과 최적 우선 탐색 방법을 결합하면 보 다 우수한 탐색 알고리즘을 만들 수 있습니다. 만일 출발 노드 로 부터 각 노드까지의 정확한 거리를 계산할 수 있고 목표 노 드까지의 거리를 예측할 수 있는 경험적(heuristic)정보가 이용 가능하다면 A* 알고리즘을 적용할 수가 있습니다. A* 알고리즘은 출발 노드에서 목표 노드까지 최단 거리를 갖 는 노드를 선택한다. 이를 위한 평가 함수는 F = g + h로 결정 합시다. g는 출발 노드에서 현재 노드까지 최소 비용이며, h는 현재 노드에서 목표 노드까지 예측된 최소 비용이다. 만일 h는 현재 노드에서 목표 노드까지의 실제 거리를 초과하지 않는다면 A* 알고리즘은 항상 최단 거리의 경로를 찾아내며,..
출처 : http://blog.naver.com/goople
A* 알고리즘 1) 기본 분기와 한정 탐색 -. 누적 경로 이용 -. 최적 우선 탐색과정과 유사 -. 최초의 경로가 발견될 때 끝낸다. 2) 개선 1 -. 종료 조건 개선 경로가 발견될 때 끝내지 않고, 가장 짧은 미완성의 경로 길이가 가장 짧은 완성된 경로 길이보다 클 때에야 종료. 3) 개선 2 -. 평가 함수를 하나 더 이용 저평가치(underestimate) 추가 이용 남은 거리에 대한 평가 함수와 누적 거리를 합한 최저한계예측값(lower bound) 이용 4) 개선 3 -. 중복되는(redundant) 경로를 버린다. 동적 프로그래밍 기법(dynamic programming principle) 이용 기존에 나왔던 노드 목록 관리 5) A*알고리즘 -. 분기와 한정 탐색을 1,2,3방법으로 개선..
A*는 맵을 탐색하면서 맵의 여러 위치들에 해당하는 노드들을 만들어 나간다. 이러한 노드들은 검색의 진행 상황을 기록하는 용도로 쓰인다. 노드들은 맵의 위치를 저장할 뿐만 아니라,흔히 f, g, h라고 부르는 중요한 세 가지 속성들도 저장한ㄷ. f, g, h는 각각 fitness(적합도), goal(목표), heuristic(휴리스틱) 값들을 의미한다. 이 값들을 좀더 설명하자면 : g는 시작노드로부터 이 노드까지 오는 데 드는 비용이다. 시작 노드에서 맵의 이 이치까지 오는 경로들은 여러 개가 있을 수 있는데, 이 노드는 그 경로들 중 특정한 하나를 의미한다. h는 이 노드에서 목표까지 가는데 드는 '추정된' 비용이다. 이때 h는 휴리스틱을 의미하며, 휴리스틱이란 '경험에 기초한 추측'을 뜻한다. 이것..
A* 알고리즘은 f (=g+h)값이 가장 작은 것을 향해 나아가는 알고리즘이다. 먼저, 어떤 상태에서 최적인 목표 G까지의 평가함수 f(G)가 있다고 가정한다. 그 다음 G보다는 덜 최적화된 결과인 H까지의 평가함수 f(H)가 있다고 가정한다. 이 경우 f(H) > f(G) 이다. 마지막으로 A* 알고리즘이 H를 선택하였다고 가정해 보자. 여기서 G로 가는 길 중간의 노드 n이 있다고 할때, 평가함수 f 중의 h가 admissible(실제 결과값 보다 항상 작다) 하기 때문에 f(G) > f(n) 이다. 여기에서 모순이 발생하게 된다. f(H)로 갔다는 것은 A*알고리즘이 f(n)보다 작기 때문에 선택했다고 볼 수 있기 때문에, f(n) > f(H) 이다. 위에서 f(G) > f(n)이라고 하였고 f(n..
