열두 차시를 한 장의 지도로

📖 예시 답안 맹목적 탐색은 목표가 어느 쪽인지에 대한 정보 없이 정해진 순서로 상태를 펼치는 방법이고 (프론티어를 큐로 쓰면 BFS, 스택으로 쓰면 DFS), 정보 이용 탐색은 '여기서 목표까지 얼마나 남았나'에 대한 어림인 휴리스틱을 이용해 더 유망해 보이는 상태를 먼저 펼치는 방법이다. 이 단원의 미로에서 BFS는 64칸을 둘러보고 17걸음짜리 최단 경로를 찾았고, A*는 52칸만 둘러보고도 같은 17걸음을 찾았다 — 어림을 쓴 대가 없이 13칸을 아낀 것이다. 다만 어림에만 의존하는 탐욕적 탐색은 20칸으로 가장 적게 둘러보지만 경로가 19걸음으로 길어져 최단을 잃었다. 곧 맹목적 탐색은 느리지만 최단을 보장하고, 정보 이용 탐색은 빠르지만 어림이 실제보다 부풀려지면 최단을 잃는다. A*는 어림이 실제 남은 비용을 넘지 않는 한(허용 가능성) 둘을 함께 잡는다.

📖 예시 답안 후향 추론은 결론에서 거꾸로 '이것을 밝히려면 무엇이 필요한가'를 캐물으므로, 밟은 규칙의 사슬이 그대로 설명이 된다. 대출이 거절됐을 때 "왜죠?"라는 물음에 어느 규칙의 어느 조건에서 막혔는지 정확히 짚어 줄 수 있고, 나아가 무엇을 알려 주면 결론이 바뀌는지까지 말해 준다. 의료·금융·법률처럼 판단의 근거를 설명할 의무가 있는 분야에서 이 성질은 대체하기 어렵다. 한계는 첫째 지식 획득의 병목 — 전문가도 자기가 아는 것을 규칙으로 다 적지 못한다 (10차시에서 '적지 못했던 지식'을 각자 하나씩 만난 그 자리다). 둘째 예외와 상식의 끝이 없다 — '새는 난다'에 펭귄·타조·다친 새…를 계속 덧붙여야 하고, 규칙이 늘수록 서로 충돌한다. 이 두 한계가 2단원의 출발점이 된다.

📖 예시 답안 다섯 칸은 상태 · 행동 · 목표 · 비용 · 어림이다. 예를 들어 '시간표 짜기'라면 상태 = 지금까지 배정된 (과목, 시간) 목록, 행동 = 아직 안 넣은 과목 하나를 빈 시간에 넣기, 목표 = 모든 과목이 겹침 없이 배정된 상태, 비용 = 공강 수 + 선호하지 않는 시간대 수, 어림 = 아직 안 넣은 과목 수. 가장 채우기 어려운 칸은 대개 어림이다. 어림을 못 세운다는 것은 '목표에 얼마나 가까워졌는지 잴 잣대가 아직 없다'는 뜻이고, 잣대가 없으면 A*를 써도 사실상 다익스트라처럼 동작한다(h = 0). 그럴 때는 문제를 잘못 고른 것이 아니라 목표를 더 뾰족하게 다시 적어야 한다는 신호다.