지난 시간의 두 방법은 목표가 어디 있는지 전혀 모른 채 미로를 뒤졌습니다.
오늘은 "목표가 대략 저쪽"이라는 힌트를 하나 쥐여 줍니다.
둘러보는 칸은 64칸에서 20칸으로 줄어듭니다. 대신 무엇을 잃을까요?
성취기준 12인기01-03
어림(휴리스틱)맨해튼 거리탐욕적 최선 우선 탐색허용 가능성반례 만들기
🎯 학습 목표
어림(휴리스틱)이 무엇인지 설명하고, 격자에서 맨해튼 거리와 직선거리를 직접 계산할 수 있다.
탐욕적 최선 우선 탐색이 둘러보는 칸을 왜 줄이는지, 그러면서 무엇을 잃는지 숫자로 말할 수 있다.
탐욕적 탐색이 크게 돌아가는 벽 배치를 직접 만들어 그 결과를 표에 적을 수 있다.
🤔
여는 장면 — 미로 한가운데서도 알 수 있는 것
지난 4차시에 우리는 같은 미로를 두 번 뒤졌습니다.
프론티어에서 가장 먼저 넣은 것을 꺼내니(큐, 너비 우선 탐색)
64칸을 둘러보고 17걸음짜리 길을 찾았습니다.
가장 나중에 넣은 것을 꺼내니(스택, 깊이 우선 탐색)
22칸만 둘러보고 19걸음짜리 길을 찾았고요.
두 방법은 사이가 나빠 보이지만 한 가지가 똑같습니다.
둘 다 목표가 어느 쪽에 있는지 전혀 모른 채 뒤졌다는 것입니다.
그래서 이 둘을 맹목적 탐색(blind search)이라고 부릅니다.
깜깜한 방에서 손으로 벽을 더듬는 것과 같아요.
프랑스 비텐하임의 한 공원에 있는 나무 울타리 미로 안쪽 길입니다.
안에 서 있으면 양옆도 앞도 잎에 막혀 갈림길 너머가 보이지 않아요.
그래도 완전히 깜깜하지는 않습니다 — 머리 위 하늘은 트여 있어 해가 어느 쪽인지,
출구가 대략 어느 방향인지는 짐작할 수 있지요.
길은 몰라도 방향은 안다는 이 상태가 오늘의 출발점입니다.
출처: Mathieu Kappler, Wikimedia Commons (CC BY-SA 4.0)
컴퓨터도 마찬가지입니다. 미로의 정답 경로는 모르지만
목표가 몇 행 몇 열인지는 대개 알고 있어요.
내비게이션은 목적지의 좌표를 알고, 배달 로봇은 도착지의 위치를 압니다.
길을 모를 뿐 방향은 아는 것이지요. 그렇다면 물음은 이렇게 됩니다.
💭 오늘의 물음
목표가 어느 쪽인지 어림짐작할 수 있다면
탐색은 얼마나 빨라지고, 그 대신 무엇을 잃는가?
답의 절반은 미리 말해 두겠습니다. 3배 넘게 빨라집니다.
64칸이 아니라 20칸만 둘러보고 목표에 닿아요.
나머지 절반은 오늘 여러분이 직접 확인할 몫입니다.
그 20칸이 찾아낸 길은 17걸음이 아니라 19걸음이거든요.
그리고 오늘 여러분이 만들 벽 배치에서는 그 차이가 12걸음까지 벌어집니다.
1
어림 — 남은 거리를 값 하나로 답하는 함수
탐색에 쥐여 줄 힌트는 아주 단순한 모양이어야 합니다.
칸 하나를 받아 숫자 하나를 돌려주면 됩니다.
h(칸) = 이 칸에서 목표까지 남은 비용의 어림값
이 어림(휴리스틱, heuristic)에서
가장 중요한 낱말은 '어림'입니다.
정확한 남은 걸음 수를 알고 있다면 탐색은 애초에 필요가 없어요.
그 값을 따라 한 걸음씩 내려가기만 하면 되니까요.
우리가 쓸 수 있는 것은 싸게 구할 수 있는 대략의 값뿐입니다.
격자에서 쓰는 두 가지 어림
미로처럼 칸이 격자로 놓인 문제에서는 두 가지가 널리 쓰입니다.
둘 다 벽을 아예 보지 않고 좌표만으로 계산합니다.
두 어림을 같은 격자 위에 겹쳐 그렸습니다.
파란 꺾은 선이 맨해튼 거리, 분홍 점선이 직선거리입니다.
맨해튼 거리 — 행 차이의 절댓값과 열 차이의 절댓값을 더합니다.
상하좌우로만 움직이는 격자에서 벽이 없다면 정확히 이만큼 걸린다는 뜻이에요.
이름은 뉴욕 맨해튼에서 왔습니다. 길이 바둑판이라 건물을 뚫고 갈 수 없으니,
실제 걷는 거리는 언제나 '가로 + 세로'가 됩니다.
직선거리(유클리드 거리) — 피타고라스 정리로 잰 빗변의 길이입니다.
자로 두 점을 곧게 이은 길이지요. 격자에서는 실제로 갈 수 없는 길이라
맨해튼 거리보다 언제나 작거나 같습니다.
우리 미로에서 재 봅시다. 출발 S는 (0, 0)이고 목표 G는 (6, 11)입니다.
두 칸
맨해튼
직선거리
진짜 걸음 수
S(0,0) → G(6,11)
6 + 11 = 17
√(36+121) ≈ 12.53
17
(2,1) → (5,6)
3 + 5 = 8
√(9+25) ≈ 5.83
—
(6,6) → G(6,11)
0 + 5 = 5
5.00
13
진짜 걸음 수는 미로의 벽을 모두 따져 실제로 재 본 값입니다(오늘 실습에서 직접 잽니다).
첫 줄을 보세요. 출발점에서는 맨해튼 어림 17이 진짜 걸음 수 17과 정확히 같습니다.
까닭이 있습니다. 최단 경로 17걸음이 오른쪽과 아래 두 방향으로만 나아가고
왼쪽이나 위로 되돌아가는 걸음이 한 번도 없기 때문이에요.
되돌아가는 걸음이 하나도 없으면 실제 걸음 수는 '가로 이동 + 세로 이동'과 같아지고,
그것이 곧 맨해튼 거리입니다.
세 번째 줄은 반대입니다. (6, 6)에서 목표까지는 어림으로는 5인데
실제로는 13걸음이 걸립니다. 사이에 벽이 있어 크게 돌아가야 하거든요.
어림은 벽을 보지 않는다는 성질이 여기서 그대로 드러납니다.
뒤에서 이 성질이 아주 중요해집니다.
💡 어림은 '싸야' 한다
어림은 칸을 꺼낼 때마다 다시 계산됩니다.
이 미로는 65칸이니 많아야 수백 번이지만, 8차시에서 다룰 조각 퍼즐에서는
수만 번 불립니다. 그래서 어림을 정확하게 만들려고 공을 들이다
계산이 무거워지면 손해예요. 힌트 하나 얻는 데 오래 걸리면 배보다 배꼽이 큽니다.
맨해튼 거리는 뺄셈 두 번과 덧셈 한 번이면 끝납니다. 그래서 널리 쓰입니다.
2
탐욕적 최선 우선 탐색 — 나침반이 가리키는 칸부터
4차시에서 만든 탐색의 뼈대를 다시 떠올려 봅시다. 아주 짧았습니다.
프론티어(가 볼 수는 있는데 아직 안 가 본 칸들의 대기실)에서 하나를 꺼내고,
그 이웃을 프론티어에 넣는다. 이것을 되풀이한다. 그게 전부였어요.
그때 배운 것은 프론티어에서 누구를 꺼내느냐가 알고리즘의 이름을 정한다는 사실입니다.
오늘은 그 자리에 세 번째 규칙을 넣습니다.
맨 앞에서 꺼낸다
너비 우선 탐색 (BFS)
가장 먼저 넣은 것부터. 가까운 곳부터 고르게 퍼진다.
모든 이동 비용이 같다면 최단을 보장한다.
맨 뒤에서 꺼낸다
깊이 우선 탐색 (DFS)
가장 나중에 넣은 것부터. 한 갈래를 끝까지 파고든다.
적게 둘러볼 때도 있지만 최단은 보장하지 않는다.
h 가 가장 작은 것을 꺼낸다
탐욕적 최선 우선 탐색
목표에 가장 가까워 보이는 칸부터.
오늘 새로 배우는 규칙이다.
탐욕적 최선 우선 탐색(greedy best-first search)은 이름이 곧 설명입니다.
'최선 우선'은 가장 좋아 보이는 것부터 본다는 뜻이고,
'탐욕적'은 지금 당장 좋아 보이는 것만 보고 뒤는 안 돌아본다는 뜻입니다.
식당에서 가장 맛있어 보이는 반찬부터 집어 먹는 것과 같아요.
나중에 배가 부를지는 생각하지 않습니다.
여기서 맹목적 탐색과 정보 이용 탐색(informed search)이 갈립니다.
BFS와 DFS는 문제에 대해 아무것도 모른 채 순서만 따졌습니다.
탐욕적 탐색은 h를 통해 이 문제가 어떤 문제인지를 씁니다.
그것이 '정보를 이용한다'는 말의 뜻입니다.
⚠️ 동점일 때는 어떻게 하나
프론티어에 h가 똑같은 칸이 여럿 있을 수 있습니다.
그때는 규칙이 하나 더 필요해요. 이 교과서와 아래 시뮬레이터는
행 번호가 작은 칸을 먼저, 행도 같으면 열 번호가 작은 칸을 먼저 꺼냅니다.
사소해 보이지만 사소하지 않습니다 — 동점 규칙을 '먼저 넣은 것부터'로 바꾸면
같은 미로에서 둘러보는 칸이 20칸에서 29칸으로 늘어납니다(실측).
두 알고리즘을 견줄 때는 이런 세부까지 맞춰야 공정한 비교가 됩니다.
세 규칙을 같은 미로에 돌리면 이렇게 나옵니다.
미로는 4차시에서 쓴 것과 완전히 같은 7행 12열이고, 벽이 아닌 칸은 65칸입니다.
꺼내는 규칙
이름
둘러본 칸
찾은 경로
최단인가
맨 앞
너비 우선 (BFS)
64
17걸음
O
맨 뒤
깊이 우선 (DFS)
22
19걸음
X
h가 가장 작은 것
탐욕적 (맨해튼)
20
19걸음
X
같은 미로 · 같은 뼈대 · 꺼내는 규칙만 바꾼 결과입니다. 셋 다 오늘 시뮬레이터에서 직접 확인합니다.
탐욕적 탐색은 20칸만 보고 목표에 닿았습니다. BFS의 3분의 1도 안 됩니다.
나침반의 값어치가 이 한 숫자에 있어요.
그런데 오른쪽 두 칸을 보면 이야기가 달라집니다.
19걸음. BFS가 찾은 17걸음보다 2걸음 깁니다.
그리고 여기서 더 놀라운 것은, 둘러본 칸 수와 경로 길이가 깊이 우선 탐색과 거의 같다는 점입니다.
정보를 쓴 탐색이 아무것도 모르는 탐색과 성적이 비슷하다면, 무언가 이상하지요.
3
탐욕적 탐색이 잃은 것 — 지나온 길을 잊었다
탐욕적 탐색이 칸을 고를 때 보는 값은 h하나뿐입니다.
여기까지 몇 걸음 걸어왔는지는 계산에 들어가지 않습니다.
이미 20걸음을 걸어온 칸이라도 목표에 세 칸 가깝다면, 방금 출발한 칸보다 먼저 꺼냅니다.
우리 미로에서 실제로 무슨 일이 일어나는지 따라가 봅시다.
탐욕적 탐색이 찾아낸 19걸음짜리 경로는 이렇습니다.
노란 두 칸을 보세요. (4, 11)까지 오른쪽 벽을 타고 쭉 내려오다가
아래가 벽이라 막힙니다. 그래서 왼쪽으로 한 칸 되돌아 (4, 10)으로 갑니다.
그 되돌아옴이 곧 2걸음 손해입니다.
나침반은 "오른쪽 아래로 가라"고만 말했고, 그 말만 듣고 끝까지 내려간 것이지요.
2걸음이면 별것 아닌 것처럼 보입니다.
하지만 이 손해는 미로 모양에 따라 얼마든지 커질 수 있습니다.
그 사정을 그림으로 보면 이렇습니다.
'ㄷ'자로 벽을 세우고 입을 목표 반대쪽으로 돌려놓으면,
목표 쪽으로만 달리는 탐색은 주머니 안으로 곧장 들어갑니다.
그리고 들어간 만큼 그대로 되돌아 나와야 합니다.
이 그림이 오늘 실습의 과제입니다.
여러분이 직접 이런 벽을 세워 탐욕적 탐색을 골탕 먹여야 해요.
미리 말해 두면, 잘 세우면 경로 차이가 2걸음에서 12걸음까지 벌어집니다.
교과서를 만들며 찾은 가장 큰 차이는 26걸음이었습니다(탐욕적 43걸음 대 BFS 17걸음).
그 기록을 깨는 것이 오늘의 도전 과제입니다.
📌 '탐욕적'이라는 이름은 탐색 밖에서도 쓴다
지금 당장 가장 이득인 것을 고르고 되돌아보지 않는 방식을
탐욕법(greedy algorithm)이라고 부릅니다.
거스름돈을 줄 때 큰 동전부터 집는 것이 대표적이에요.
우리나라 동전(500·100·50·10원)에서는 이 방법이 늘 최소 개수를 냅니다.
그런데 동전이 400원·300원·100원짜리인 나라라면 어떨까요?
600원을 만들 때 탐욕법은 400 + 100 + 100으로 3개를 쓰지만,
300 + 300이면 2개면 됩니다. 탐욕법은 대체로 빠르고 가끔 틀립니다.
그 '가끔'이 언제인지를 아는 것이 오늘의 공부입니다.
4
믿을 수 있는 어림 — 허용 가능성
어림은 아무 값이나 돌려주어도 될까요? 그럴 리 없습니다.
"남은 거리는 1이야"라고 늘 거짓말하는 어림을 쓰면 탐색이 엉망이 됩니다.
좋은 어림을 가르는 조건이 있어요. 그중 첫째가 허용 가능성입니다.
📐 허용 가능한 어림 (admissible heuristic)
어떤 칸에서도 실제 남은 비용보다 크지 않은 어림.
한마디로 절대 부풀리지 않는 어림입니다. 모자라는 것은 괜찮고, 넘치면 안 됩니다.
맨해튼 거리는 왜 이 조건을 만족할까요? 까닭은 개념 1에서 이미 나왔습니다.
맨해튼 거리는 벽을 아예 보지 않기 때문입니다.
벽이 없다고 치고 잰 거리이므로, 실제 미로에서는 벽 때문에 같거나 더 멀 수밖에 없어요.
길을 막는 벽이 새로 생긴다고 해서 길이 짧아지는 일은 없으니까요.
말로만 하면 미덥지 않으니, 오늘 실습에서 65칸을 전부 검사합니다.
목표에서 거꾸로 너비 우선 탐색을 한 번 돌리면 칸마다 진짜 남은 걸음 수가 나옵니다.
그 값과 어림을 65번 비교하면 됩니다. 결과를 미리 적어 두면 이렇습니다.
어림
실제를 넘긴 칸
딱 맞은 칸
가장 크게 모자란 폭
허용 가능한가
맨해튼 거리
0
31
8
O
직선거리
0
3
8
O
맨해튼 × 3 (부풀린 어림)
64
1
0
X
65칸 전부를 검사한 결과입니다. '맨해튼 × 3'이 안 넘긴 칸 1개는 목표 자신입니다(0의 3배는 0).
맨해튼 거리는 31칸에서 실제와 정확히 일치했고, 한 칸도 부풀리지 않았습니다.
직선거리도 부풀리지는 않지만 딱 맞은 칸이 3칸뿐입니다.
둘 다 안전하다면, 실제에 더 가까운 쪽이 더 쓸모 있는 힌트겠지요.
이 미로의 65칸 어디에서도 맨해튼 거리가 직선거리보다 작은 칸은 없습니다(52칸에서 크고 13칸에서 같음).
상하좌우로만 움직이는 문제에서 맨해튼 거리를 즐겨 쓰는 까닭이 이것입니다.
⚠️ 허용 가능하다고 최단이 보장되는 것은 아니다
여기서 아주 흔한 오해가 생깁니다.
오늘 쓴 맨해튼 거리는 허용 가능한 어림인데도,
탐욕적 탐색은 19걸음짜리 길을 내놓았습니다. 최단이 아니에요.
허용 가능성은 다음 두 차시에 배울 A*의 최단 보장 조건이지, 탐욕적 탐색의 조건이 아닙니다.
탐욕적 탐색이 최단을 못 찾는 까닭은 어림이 나빠서가 아니라
지나온 걸음 수를 아예 안 보기 때문입니다. 이 구멍을 메우는 것이 6차시입니다.
h를 0으로 두면 어떻게 되나
어림을 아예 안 쓰겠다는 것은 h(칸) = 0으로 두는 것과 같습니다.
모든 칸의 값이 0이면 우선순위가 전부 동점이 되지요.
그러면 남는 것은 동점 규칙뿐입니다 — 행이 작은 칸부터, 열이 작은 칸부터.
목표가 어디 있든 상관없이 왼쪽 위부터 차례로 훑는 탐색이 됩니다.
결과는 65칸 전부를 꺼내는 것입니다. 빈칸이 65칸이니 하나도 안 남기고 다 본 셈이에요.
나침반을 빼앗기면 정보 이용 탐색은 그냥 맹목적 탐색으로 되돌아갑니다.
오늘 시뮬레이터에서 이 값을 직접 확인하게 됩니다.
📌 64와 65 — 1칸 차이가 신경 쓰인다면
표를 나란히 보면 이상한 데가 눈에 띕니다.
너비 우선 탐색은 64칸인데 h = 0인 탐욕적 탐색은 65칸입니다.
빈칸이 65칸인데 BFS는 왜 하나를 안 볼까요? 버그가 아닙니다.
이 미로에서 목표까지 거리가 17인 칸은 딱 둘 — (6, 9)와 목표 (6, 11)입니다.
BFS는 큐 순서상 목표를 먼저 꺼내고 그 자리에서 끝나므로 (6, 9)를 영영 안 꺼냅니다.
반면 h = 0일 때는 동점 규칙이 열 번호가 작은 쪽을 먼저 꺼내므로
(6, 9)를 꺼낸 다음에 목표를 꺼냅니다. 그래서 한 칸이 더 셉니다.
같은 숫자가 나오지 않는다고 놀라지 말고, 어디서 갈렸는지를 찾는 것이
알고리즘을 견주는 사람의 일입니다. 7차시에서 이 (6, 9)를 다시 만나게 됩니다.
💻
손으로 — 세 방식을 재고, 함정을 직접 만든다
아래 시뮬레이터는 4차시와 똑같은 미로에서 시작합니다.
바꿀 수 있는 것은 세 가지예요 — 꺼내는 규칙(세 방식),
어림(맨해튼 · 직선거리 · 0), 그리고 벽입니다.
격자를 클릭하거나 끌면 벽이 생기고 지워집니다. 출발과 목표는 못 바꿔요.
🧭 나침반 시험대 — 탐욕적 탐색의 함정INTERACTIVE
방식과 어림을 고르고 ▶ 재생을 누르세요.
보라색이 이미 꺼내 본 칸, 하늘색이 아직 대기 중인 프론티어입니다.
칸 안의 작은 숫자가 그 칸의 어림 h예요.
격자를 클릭·드래그하면 벽이 토글됩니다.
꺼내는 규칙
둘러본 칸프론티어(대기실)벽찾은 경로출발 S목표 G
견본 미로
둘러본 칸0
프론티어1
지금 칸의 h—
찾은 경로—
빈칸65
성적표 — 다섯 줄을 모두 채워 공책에 옮겨 적으세요
방식
둘러본 칸
경로 걸음
최단인가
너비 우선 (BFS)
–
–
–
깊이 우선 (DFS)
–
–
–
탐욕적 · 맨해튼
–
–
–
탐욕적 · 직선거리
–
–
–
탐욕적 · h = 0
–
–
–
함정 판정 — BFS 와 탐욕적 · 맨해튼 두 줄을 채우면 여기에 판정이 뜹니다.
[안내] 방식을 고르고 ▶ 재생을 누르세요.
지금 격자를 코드로 옮기면 이렇습니다 (아래 실행기의 MAZE에 붙여 넣을 수 있어요).
MAZE = [...]
과제 ① 다섯 줄을 채운다 (5분)
원본 미로에서 다섯 가지 설정을 모두 돌려 성적표를 채우고 공책에 옮겨 적으세요.
⚡ 다섯 줄 한꺼번에를 누르면 한 번에 채워지지만,
적어도 두 줄은 ▶ 재생으로 움직임을 보면서 하세요.
숫자만 보면 놓치는 것이 있습니다 — 보라색이 어느 쪽으로 뻗는지가 오늘의 핵심이거든요.
BFS를 재생한다. 보라색이 물결처럼 사방으로 퍼집니다.
목표가 어느 쪽인지 모르니 모든 방향을 똑같이 대접해요.
탐욕적(맨해튼)을 재생한다. 보라색이 오른쪽 아래로 뾰족하게 뻗습니다.
이 뾰족함이 20칸의 정체입니다.
어림을 0으로 바꾸고 재생한다. 뾰족함이 사라지고
왼쪽 위부터 차례로 훑습니다. 나침반을 빼앗긴 모습이에요.
다섯 줄을 견준다. 어느 줄이 가장 적게 둘러보았나요?
그 줄의 경로는 최단인가요? 두 물음의 답이 같은 줄이 있습니까?
💡 이 값이 나와야 맞습니다
원본 미로에서는 BFS 64칸 17걸음 · DFS 22칸 19걸음 ·
탐욕적(맨해튼) 20칸 19걸음 · 탐욕적(직선거리) 18칸 17걸음 · 탐욕적(h=0) 65칸 17걸음입니다.
다르게 나온다면 벽을 이미 건드린 것이니 🔄 초기화를 누르세요.
넷째 줄이 눈에 걸릴 것입니다. 직선거리를 쓴 탐욕적 탐색은 18칸에 17걸음 —
더 적게 둘러보고 최단까지 찾았습니다. 맨해튼보다 낫습니다.
그렇다면 직선거리가 더 좋은 어림일까요? 이 미로에서만 그렇습니다.
벽 두 칸만 바꾸면 뒤집혀요. 과제 ③에서 확인합니다.
과제 ② ㄷ자 함정을 만든다 (7분) — 오늘의 본 과제
이제 여러분이 탐욕적 탐색을 이기는 미로를 만들 차례입니다.
개념 3의 그림을 다시 보고, 격자를 클릭·드래그해서 벽을 세우고 지우세요.
🎯 목표
탐욕적(맨해튼)의 경로가 BFS의 경로보다 6걸음 이상 길어지게 만드세요.
성공하면 시뮬레이터에 🏆 함정 제조 성공이 뜹니다.
원본 미로에서는 차이가 2걸음뿐이라 아직 배지가 안 뜹니다.
먼저 BFS와 탐욕적(맨해튼)을 한 번씩 돌려 지금 차이가 몇 걸음인지 확인합니다.
벽을 바꿀 때마다 성적표가 지워지니, 바꾼 뒤에는 다시 두 줄을 채워야 해요.
벽을 더하기만 해서는 잘 안 됩니다. 실제로 벽을 1~2개 더하는
2,016가지를 전부 해 보았는데 차이가 최대 4걸음이었습니다.
이미 있는 벽을 지워 새 길을 열어 주는 것이 요령입니다.
ㄷ자를 어디에 둘지 생각합니다. 탐욕적 탐색은 오른쪽 아래로 달려갑니다.
그 길목에 입이 왼쪽으로 열린 주머니를 만들어 두면 곧장 빨려 들어갑니다.
벽 세우기 4칸 — (5,5) (5,7) (5,8) (5,10).
그러면 5행이 ..#..#######가 되어 오른쪽 절반이 위아래로 갈립니다.
벽 지우기 2칸 — (6,7) (6,8). 그러면 6행이 ...........G가 되어
맨 아래에 목표까지 곧장 이어지는 새 통로가 생깁니다.
이 미로에서 탐욕적 탐색은 41칸을 둘러보고 29걸음짜리 길을 냅니다.
BFS는 63칸에 17걸음이고요. 차이 12걸음.
재생해서 무슨 일이 일어나는지 보세요. 탐욕적 탐색은 위쪽 길로
오른쪽 끝까지 달려갔다가, 5행 벽에 막혀 아래로 못 내려가고,
4열까지 되돌아 나온 뒤에야 6행으로 내려가 다시 오른쪽으로 갑니다.
들어간 만큼 그대로 나온 것이지요. 왜 이 배치가 먹히는지 알겠다면,
이제 더 깊은 주머니를 만들어 기록을 깨 보세요.
과제 ③ 어림을 바꿔 뒤집어 본다 (3분)
과제 ①에서 직선거리가 맨해튼보다 나았습니다. 그것이 규칙인지 우연인지 재 봅시다.
원본으로 초기화한 뒤 세 칸만 고칩니다.
(1, 11)의 벽을 지웁니다. 오른쪽 위 끝에 아래로 내려가는 샛길이 하나 열립니다.
(2, 10)을 벽으로 만듭니다. 2행에서 오른쪽으로 빠져나가던 길을 막습니다.
(3, 9)도 벽으로 만듭니다. 원래 최단 경로가 지나던 칸입니다.
세 칸을 다 고치면 이 미로의 최단 자체가 17걸음에서 19걸음으로 늘어납니다.
빈칸이 65칸에서 64칸으로 바뀌면 세 칸을 제대로 고친 것입니다.
탐욕적 · 맨해튼과 탐욕적 · 직선거리를 각각 돌려 견줍니다.
이 세 칸만으로 순서가 뒤집힙니다. 맨해튼은 20칸 19걸음,
직선거리는 27칸 21걸음이 됩니다. 이 미로에서는 맨해튼이 이겨요.
너비 우선 탐색도 이 미로에서는 63칸 19걸음이니,
맨해튼이 낸 19걸음이 곧 최단입니다. 직선거리만 2걸음을 더 걸은 셈이지요.
재생해서 어디서 갈렸는지 보세요. 직선거리는 비스듬한 방향을 더 좋게 칩니다.
그래서 (1, 7)에서 2행으로 내려간 뒤 아래로 (5, 8)까지 파고들었다가 되돌아 나옵니다.
찾아낸 길에도 그 흔적이 남아, 2행으로 내려갔다가 (2, 10)에 막혀 다시 1행으로 올라옵니다.
내려갔다 올라온 두 걸음이 그대로 손해예요.
맨해튼은 행 차이와 열 차이를 그냥 더할 뿐이라 그 미끼에 걸리지 않습니다.
교과서를 만들며 벽을 무작위로 바꾼 21,254가지를 세어 보았더니
직선거리 쪽이 더 짧은 경로를 낸 경우가 13,417가지, 같은 경우가 7,829가지,
더 긴 경우가 8가지였습니다. 대체로 낫지만 규칙은 아닙니다.
"어느 어림이 더 좋은가"라는 물음에 문제를 정하지 않고는 답할 수 없다는 뜻입니다.
그리고 — 어림을 직접 검사한다
시뮬레이터가 못 보여 주는 것이 하나 있습니다.
"맨해튼 어림이 정말 실제를 넘지 않는가"는 65칸을 전부 재 봐야 알 수 있어요.
아래 코드가 그 일을 합니다. 목표에서 거꾸로 너비 우선 탐색을 한 번 돌려
칸마다 진짜 남은 걸음 수를 구하고, 어림 셋과 하나씩 비교합니다.
빈칸 두 곳을 채우고 실행하세요.
💡 막혔을 때
빈칸 ①은 피타고라스 정리입니다.
math.sqrt( ) 안에 세로 차이의 제곱과 가로 차이의 제곱을 더해서 넣으세요.
제곱은 ** 2로 씁니다. 빈칸 ②는 부등호 하나입니다. '어림이 실제보다 크다'를 그대로 옮기면 돼요.
어림은 f(p), 실제는 REAL[p]입니다.
+ 1e-9를 오른쪽에 더해 두는 까닭은, 직선거리가 소수라서
5.000000001 같은 값이 실제 5보다 크다고 잘못 세어지는 것을 막기 위해서입니다. 미로를 바꿔 보고 싶다면 위 시뮬레이터의
MAZE = [...] 상자를 그대로 복사해 붙여 넣으세요.
여러분이 만든 함정 미로에서 어림이 얼마나 어긋나는지 잴 수 있습니다.
📖
정리 — 나침반은 빠르게 하지만 옳게 하지는 않는다
오늘 한 일을 한 문장으로 줄이면 이렇습니다.
탐색에 "목표가 저쪽"이라는 값 하나를 쥐여 주었더니, 훨씬 빨라졌지만 답이 나빠졌다.
물음
오늘의 답
어림(휴리스틱)이란?
칸 하나를 받아 목표까지 남은 비용의 짐작값을 돌려주는 함수 h
격자에서 무엇을 쓰나?
맨해튼 거리(가로 차 + 세로 차) · 직선거리(피타고라스)
탐욕적 탐색은 무엇을 하나?
프론티어에서 h가 가장 작은 칸을 꺼낸다. 지나온 걸음 수는 안 본다
얻은 것은?
둘러본 칸 64 → 20 (3배 넘게 빠르다)
잃은 것은?
경로 17 → 19걸음. 함정을 만들면 17 → 29걸음까지 벌어진다
허용 가능한 어림이란?
어떤 칸에서도 실제보다 부풀리지 않는 어림. 맨해튼은 65칸 전부에서 만족
h = 0이면?
우선순위가 전부 동점이 되어 맹목적 탐색으로 되돌아간다(65칸 전부)
마지막 줄이 다음 시간의 문을 엽니다.
탐욕적 탐색이 지는 까닭은 어림이 나빠서가 아니었습니다.
맨해튼 거리는 한 칸도 부풀리지 않는 훌륭한 어림이었어요.
문제는 지나온 걸음 수를 아예 안 본다는 데 있었습니다.
그러면 답은 뻔해 보입니다. 둘 다 보면 되지 않을까요?
지나온 비용 g와 남은 어림 h를 함께 저울에 올리는 것 —
그것이 6차시의 f = g + h이고,
7차시에서 여러분이 직접 코드로 옮길 A*입니다.
A*를 만든 세 사람 가운데 하나인 피터 하트가
로봇 Shakey 50주년 기념 행사에서 강연하는 모습입니다. 뒤 화면은 Shakey와 그 개발을 이끈 찰스 로즌의 옛 사진이에요.
1960년대 말 미국 SRI의 Shakey 연구진은 로봇이 방 안에서 길을 찾게 하려 했는데, 당시 컴퓨터로는 모든 길을 다 뒤질 수 없었습니다.
적게 보면서도 옳은 길을 찾는 방법이 절실했고,
하트·닐스 닐슨·버트럼 라파엘이 1968년에 내놓은 것이 바로 A*입니다.
오늘 배운 어림 h는 그 알고리즘의 절반입니다. 나머지 절반이 다음 시간에 옵니다.
출처: Dicklyon, Wikimedia Commons (CC BY-SA 4.0)
🔁 되돌아보기
오늘 우리는 탐색에 어림 h를 쥐여 주어
둘러보는 칸을 64칸에서 20칸으로 줄였고,
그 대가로 경로가 17걸음에서 19걸음으로 늘어나는 것을 확인했습니다.
그리고 벽을 직접 세워 그 차이를 12걸음까지 벌리는 반례를 만들었습니다.
다음 시간에는 g와 h를 함께 보는 f = g + h로
빠르면서 최단인 길이 정말 가능한지 확인합니다.
오늘 만든 함정 미로를 지우지 말고 적어 두세요 — 다음 시간에 그 미로를 다시 씁니다.
✅
확인 문제
✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.
1. 어림(휴리스틱)이 무엇인지 한 문장으로 정의하고,
격자 문제에서 쓸 수 있는 어림을 두 가지 들어 각각의 계산 방법을 쓰시오.
📖 모범 답안
정의 — 어림(휴리스틱)은 어떤 상태에서 목표까지 남은 비용이 대략 얼마인지를
값 하나로 답하는 함수다. 정확한 값이 아니라 짐작값이라는 점이 핵심이다
(정확한 값을 알면 탐색 자체가 필요 없다).
두 가지 — ① 맨해튼 거리: |행 차이| + |열 차이|.
상하좌우로만 움직일 때 벽이 없다면 정확히 이만큼 걸린다.
② 직선거리(유클리드 거리): √(행 차이² + 열 차이²). 피타고라스 정리로 잰 빗변.
둘 다 벽을 보지 않고 좌표만으로 계산하므로 값싸다.
2. 칸 (2, 1)에서 칸 (5, 6)까지의 맨해튼 거리를
계산 과정과 함께 구하시오. 같은 두 칸의 직선거리도 구하고,
두 값 중 어느 쪽이 큰지와 그 까닭을 쓰시오.
📖 모범 답안
맨해튼 거리 = |5 − 2| + |6 − 1| = 3 + 5 = 8
직선거리 = √(3² + 5²) = √34 ≈ 5.83
맨해튼이 더 크다. 직선거리는 두 점을 곧게 이은 빗변이고,
맨해튼 거리는 그 빗변을 이루는 두 변의 합이다.
삼각형에서 두 변의 합은 나머지 한 변보다 길므로(삼각부등식) 맨해튼이 항상 크거나 같다.
상하좌우로만 움직이는 격자에서는 빗변으로 갈 수 없으니,
맨해튼 쪽이 실제에 더 가까운 어림이다.
3. 오늘 시뮬레이터의 원본 미로에서
다섯 줄을 모두 돌린 결과를 옮겨 적으시오. 그리고 탐욕적 · h = 0이
65칸인데 너비 우선 탐색은 64칸인 까닭을 설명하시오.
📖 모범 답안
너비 우선 64칸 17걸음 / 깊이 우선 22칸 19걸음 /
탐욕적 맨해튼 20칸 19걸음 / 탐욕적 직선거리 18칸 17걸음 /
탐욕적 h=0 65칸 17걸음.
1칸 차이의 까닭 — 이 미로에서 목표까지 거리가 17인 칸은
(6, 9)와 목표 (6, 11) 둘뿐이다.
너비 우선 탐색은 큐 순서상 목표를 먼저 꺼내고 그 자리에서 탐색을 끝내므로
(6, 9)를 끝내 꺼내지 않는다 → 65칸 중 64칸.
h = 0인 탐욕적 탐색은 모든 칸의 우선순위가 동점이라 행·열이 작은 칸부터 꺼내는데,
(6, 9)는 목표 (6, 11)보다 열 번호가 작으므로 목표보다 먼저 꺼내진다 → 65칸.
알고리즘이 달라서가 아니라 마지막 동점 처리에서 갈린 것이다.
4. 오늘 여러분이 직접 만든 함정 미로에서
① 탐욕적 탐색이 둘러본 칸과 경로 걸음, ② 너비 우선 탐색이 둘러본 칸과 경로 걸음을 적고,
두 값을 견주어 '빠르게 찾기'와 '최선을 보장하기'가 왜 맞바꿈인지 한 줄로 쓰시오.
📖 모범 답안
미로마다 답이 다르므로 두 가지를 확인하면 된다.
① 탐욕적이 너비 우선보다 적게 둘러보았는가,
② 탐욕적의 경로가 너비 우선보다 길어졌는가. 둘 다 참이면 함정이 성립한 것이다.
견본 답(ㄷ자 견본 미로) — 탐욕적 41칸 29걸음 /
너비 우선 63칸 17걸음. 둘러본 칸은 22칸 적은데 경로는 12걸음 길다.
한 줄 — 탐욕적 탐색은 목표에 가까워 보이는 쪽만 보고 달리므로
살펴볼 칸이 줄지만, 지나온 걸음 수를 안 보기 때문에 되돌아 나온 걸음까지 경로에 남는다.
계산을 아끼는 만큼 답의 질을 치르는 것이다.
5. '허용 가능한(admissible) 어림'이 무엇인지 쓰고,
격자 미로에서 맨해튼 거리가 왜 그 조건을 만족하는지 설명하시오.
이어서 맨해튼 거리를 3배로 부풀린 어림을 쓰면 무슨 일이 생길지 예측하고,
오늘 실행한 결과로 확인하시오.
📖 모범 답안
정의 — 어떤 상태에서도 실제 남은 비용보다 크지 않은 어림.
모자라는 것은 괜찮지만 부풀리면 안 된다.
맨해튼이 만족하는 까닭 — 맨해튼 거리는 벽을 아예 보지 않고 좌표만으로 잰다.
벽이 없다고 치고 잰 값이므로, 벽이 있는 실제 미로에서는 같거나 더 멀 수밖에 없다.
길을 막는 벽이 생겼다고 길이 짧아지는 일은 없기 때문이다.
실행 결과로도 확인된다 — 65칸 전부에서 실제를 넘긴 칸이 0개,
정확히 일치한 칸이 31개였다.
3배로 부풀리면 — 허용 가능성이 곧바로 깨진다.
실행 결과 65칸 중 64칸에서 실제를 넘겼다(안 넘긴 1칸은 목표 자신, 0의 3배는 0).
부풀린 어림은 "저쪽은 아주 멀다"는 거짓말을 하므로,
실제로는 가까운 길을 살펴보기도 전에 제쳐 두게 만든다.
그러면 탐색은 더 빨라지지만 최단 경로를 놓칠 수 있다.
⚠️ 다만 허용 가능하다고 최단이 보장되는 것은 아니다 —
오늘 맨해튼 거리는 허용 가능했는데도 탐욕적 탐색은 19걸음을 냈다.
허용 가능성은 6·7차시의 A*에서 최단을 보장하는 조건이다.
6. [O/X] "정보 이용 탐색은 언제나 최단 경로를 찾는다."
O인지 X인지 판단하고, 오늘 만든 반례로 근거를 대시오.
또 이 문장을 참이 되도록 고쳐 쓰시오.
📖 모범 답안
X (거짓).
반례 — 오늘 쓴 원본 미로가 그대로 반례다.
탐욕적 최선 우선 탐색은 어림(정보)을 쓰는 정보 이용 탐색인데도
19걸음짜리 길을 냈다. 최단은 17걸음이고,
정보를 전혀 안 쓰는 너비 우선 탐색이 그 17걸음을 찾았다.
직접 만든 ㄷ자 함정 미로에서는 차이가 12걸음까지 벌어졌다.
고쳐 쓰기(어느 쪽이든 좋다) —
"정보 이용 탐색은 대개 더 적은 칸을 둘러보지만, 최단 경로를 보장하지는 않는다."
또는 "정보 이용 탐색 중에서도 지나온 비용과 남은 어림을 함께 보고,
그 어림이 허용 가능한 경우에만 최단 경로가 보장된다."
(뒤엣것이 6·7차시에서 배울 A*의 조건이다.)
🔎
더 알아보기
어림은 문제와 짝을 이룬다 — 움직임이 바뀔 때, 비용이 시간일 때, 그리고 탐욕이 오히려 나은 자리
원리 더 깊이
대각선으로도 갈 수 있다면 — 맨해튼 거리는 더 이상 안전하지 않다
오늘 미로에서는 상하좌우 네 방향으로만 움직였습니다. 그런데 게임 지도에서는 흔히 대각선 이동도 허용하지요.
그러면 (0, 0)에서 (3, 3)까지 그림 오른쪽처럼 세 걸음이면 갑니다.
맨해튼 거리는 여전히 3 + 3 = 6이라고 말해요. 실제보다 두 배로 부풀렸으니 허용 가능성이 깨졌습니다.
그래서 대각선을 허용하는 격자에서는 다른 어림을 씁니다. 대각선 한 걸음도 비용이 1이라면
체비쇼프 거리 max(|행 차|, |열 차|)가 벽이 없을 때의 걸음 수와 정확히 같습니다.
대각선 한 걸음을 실제 길이대로 √2(약 1.41)로 친다면 옥타일 거리(긴 쪽 + 0.41 × 짧은 쪽)가 딱 맞고,
이때는 직선거리도 실제를 넘지 않으니 안전합니다. 반대로 대각선 비용이 1인데 직선거리를 쓰면 √18 ≈ 4.24로, 역시 실제 3보다 커요.
교훈은 하나입니다. 어림은 외워 둔 '거리 공식'이 아니라 '그 문제에서 벽이 없다면 드는 비용'이어야 합니다.
같은 격자라도 갈 수 있는 방향과 걸음마다 매기는 비용이 바뀌면, 안전한 어림도 함께 바뀝니다.
현장
내비게이션은 '남은 거리'가 아니라 '남은 시간'을 어림한다
자동차 내비게이션이 줄이려는 비용은 대개 거리가 아니라 걸리는 시간입니다.
그러면 어림도 시간 단위여야 하지요. 남은 거리를 그대로 어림으로 쓰면 단위가 맞지 않습니다.
허용 가능한 시간 어림을 만드는 흔한 방법은 목적지까지의 직선거리를 그 도로망에서 낼 수 있는 가장 빠른 속도로 나누는 것입니다.
"아무리 빨라도 이만큼은 걸린다"는 값이라 절대 부풀려지지 않아요.
사진의 교차로처럼 옆 도로로 갈아타려고 둥근 연결로를 크게 빙 돌아야 하는 곳에서도, 이 어림은 모자랄 뿐 넘치지는 않습니다.
만약 평균 속도로 나눈다면 어떨까요? 막히지 않는 고속도로 구간에서는 실제로 걸리는 시간보다
어림이 커질 수 있어 허용 가능성이 깨집니다. 대신 값이 실제에 더 가까워 탐색은 빨라질 수 있지요.
안전한 쪽으로 어림할지, 빠른 쪽으로 어림할지 — 오늘 표에서 본 맞바꿈이 도로 위에서도 똑같이 나타납니다.
사진: 독일 쾰른 북쪽의 고속도로 교차로(쾰른-북) · 출처: El Grafo, Wikimedia Commons (CC BY-SA 3.0)
생각할 거리
그러면 탐욕적 탐색은 쓸모가 없을까
그렇지 않습니다. 오늘 확인한 것은 '최단을 보장하지 않는다'이지 '쓸모없다'가 아니에요.
그래프처럼 원본 미로에서 탐욕적 탐색은 둘러본 칸을 64에서 20으로 줄이고 2걸음만 더 걸었습니다.
ㄷ자 함정에서는 12걸음을 더 걸었지만, 그래도 둘러본 칸은 BFS보다 22칸 적었지요.
그래서 다음 같은 자리에서는 탐욕적 쪽을 고를 만합니다.
답이 조금 나빠도 되는 곳 — 예를 들어 게임 속 캐릭터 수백이 한꺼번에 길을 찾는다면
한 명이 두 걸음 더 걷는 것은 티가 나지 않지만, 한 명마다 지도를 다 뒤지면 화면이 버벅입니다.
기록할 공간이 모자란 곳 — 오늘 원본 미로에서 대기실에 칸을 넣은 횟수는 너비 우선이 64번, 탐욕적이 32번이었어요.
'이미 본 칸' 기록도 그만큼 적게 남습니다.
일단 답이 있어야 하는 곳 — 거친 답을 먼저 빨리 얻고, 시간이 남으면 다듬는 방식도 흔합니다.
공학의 판단은 늘 같은 모양입니다 — "이 문제에서 최적을 살 만한 값어치가 있는가?"
수술 로봇의 경로라면 사야 하고, 게임 캐릭터의 걸음이라면 안 사도 됩니다.
다음 시간에는 지나온 걸음까지 함께 저울에 올려, 덜 둘러보면서도 최단을 놓치지 않는 방법을 배웁니다.
