-목표 노드가 어디있는 지 모르는 상태에서 중요한 것은 어떤 노드들을 먼저 확장해서 탐색할 것인가인데, 이때 informed search는 그 후보들을 평가할 수 있는 평가함수가 존재(f(n) - evaluation function)
-순서하고 상관없이(깊이를 따지지말고) 들어있는 후보들 중에 평가함수가 가장 좋은 것들 찾아서 확장 대상이 되도록 함(Priority Queues)
f(n) = h(n)(heuristic)
-현재 상태 n에서부터 가장 가까운 목표까지의 비용(costs)을 예측한 값
-시작상태가 아닌 현재 상태부터임
-비용은 적을수록 좋음 즉, 그래서 후보들 중에서 h(n)이 가장 좋은 값을 가지는 노드부터 우선적으로 확장을 시도
SLD= Straight-Line Distance
-ex) h.sdl(n)= straight-line distance from n to ~~
-목표까지의 경로는 몰라도 현 위치와 목표 위치의 좌표를 대충 안다는 가정하에 직선거리를 구함(여러 장애물들을 일단 무시한 직선거리)
Gbfs
-bfs이긴한데 평가함수를 목표까지 남아 있는 소요 비용 가지고 비용이 작은 것일수록 우선적으로 확장하는 알고리즘
ex) Romania with step costs in km
-여기서 SLD의 값들이 평가함수의 값이 되는 것임
-f(n) = g(n) + h(n)
-g(n): initial node에서 현재 상태 n까지 비용의 평가치
-두 길이가 합쳐져서 평가치가 낮을수록 좋음(비용을 따지고 있기 때문에)
ex)
- 확장 순서: Arad - Sbiu - Rimnicu Vilcea - Fagaras - Pitesti - Bucharest
※주의: Rimnicu Vilcea에서 Pitesti가 아닌 Fagaras를 먼저 확장한다는 점(f(n) 값에 의해서)
-모든 노드 n에 대해서 h(n) <= h*(n) // h(n): 현재 상태에서 목표 상태까지의 실제 cost
-현재 상태에서 목표 상태까지의 cost를 예측할 때 과대 평가를 하지 않는 것(언제나 실제값보다 작게) - 허용성(admissible)
-if h(n) is admissible, a using TREE-SEARCH is optimal(최적성 )
→ex) Straight-Line Distance는 그럼 Admissible Heurisitcs에 속하나? - Yes: 직선거리는 실제거리보다 언제나 작게 예측하기 때문(같은 경우도 존재하긴 하겠지, 실제 거리가 더 짧아질 수는 없다는 말)
→ex) the 8-puzzle:
-h(2): 각 타일별로 목표위치까지 상하좌우 몇 번을 움직여야 하는지(나머지 타일을 다 무시하고 각 타일들이 몇 번 이동해야 목표위치까지 도달할 수 있는지) - total Manhattan distance
-h(1): 각 타일들을 전부 떼어내서 붙이는 것
-둘 다 현실적인 문제의 해답이 아님, 둘 다 Admissible하고 최적 solution을 보장할 수 있긴 함 but 이 문제와 이 최적 solution을 얼마나 효율적으로 찾는지는 다른 문제임(이 문제에 대한 내용이 Dominance)
-h가 낙관적으로 잘못 예측하면 g의 값이 늘어남
-두 heuristic function이 admissible하다는 가정하에 어떤 것이 더 domoiates(우세)한가에 대한 내용
-if h2(n) >= h1(n) for all n(both admissible) then h2 dominates h1
-h2 is better than h1 for search
-IDS는 무정보탐색 중에서 가장 효율적인 알고리즘
-h 함수가 상한값(실제값)에 가까울수록 즉, 크게 예측할수록 더 우수하다(효율적이다)