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..
방향 그래프 최단 경로를 구하는 알고리즘으로 유명한 다익스트라 알고리즘 ACM ICPC 대회에서 가끔 요구한다. #include using namespace std; int main() { int i,j,k,s,e,min,n=8; int path[8],path_cnt=0; // unconnect const int U=static_cast(-1)/2; int data[8][8] = { {0,2,U,U,U,3,U,U}, {2,0,4,1,U,U,U,U}, {U,4,0,U,3,U,U,U}, {U,1,U,0,3,U,2,U}, {U,U,3,3,0,U,U,4}, {3,U,U,U,U,0,6,U}, {U,U,U,2,U,6,0,4}, {U,U,U,U,4,U,4,0}}; bool v[8]; int distance[8],vi..
최단경로 구하기 (Shortest Path) 어떤 그래프 G의 정점 A에서 다른 어떤 정점 B로의 최단경로는 A에서 B로가는 경로를 가운데 가장 작은 가중치 합을 가지는 경로를 말한다. 1. 최단경로를 구하는 방법최단 경로는 앞에서 살펴본 최소 비용 신장트리와 같이 그리디 알고리즘으로 구할 수 없다. 그리디 알고리즘을 사용하면 왜 구할 수 없는지를 생각해보자. 그리디 알고리즘은 현재 상태에서 가장 최적의 것을 선택해 나가는 방법이다. 그러나, 특정한 두 점사이를 연결하는 여러개의 경로들이 있을때, 가장 작은 가중치 합을 가지는 경로를 찾는 것은 이 경로들의 공통되는 끝점에서 가장 짧은 에지만을 선택해서는 찾을 수 없다. 즉, 최단경로는 자기 자신의 가중치는 높아도 전체적인 경로가중치를 줄여주는 간선이 있..
출처: http://en.wikipedia.org/wiki A-star algorithm은 초기노드에서 목표노드까지의 경로를 찾는 graph searching algorithm. Best-first search의 한 종류인데, 그러면 best-first search는 과연 무엇인가? Best-first search : 어떤 rule에 따라서 가장 promising하다고 판단된 노드부터 먼저 방문하는 depth-first search를 최적화하는 graph search 알고리즘이다. 이때 어떤 rule이란, 노드에 대한 extra 정보를 의미함으로써, heuristic function을 정의한다. Dijkstra의 shortest path finding 알고리즘도 best-first search의 종류에 ..
허니와 클로버
원제 Honey and Clover 구성 30분 X 26화 장르 코믹 시청등급 15세 제작연도 2005년 감독 카사이 켄이치 제작사 J.C Staff/후지TV 저작권 ⓒ CHIKA UMINO / SHUEISHA • HACHIKURO SEISAKU INNKAI 줄거리 '우리의 푸르른 날~ 너와 나의 네잎 클로버를 위해' 낡고 허름한 아파트에서 함께 살고 있는 가난한 미대생 다케모토, 모리타, 마야마. 새 학년이 된지 얼마 안되어 하나모토 교수의 조카 하구미가 입학하면서 이야기는 시작된다. 귀엽고 자그마한 외모지만 천재적인 능력을 가진 하구미. 타케모토와 모리타는 그녀를 보자마자 한눈에 반한다. 한편 아르바이트 회사의 사장을 짝사랑 하는 마야마와 그를 짝사랑 하는 친구 아유미까지... 풋풋한 미대생들의 사랑..
