방송대 인공지능 3강: 휴리스틱 탐색과 A* 최적성
목표에 가까워 보이는 후보를 먼저 고르면 탐색은 빨라질 수 있지만, 그 판단이 항상 최적의 해를 보장하는 것은 아니다. 평가값에 어떤 정보를 넣는지, 나쁜 이동을 허용하는지, 휴리스틱이 실제 잔여비용을 넘지 않는지를 차례로 판정하여 언덕오르기·모의 담금질·A*를 구분한다.
후보를 선택하기 전에 네 가지를 질문한다
경험적 탐색(heuristic search)은 모든 방향을 똑같이 조사하지 않고, 대체로 목표에 유리하다고 알려진 경험적 규칙을 사용한다. 경험적 규칙은 많은 경우에 도움이 되는 판단 지침이지만 언제나 옳은 법칙은 아니다. 따라서 “값이 작으니 고른다”에서 멈추지 말고 그 값이 무엇을 재는지 먼저 밝혀야 한다.
판단 질문: ① 이미 사용한 비용을 보는가, ② 남은 비용의 예측치를 보는가, ③ 현재 후계노드만 비교하는가 OPEN 전체를 비교하는가, ④ 당장 나빠지는 이동도 허용하는가?
언덕오르기는 현재 위치의 후계노드 가운데 예측값이 가장 좋은 하나를 택한다. 모의 담금질은 때때로 나쁜 후계상태도 받아들인다. A*는 출발점부터 쓴 비용과 목표까지 남았다고 예측한 비용을 합쳐 OPEN 전체에서 최소 후보를 고른다. 세 방법은 모두 평가값을 쓰지만 정보의 범위와 선택 규칙이 다르다.
평가값은 이미 쓴 비용과 앞으로의 예측을 분리해 읽는다
출발노드 S에서 현재노드 n까지 실제로 소비한 경로비용을 g(n)이라 한다. n에서 목표 G까지 실제로 필요한 최소비용은 h(n)이지만, 탐색 중에는 정답 경로를 아직 모르므로 보통 정확한 h(n)을 알 수 없다. 경험적 지식으로 이를 추정한 값이 ĥ(n)이다.
| 기호 | 뜻 | 계산 시점의 성격 | 혼동 방지 질문 |
|---|---|---|---|
| g(n) | S에서 n까지 이미 소비한 비용 | 발견한 경로에서 계산한 값 | 지금까지 얼마를 썼는가? |
| h(n) | n에서 G까지의 실제 최소비용 | 대개 탐색 전에 알 수 없는 참값 | 실제로 앞으로 얼마가 필요한가? |
| ĥ(n) | h(n)의 휴리스틱 예측치 | 문제 지식을 이용한 추정값 | 앞으로 얼마가 들 것처럼 보이는가? |
| f̂(n) | g(n)+ĥ(n) | n을 거치는 전체 경로비용의 예측치 | 지금까지와 앞으로를 합치면 얼마인가? |
평가함수는 어떤 상태가 목표 탐색에 얼마나 바람직한지를 수치로 나타내는 척도다. 무엇을 평가함수에 넣느냐에 따라 탐색의 행동이 바뀐다. ĥ만 보면 목표 방향을 강하게 좇지만 돌아온 비용을 잊고, g만 보면 확실히 싼 경로부터 보지만 목표 방향의 단서를 쓰지 못한다.
같은 후보표에서도 탐색 규칙에 따라 선택이 달라진다
현재 OPEN에 A, B, C가 있고 아래와 같이 계산되었다고 하자. 이 표는 같은 상태정보를 놓고 알고리즘이 무엇을 우선하는지 분리해 보는 연습이다.
| 후보 | g | ĥ | f̂=g+ĥ |
|---|---|---|---|
| A | 2 | 7 | 9 |
| B | 5 | 2 | 7 |
| C | 7 | 1 | 8 |
균일비용 관점에서는 g가 가장 작은 A가 먼저다. 언덕오르기에서는 현재 상태에서 만들어진 후계노드들이라는 조건 아래 ĥ가 가장 작은 C를 택한다. A*는 f̂가 가장 작은 B를 택한다. “평가값이 최소인 노드”라는 말만 외우면 세 답을 구별할 수 없고, 평가식의 구성 요소까지 확인해야 한다.
언덕오르기는 현재 위치에서 가장 좋아 보이는 한 걸음을 택한다
언덕오르기 탐색은 현재상태를 확장해 만든 후계노드 중 ĥ(n)이 최소인 노드를 다음 상태로 선택한다. 선택한 방향을 따라 계속 전진한다는 점에서 깊이우선 탐색과 비슷한 진행 모양을 보이지만, 생성 순서가 아니라 휴리스틱 값으로 갈래를 고른다는 차이가 있다.
8-퍼즐에서는 “목표 위치에 있지 않은 조각의 수”를 ĥ로 사용할 수 있다. 강의의 초기상태는 잘못 놓인 조각이 4개이므로 ĥ=4다. 한 번 움직인 세 후계상태의 값이 각각 5, 3, 5라면 언덕오르기는 가운데의 ĥ=3인 상태만 따라간다. 이때 그 상태까지 몇 번 이동했는지를 나타내는 g는 선택식에 넣지 않는다.
잘못된 풀이: “현재까지 이동 횟수가 적으니 언덕오르기가 선택한다”는 설명은 g와 ĥ를 섞은 것이다. 언덕오르기의 강점은 단순한 국소 판단이고, 약점도 지나온 경로와 다른 유망 후보를 충분히 보지 않는 데서 생긴다.
멈춘 모양을 보면 고원·능선·지역최적점을 진단할 수 있다
등산 문제에서 상태는 등산가의 좌표와 고도, 연산자는 동·서·남·북으로 일정 거리 이동하는 동작이다. 주변 네 지점 중 고도가 가장 높은 곳으로 이동하는 최급상승법은 눈앞의 개선을 반복한다. 그러나 “주변보다 높다”와 “산 전체에서 가장 높다”는 같은 말이 아니다.
| 실패 지형 | 관찰되는 현상 | 왜 단순 국소 선택이 곤란한가 |
|---|---|---|
| 지역최대치 | 주변은 모두 낮지만 더 먼 곳에 더 높은 정상 존재 | 일시적으로 내려가지 않으면 다른 봉우리로 갈 수 없음 |
| 고원 | 여러 이웃의 평가값이 같아 개선 방향이 드러나지 않음 | 동률만으로는 진행 방향이나 출구를 판별하기 어려움 |
| 능선 | 좋은 방향이 허용된 이동축과 비스듬히 놓임 | 동·서·남·북 한 걸음만 보면 지그재그나 정체가 발생함 |
등산은 고도를 최대화하는 표현이고 8-퍼즐의 ĥ는 비용을 최소화하는 표현이다. 부호와 목표는 반대처럼 보여도 “현재 이웃 중 가장 좋아 보이는 곳으로만 이동한다”는 구조는 같다. 시험에서는 최대화·최소화의 말보다 국소 정보만 쓰는지 확인한다.
모의 담금질은 초기에 우회하고 후기에 수렴한다
모의 담금질(simulated annealing)은 금속이나 유리를 가열한 뒤 천천히 식히는 풀림 과정에서 이름을 얻은 확률적 최적화 방법이다. 현재상태보다 평가값이 좋아지는 후계상태는 받아들이고, 나빠지는 후계상태도 온도에 따른 확률로 받아들여 지역최적점에서 빠져나갈 가능성을 만든다.
- 시간 t의 온도 T를 냉각 일정 temperature(t)로 계산한다.
- 현재상태의 후계노드 하나를 임의로 고른다.
- 최소화 문제에서 ΔE= h(차기상태)-h(현재상태)를 계산한다.
- ΔE<0이면 차기상태가 개선되므로 항상 이동한다.
- ΔE≥0이면 확률 e-ΔE/T로 나쁜 이동을 받아들인다.
- T가 0이 되면 현재상태를 반환한다.
무작위로 후계상태를 고른다는 사실과 아무 기준 없이 이동한다는 말은 다르다. 선택 후보는 임의지만 수용 여부는 개선량 ΔE와 온도 T가 결정한다.
온도와 손해값을 넣어 수용확률을 직접 계산한다
현재 평가값이 7이고 차기상태가 9라면 최소화 문제에서 ΔE=9-7=2다. 나빠진 정도는 같아도 온도가 달라지면 수용확률은 크게 달라진다.
| 온도 T | 계산 | 수용확률 | 해석 |
|---|---|---|---|
| 10 | e-2/10 | 약 0.819 | 초기에는 우회 이동을 비교적 자주 허용 |
| 2 | e-2/2=e-1 | 약 0.368 | 탐색과 수렴의 중간 단계 |
| 0.5 | e-2/0.5=e-4 | 약 0.018 | 후기에는 나쁜 이동을 거의 거부 |
같은 T에서 ΔE가 클수록 지수가 더 작은 값이 되어 수용확률이 낮아진다. 같은 ΔE에서 T가 클수록 확률은 1에 가까워지고, T가 0에 가까워질수록 0에 가까워진다. ΔE<0인 개선 이동은 이 확률식을 적용하기 전에 항상 받아들인다.
검산 규칙: 나쁜 이동인데 계산한 확률이 1보다 크거나 음수라면 부호 또는 식을 잘못 넣은 것이다. e-ΔE/T는 ΔE≥0, T>0에서 0과 1 사이에 있어야 한다.
냉각 일정은 탐색과 수렴의 균형을 정한다
온도를 너무 빨리 낮추면 나쁜 이동을 거의 허용하지 않아 언덕오르기처럼 지역최적점에 갇힐 수 있다. 반대로 높은 온도를 지나치게 오래 유지하면 여러 지역을 탐색할 수 있지만 좋은 상태에 안정적으로 머무는 시간이 늦어진다. 핵심은 초기에 탐색 범위를 넓히고 후기에 선택을 보수적으로 바꾸는 것이다.
모의 담금질은 “나쁜 상태도 무조건 선택한다”거나 “반드시 전역최적해를 즉시 찾는다”는 방법이 아니다. 확률적 우회를 허용해 국소 함정을 벗어날 가능성을 높이는 접근이다. 결과는 후계상태 선택, 냉각 일정과 실행 과정에 따라 달라질 수 있다.
A*는 경로 장부와 목표 예측을 한 식에 결합한다
A*의 평가함수는 f̂(n)=g(n)+ĥ(n)이다. g는 이미 실제로 지불한 비용이므로 확실하지만, ĥ는 앞으로 필요한 비용의 예측이다. A*는 OPEN에서 f̂가 최소인 노드를 꺼내 CLOSED에 넣고, 목표인지 검사한 뒤 후계노드를 생성한다.
앞의 후보표에서 A는 목표까지 멀어 보이지만 g=2로 싸게 도착했고, C는 목표에 가까워 보이지만 이미 g=7을 썼다. B는 g=5와 ĥ=2의 합이 7로 가장 작으므로 A*가 먼저 확장한다. 현재까지의 비용과 목표 방향 중 한쪽만 보는 것이 아니라 둘의 합으로 예상 총비용을 비교한 결과다.
- 출발노드 S의 f̂를 계산해 OPEN에 넣는다.
- OPEN에서 f̂가 가장 작은 n을 꺼내 CLOSED로 옮긴다.
- n이 목표이면 성공하고, 아니면 후계노드들의 g, ĥ, f̂를 계산한다.
- 중복 상태를 처리한 뒤 후보를 OPEN에 넣는다.
- OPEN이 비면 탐색 실패다.
중복 상태는 위치뿐 아니라 경로 장부까지 고친다
같은 상태는 남은 목표비용의 예측치 ĥ도 같다고 본다. 따라서 OPEN에 동일 상태가 두 경로로 들어오면 f̂가 큰 항목을 제거하면 된다. 실제로는 ĥ가 같으므로 g가 더 작은 경로를 남기는 것과 같다.
CLOSED에 있던 상태 old가 더 싼 새 경로 new로 다시 발견되면 처리가 더 중요하다. f̂(old)≤f̂(new)이면 new를 버린다. 반대로 f̂(old)>f̂(new)이면 새 노드 자체는 제거하되 old의 부모 포인터를 new의 부모로 바꾸고, old와 그 후계노드들의 g와 f̂를 갱신한다. 이미 확장된 아래쪽 경로도 비용 변화의 영향을 받기 때문이다.
오개념 분석: 중복 상태를 무조건 삭제하면 더 싼 우회 경로를 잃을 수 있다. 상태 동일성 확인, 두 f̂ 비교, 부모 포인터 수정, 후계노드 비용 전파를 하나의 절차로 기억한다.
휴리스틱을 과대평가하지 않아야 최적비용을 보장한다
A*가 최소비용 경로를 보장하려면 강의 범위에서 모든 n에 대해 ĥ(n)≤h(n)이어야 한다. 즉 목표까지 실제로 필요한 비용보다 휴리스틱이 더 크다고 예측하지 않아야 한다. 이런 휴리스틱을 과대평가하지 않는 휴리스틱으로 이해할 수 있다.
예를 들어 어떤 노드에서 실제 잔여비용 h가 6이라면 ĥ=4 또는 6은 조건을 만족하지만 ĥ=8은 위반한다. ĥ=0은 조건을 안전하게 만족하지만 목표 방향 정보가 약해져 탐색량을 많이 줄이지 못한다. 따라서 값이 작기만 한 휴리스틱보다 실제 비용을 넘지 않으면서도 h에 가까운 예측이 유용하다.
판정 순서: 실제 잔여비용 h와 예측 ĥ의 대소를 확인한다. ĥ≤h이면 최적성 조건을 만족하고, ĥ>h인 상태가 하나라도 있으면 이 강의에서 제시한 최소비용 보장을 그대로 주장할 수 없다.
8-퍼즐에서는 이동 횟수와 잘못 놓인 조각 수를 더한다
강의의 A* 8-퍼즐 예제는 g(n)을 빈칸의 이동 횟수, ĥ(n)을 목표 위치에 있지 않은 조각의 수로 둔다. 초기상태에서는 g=0, ĥ=4이므로 f̂=4다. 한 번 이동한 후보들의 f̂가 1+5=6, 1+3=4, 1+5=6이라면 가운데 상태가 선택된다.
그 뒤에도 한 단계의 ĥ만 보지 않고 누적 이동 횟수 g를 더한다. 목표상태에서는 ĥ=0이지만 g는 5이므로 f̂=5다. “목표이므로 평가함수도 0”이라고 쓰면 이미 사용한 이동비용 g를 빠뜨린 것이다. 이 점이 ĥ만 사용하는 언덕오르기와 A*의 결정적 차이다.
잘못 놓인 조각 수는 목표와 다른 칸을 세기 때문에 계산이 쉽다. 다만 서로 다른 두 상태가 같은 ĥ를 가질 수 있으며, 그때 A*는 g까지 합친 f̂로 후보를 비교한다.
도시 그래프에서는 f̂ 장부를 따라 최단경로를 검산한다
강의의 도시 그래프에서 도로비용은 a-b=6, a-c=4, b-c=5, b-d=7, b-e=6, c-d=3, c-e=8, d-f=3, e-g=3, f-g=2다. 목표 g까지의 직선거리 휴리스틱은 a=9, b=6.5, c=7, d=4, e=2.5, f=1, g=0으로 주어진다.
| 확장 | 주요 후보의 f̂ 계산 | 다음 선택 |
|---|---|---|
| a | b: 6+6.5=12.5, c: 4+7=11 | c |
| c | b: 9+6.5=15.5, d: 7+4=11, e: 12+2.5=14.5 | d |
| d | b: 14+6.5=20.5, f: 10+1=11 | f |
| f | g: 12+0=12 | g |
확장 순서는 a→c→d→f→g이고 복원한 경로의 실제 비용은 4+3+3+2=12다. f̂는 다음 노드를 고르는 예상 총비용이고, 최종 답의 비용은 선택된 경로의 실제 도로비용 g를 합해 검산한다. 직선거리 휴리스틱을 결과 비용에 한 번 더 더하지 않는다.
목표와 위험에 맞춰 탐색 방법을 판정한다
| 판단 조건 | 적합한 관점 | 반드시 점검할 위험 |
|---|---|---|
| 현재 이웃의 휴리스틱만으로 빠르게 개선하고 싶다 | 언덕오르기 | 지역최적점·고원·능선 |
| 일시적 악화를 허용해 국소 함정을 벗어나고 싶다 | 모의 담금질 | 냉각 속도와 확률적 결과 |
| 경로비용과 목표 예측을 함께 쓰고 최적경로를 원한다 | A* | ĥ≤h와 중복 경로 갱신 |
자가 점검할 때는 후보 하나를 골라 g, ĥ, f̂를 따로 적어 본다. 이어서 언덕오르기라면 ĥ, A*라면 f̂ 중 무엇을 비교할지 말하고, 나쁜 이동을 허용한다면 모의 담금질의 ΔE와 T를 계산한다. 마지막으로 A*의 최적성을 묻는 문제에서는 ĥ≤h를 별도로 확인한다.
핵심 개념 정리
- 휴리스틱: 대부분의 경우 유용하지만 항상 정답인 것은 아닌 경험적 규칙을 평가함수에 반영한다.
- 비용 분리: g는 이미 쓴 실제 비용, h는 실제 잔여비용, ĥ는 잔여비용의 예측이다.
- 국소 선택: 언덕오르기는 현재 후계노드의 ĥ만 비교하므로 지역최적점·고원·능선에 취약하다.
- 확률적 우회: 모의 담금질은 ΔE≥0인 악화 이동을 e-ΔE/T 확률로 허용하며 온도가 낮아질수록 보수적으로 변한다.
- 전체비용 예측: A*는 f̂=g+ĥ가 최소인 OPEN 후보를 확장하고 중복 경로의 비용과 부모 포인터를 관리한다.
- 최적성: 모든 상태에서 ĥ≤h이면 강의의 조건 아래 A*가 최소비용 경로를 보장한다.
문제를 풀 때는 “평가값의 구성 요소는 무엇인가 → 비교 범위는 현재 후계노드인가 OPEN 전체인가 → 악화 이동을 허용하는가 → 중복 상태의 더 싼 경로를 어떻게 반영하는가 → 휴리스틱이 실제 잔여비용을 넘지 않는가”의 순서로 판정한다. 알고리즘 이름보다 후보가 선택되는 근거를 식과 장부로 설명할 수 있어야 한다.
예상문제 10선
1. 경험적 탐색에서 경험적 규칙을 가장 정확하게 설명한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 경험적 규칙은 최적해를 자동으로 증명하는 보편 법칙이 아니다.
- ② 오답: 방문 노드 저장은 OPEN·CLOSED 같은 탐색 관리의 역할이다.
- ③ 오답: 이미 소비한 실제 비용은 g이며 경험적 예측과 구분한다.
- ④ 정답: 경험적 규칙은 대부분의 경우 잘 맞는 지식을 이용해 목표에 유리한 후보를 고르게 한다.
2. g(n)의 의미는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: g는 출발점부터 현재 노드까지 실제로 누적된 경로비용이다.
- ② 오답: 목표까지의 실제 최소 잔여비용은 h다.
- ③ 오답: 목표까지의 경험적 예측치는 ĥ다.
- ④ 오답: 수용확률은 모의 담금질에서 ΔE와 T로 계산한다.
3. 후보 A(g=2, ĥ=7), B(g=5, ĥ=2), C(g=7, ĥ=1)가 현재상태의 후계노드라면 언덕오르기가 고를 후보는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: g 최소 선택은 언덕오르기의 기준이 아니다.
- ② 정답: 언덕오르기는 현재 후계노드 중 ĥ가 최소인 C를 택한다.
- ③ 오답: g+ĥ가 최소인 B를 고르는 것은 A*의 판단이다.
- ④ 오답: 휴리스틱 값이 서로 다르므로 언덕오르기의 우선순위가 정해진다.
4. 최소화 문제에서 현재값이 6, 차기값이 9일 때 모의 담금질의 악화 이동 수용확률은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 이 식은 T가 커질수록 1을 넘을 수 있어 확률이 될 수 없다.
- ② 오답: 모의 담금질의 지수는 -ΔE/T이며 T와 ΔE의 위치를 바꾸지 않는다.
- ③ 정답: ΔE=9-6=3이므로 수용확률은 e-3/T다.
- ④ 오답: 악화 이동도 T가 0보다 크면 0이 아닌 확률로 받아들일 수 있다.
5. 최소화 문제의 모의 담금질에서 ΔE<0이면 어떻게 하는가?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: ΔE가 음수이면 차기 평가값이 더 작아진 개선 이동이므로 확률 계산 없이 받아들인다.
- ② 오답: 개선 이동의 수용 여부는 온도와 무관하다. 온도는 악화 이동을 확률적으로 받아들이는 정도를 조절한다.
- ③ 오답: 실제 ΔE를 0으로 바꾸면 개선 여부를 잃는다. 음수인 값을 확인한 즉시 이동을 받아들인다.
- ④ 오답: 개선 폭이 작더라도 ΔE가 음수이면 개선 이동이므로 악화 이동용 확률 계산을 적용하지 않는다.
6. 후보 A(g=2, ĥ=7), B(g=5, ĥ=2), C(g=7, ĥ=1) 중 A*가 먼저 선택할 후보는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: A의 f̂는 g만이 아니라 ĥ도 더해 9다.
- ② 오답: C의 ĥ는 최소지만 f̂는 7+1=8로 B보다 크다.
- ③ 정답: B의 예상 총비용 f̂=7이 A의 9와 C의 8보다 작다.
- ④ 오답: 세 후보의 f̂는 각각 9, 7, 8로 서로 다르다.
7. A*에서 동일 상태가 OPEN에 두 경로로 존재할 때의 올바른 처리는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 생성 순서만 고집하면 더 싼 도달 경로를 버릴 수 있다.
- ② 정답: 동일 상태는 ĥ가 같으므로 f̂ 비교를 통해 더 싼 경로를 남긴다.
- ③ 오답: 동일 상태의 남은 문제는 같으므로 경로마다 ĥ를 임의로 바꾸지 않는다.
- ④ 오답: OPEN은 아직 확장되지 않은 후보이며 중복 둘을 모두 확정하지 않는다.
8. 강의에서 A*가 최소비용 경로를 보장하기 위한 휴리스틱 조건은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 실제 잔여비용보다 크게 예측하면 유망한 최적 경로가 불리하게 평가될 수 있다.
- ② 오답: 목표에서 휴리스틱이 0인 것만으로는 중간 상태의 과대평가를 막지 못하므로 전체 상태에 대한 조건이 필요하다.
- ③ 오답: 음수가 아니라는 조건만으로는 실제 잔여비용보다 큰 과대평가를 허용하므로 최적성 조건이 되지 못한다.
- ④ 정답: 휴리스틱이 실제 잔여비용을 과대평가하지 않아야 강의의 최소비용 보장이 성립한다.
9. 강의의 A* 8-퍼즐 예제에서 g(n)으로 사용한 값은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 잘못 놓인 조각 수는 목표까지의 예측치 ĥ로 사용한다.
- ② 정답: 각 빈칸 이동의 비용을 1로 보아 누적 이동 횟수가 g가 된다.
- ③ 오답: 잘못 놓인 조각 수는 목표까지 남은 비용을 예측하는 ĥ이며 이미 이동한 비용 g가 아니다.
- ④ 오답: 빈칸 이동 횟수와 잘못 놓인 조각 수의 합은 f̂=g+ĥ이며 g 하나의 정의와 다르다.
10. 강의의 도시 그래프에서 A*가 찾은 경로와 실제 비용의 조합은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: a-b-e-g의 도로비용은 6+6+3=15로 최솟값 12보다 크다.
- ② 오답: a-c-e-g도 4+8+3=15이므로 선택 경로보다 비싸다.
- ③ 정답: A*의 확장 순서는 a, c, d, f, g이며 경로비용은 4+3+3+2=12다.
- ④ 오답: a-b-d-f-g는 6+7+3+2=18로 더 큰 비용이 든다.
참고 자료와 작성 기준
이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 개념 관계, 계산 예제와 문제 해설은 학습자의 이해를 돕도록 구성하고 검토했습니다.
- 작성·편집: 올에이클래스 학습연구팀
- 주요 근거: 한국방송통신대학교 컴퓨터과학과 「인공지능」 3강 ‘문제풀이(2)’ 강의자료(2025)
- 보충 자료: 외부 보충 자료를 사용하지 않고 해당 강의자료의 범위 안에서 재구성했습니다.
- 편집 원칙: 올에이클래스 편집 정책
- 최종 내용 검토: 2026-08-17
댓글
댓글 쓰기