방송대 방통대 인공지능 3강 - 문제풀이(2) - 요약 노트 시험족보 예상문제 - 올에이클래스

 

인공지능 3강 - 문제풀이(2)

이번 강의에서는 경험적 지식을 탐색에 활용하는 방법을 배웁니다. 언덕오르기 탐색과 모의 담금질의 차이를 이해하고, A* 알고리즘의 평가함수·중복 노드 처리·최적성 조건을 8-퍼즐과 경로 탐색 예제로 확인합니다.

경험적 탐색과 평가함수

경험적 탐색의 개념

경험적 탐색(heuristic search)은 목표상태를 더 신속하게 찾기 위해 경험적 규칙을 사용하는 탐색 방법입니다. 경험적 규칙(rule of thumb)은 항상 옳다고 보장되지는 않지만 대부분의 경우에 잘 맞는 규칙입니다. 모든 가능성을 같은 비중으로 조사하기보다 목표에 가까워 보이는 상태를 우선하도록 탐색 방향을 안내합니다.

경험적 지식은 평가함수(evaluation function)에 반영됩니다. 평가함수는 어떤 상태가 목표상태 탐색에 얼마나 바람직한지를 수치로 평가하는 척도입니다. 목표까지 가는 데 필요한 비용이나 그 상태가 해로 향하는 경로 위에 있을 가능성 등을 평가 기준으로 삼을 수 있습니다.

평가함수의 세 가지 비용

기호	의미	확정 여부
g(n)	출발노드 S에서 현재 노드 n까지 도달하는 데 소비한 경로비용	이미 지나온 경로의 실제 비용
h(n)	현재 노드 n에서 목표노드 G까지 도달하는 데 필요한 경로비용	실제 남은 비용
ĥ(n)	경험적 지식을 이용하여 h(n)을 예측한 비용	목표까지 남은 비용의 추정치

탐색 시점에는 출발점에서 현재 노드까지 지나온 경로를 알고 있으므로 g(n)은 계산할 수 있습니다. 그러나 목표까지 이어지는 실제 최적 경로를 아직 모르므로 h(n)을 곧바로 알 수 없는 경우가 많습니다. 이때 경험적 지식을 사용한 ĥ(n)으로 h(n)을 추정합니다.

시험 핵심: g(n)은 이미 지불한 실제비용이고, h(n)은 앞으로 필요한 실제비용이며, ĥ(n)은 그 앞으로의 비용에 대한 예측치입니다.

언덕오르기 탐색

탐색 순서와 선택 기준

언덕오르기 탐색은 현재상태를 확장하여 생성한 후계노드들 가운데 다음에 확장할 노드를 하나 선택합니다. 선택된 가지를 따라 진행한다는 점에서 탐색 순서는 깊이우선 탐색과 유사하지만, 아무 후계노드나 고르는 것이 아니라 평가함수로 계산한 비용이 최소인 노드를 선택합니다.

강의에서 언덕오르기 탐색의 평가함수는 ĥ(n)입니다. 즉, 후계노드 n에서 목표노드 G까지 도달하는 비용의 예측값만 비교합니다. 출발노드에서 그 후계노드까지 이미 사용한 경로비용 g(n)은 고려하지 않습니다. 이 때문에 현재 위치에서 좋아 보이는 선택을 빠르게 할 수 있지만 전체 경로비용을 기준으로 한 최적성을 보장하지는 못합니다.

8-퍼즐 예제

8-퍼즐에서는 한 번의 연산으로 빈칸과 인접한 조각을 바꾸어 초기상태를 목표상태로 변환합니다. 강의의 언덕오르기 예제는 목표상태와 비교했을 때 지정된 위치에 있지 않은 조각의 수를 상태의 비용으로 사용하며, 초기상태의 비용은 4입니다.

현재상태에서 가능한 후계상태들의 비용을 계산한 다음 가장 작은 값을 가진 상태를 선택하고, 그 상태에서 다시 같은 과정을 반복합니다. 누적 이동 횟수가 아니라 매 순간 목표 배열과 다른 조각 수만 보고 전진한다는 점이 핵심입니다. 비용이 같은 후계상태가 여러 개라면 이 평가만으로는 어느 쪽이 더 좋은 전체 경로인지 판별하기 어렵습니다.

8-퍼즐의 ‘제 위치에 있지 않은 조각 수’는 목표까지 남은 비용을 추정하는 경험적 척도입니다. 실제로 필요한 이동 횟수와 항상 같지는 않습니다.

계수최적화와 최급상승법의 난제

등산 문제로 이해하는 최급상승법

강의는 초행길의 산에서 짙은 안개를 만난 등산가의 상황으로 계수최적화 문제를 설명합니다. 지도와 길이 보이지 않을 때 등산가는 현재 위치 주변의 고도를 조사하고 더 높은 방향으로 이동하는 선택을 반복할 수 있습니다. 상태는 등산가의 좌표와 고도이고, 연산자는 동·서·남·북으로 정해진 거리만큼 이동하는 것입니다.

이 표현에서 모든 후계상태의 고도가 현재상태보다 낮은 상태가 목표상태입니다. 주변에서 가장 가파르게 상승하는 방향을 택하는 방식을 최급상승법(steepest ascent method)이라고 합니다. 그러나 주변 정보만으로 판단하므로 현재 지점이 산 전체에서 가장 높은 지점인지는 알 수 없습니다.

지역최대치·고원·능선 문제

난제	상태공간의 모습	탐색이 어려운 이유
지역최대치 문제	현재 위치는 주변보다 높지만 다른 곳에 더 높은 봉우리가 있음	모든 인접 상태가 나빠 보여 전역최대치 전에 멈춤
고원문제	넓은 영역에서 평가값이 같거나 거의 같음	어느 방향이 개선 방향인지 판단하기 어려움
능선문제	좋은 방향이 연산자가 허용하는 축과 비스듬히 놓임	한 번의 단순 이동으로 능선을 따라가기 어려워 진전이 느리거나 막힘

시험 핵심: 언덕오르기 탐색은 국소 정보에 의존하므로 현재보다 당장 좋아지는 후계상태가 없다고 해서 전역 최적해에 도달했다고 단정할 수 없습니다.

모의 담금질

개념과 물리적 비유

모의 담금질(simulated annealing)은 평가함수의 값이 전역최소치 또는 전역최대치에 해당하는 해를 구하기 위한 확률적 접근방법입니다. 담금질은 금속이나 유리를 일정한 온도로 가열한 다음 천천히 식혀 내부 조직을 고르게 하고 응력을 제거하는 열처리 조작입니다. 탐색에서도 처음에는 상태를 비교적 자유롭게 이동하게 하고 시간이 흐를수록 이동을 안정시키는 방식으로 이 과정을 모방합니다.

최소화 문제를 기준으로 보면 모의 담금질은 현재보다 평가값이 작은 상태는 받아들이고, 평가값이 커지는 나쁜 이동도 일정 확률로 받아들입니다. 따라서 언덕오르기 방식이라면 벗어나기 어려운 지역최소치를 넘어 전역최소치가 있는 영역으로 이동할 가능성이 생깁니다.

알고리즘의 처리 과정

1. 문제의 초기상태를 현재상태로 정합니다.
2. 시간 t에 따라 서서히 감소하는 온도 T=temperature(t)를 계산합니다.
3. T가 0이면 현재상태를 반환하고 탐색을 끝냅니다.
4. 현재상태의 후계노드 가운데 하나를 임의로 차기상태로 선택합니다.
5. 평가값 변화 ΔE=h(차기상태)-h(현재상태)를 계산합니다.
6. ΔE<0이면 평가값이 개선되었으므로 차기상태를 수용합니다.
7. ΔE≥0이면 확률 e^-ΔE/T에 따라 차기상태를 수용합니다.

온도와 수용확률의 관계

ΔE가 양수일 때 나빠진 정도가 클수록 e^-ΔE/T는 작아집니다. 같은 ΔE라면 온도 T가 높을 때 수용확률이 크고, T가 0에 가까워질수록 수용확률은 작아집니다. 따라서 탐색 초반에는 다양한 영역을 탐색하고, 후반에는 좋은 상태 주변에서 안정되는 효과가 나타납니다.

모의 담금질은 나쁜 이동을 무조건 허용하는 알고리즘이 아닙니다. 나빠진 정도와 현재 온도가 결정하는 확률에 따라 제한적으로 허용하며, 온도는 시간에 따라 감소합니다.

A* 알고리즘의 평가함수와 절차

전체 경로비용의 예측

노드 n을 거쳐 목표노드 G까지 가는 실제 전체 경로비용은 f(n)=g(n)+h(n)입니다. 탐색 중에는 h(n)을 알 수 없으므로 경험적 예측치 ĥ(n)을 사용하여 평가함수 f̂(n)을 다음과 같이 정의합니다.

A* 평가함수: f̂(n)=g(n)+ĥ(n). 지금까지 실제로 든 비용과 앞으로 들 것으로 예측한 비용을 함께 평가합니다.

언덕오르기 탐색이 ĥ(n)만 사용하는 것과 달리 A*는 g(n)도 함께 고려합니다. 따라서 목표에 가까워 보이더라도 지금까지 지나치게 큰 비용을 사용한 경로는 낮게 평가할 수 있습니다.

OPEN과 CLOSED를 이용한 탐색

1. 출발노드 S의 f̂(S)를 계산하여 OPEN에 넣습니다.
2. OPEN에 노드가 남아 있는 동안 f̂가 최소인 노드 n을 꺼내 CLOSED에 넣습니다.
3. n이 목표노드이면 탐색에 성공합니다.
4. n을 확장해 후계노드를 생성하고 각 후계노드의 f̂를 계산합니다.
5. 중복 생성된 노드를 처리한 뒤 유효한 후계노드를 OPEN에 넣습니다.
6. OPEN이 비었는데 목표를 찾지 못하면 탐색에 실패합니다.

OPEN은 앞으로 확장할 후보를 보관하고, CLOSED는 이미 선택되어 확장된 노드를 관리합니다. 매 단계에서 전체 예상비용이 가장 작은 후보를 확장함으로써 유망한 경로를 우선 조사합니다.

A*의 중복 노드 처리와 최적성

동일 상태가 OPEN에 있는 경우

새로 생성된 n_new와 동일한 상태를 나타내는 n_old가 OPEN에 있으면 두 노드 모두 아직 확장되지 않은 상태입니다. 동일한 상태에서는 목표까지의 예측비용 ĥ가 같으므로 f̂가 큰 노드를 제거하고 더 저렴한 경로만 남기면 됩니다.

동일 상태가 CLOSED에 있는 경우

비교 결과	처리	이유
f̂(nold)≤f̂(nnew)	nnew를 제거	기존에 확장한 경로가 새 경로보다 좋거나 같음
f̂(nold)>f̂(nnew)	nnew를 제거하되 nold의 부모 포인터를 새 경로의 부모로 수정	더 저렴한 새 경로를 기존 상태에 반영해야 함

두 번째 경우에는 부모 포인터만 바꾸고 끝내면 안 됩니다. n_old까지의 경로비용이 달라졌으므로 n_old와 그 후계노드들의 평가함수 값도 갱신해야 합니다. 그래야 더 저렴한 경로가 이미 확장된 부분 전체에 반영됩니다.

최소비용 경로를 보장하는 조건

어느 노드에서도 예측비용 ĥ(n)이 실제 남은 비용 h(n)보다 크지 않다면, 즉 항상 ĥ(n)≤h(n)이 성립한다면 A*는 최소비용 경로의 탐색을 보장합니다. 이러한 예측은 실제비용을 과대평가하지 않는다는 뜻입니다.

강의의 도식에서 최소경로 위 노드 n₁과 다른 경로의 노드 n₂를 비교하면, 과대평가하지 않는 ĥ를 사용했을 때 최소경로 쪽의 평가값이 실제로 더 비싼 다른 경로의 비용보다 앞서도록 유지됩니다. 이 관계가 A*의 최적성 보장의 핵심입니다.

시험 핵심: ĥ(n)≤h(n)은 ‘예측이 정확해야 한다’는 뜻이 아니라 ‘실제 남은 비용보다 크게 예측하지 않아야 한다’는 조건입니다.

A* 적용 예제

8-퍼즐에서의 평가값

A* 8-퍼즐 예제에서 g(n)은 초기상태부터 해당 상태까지 빈칸이 이동한 횟수이고, ĥ(n)은 목표상태와 비교했을 때 지정된 위치에 있지 않은 조각의 수입니다. 각 노드에는 f̂(n)=g(n)+ĥ(n)을 계산하여 표시하고, OPEN에 있는 상태 가운데 그 합이 가장 작은 상태를 순서대로 확장합니다.

초기상태에서는 g=0, ĥ=4이므로 f̂=4입니다. 첫 이동 뒤 후보들의 평가값은 1+5=6, 1+3=4, 1+5=6이므로 가운데 후보가 먼저 선택됩니다. 이후에도 같은 원칙으로 확장하여 강의 도식의 일곱 번째 확장에서 g=5, ĥ=0, f̂=5인 목표상태에 도달합니다.

도시 경로 탐색

도시 a부터 g까지의 도로망에서 g(n)은 출발지 a부터 현재 도시까지의 누적 도로거리이고, ĥ(n)은 각 도시에서 목적지 g까지의 직선거리입니다. 출발지 a의 평가값은 9입니다. a의 후계도시 b와 c는 각각 6+6.5=12.5, 4+7=11이므로 c가 먼저 확장됩니다.

c에서 생성되는 후보 중 d는 7+4=11, e는 12+2.5=14.5입니다. 기존 b에 이르는 새 경로는 9+6.5=15.5로 기존 경로보다 나쁘므로 제거합니다. 이어 d, f, g의 순서로 확장되며 f의 평가값은 10+1=11, 목표 g의 비용은 12입니다.

예제 결론: 탐색된 최소비용 경로는 a-c-d-f-g이고 실제 비용은 4+3+3+2=12입니다.

핵심 개념 정리

• 경험적 탐색: 경험적 규칙을 평가함수에 반영하여 목표상태를 더 효과적으로 찾습니다.
• 비용 구분: g(n)은 출발점부터 현재까지의 실제비용, h(n)은 목표까지의 실제비용, ĥ(n)은 그 남은 비용의 예측치입니다.
• 언덕오르기 탐색: 후계노드 중 ĥ가 최소인 노드를 선택하며 g는 고려하지 않습니다. 지역최대치·고원·능선 문제에 취약합니다.
• 모의 담금질: 개선 이동은 수용하고, 나쁜 이동도 e^-ΔE/T의 확률로 수용합니다. 온도는 시간에 따라 감소합니다.
• A*: f̂(n)=g(n)+ĥ(n)이 최소인 노드를 OPEN에서 선택해 확장합니다.
• 중복 노드: 더 비싼 경로를 제거하되 CLOSED의 기존 노드보다 새 경로가 저렴하면 부모 포인터와 후계노드 평가값을 갱신합니다.
• 최적성: 모든 노드에서 ĥ(n)≤h(n)이면 A*가 최소비용 경로를 탐색하는 것이 보장됩니다.

세 탐색 방법의 차이는 비용을 어떻게 보고 다음 상태를 선택하는지에 있습니다. 언덕오르기는 남은 비용의 예측만 보고 국소적으로 전진하고, 모의 담금질은 확률적 후퇴로 지역최적점을 벗어나려 하며, A*는 누적 실제비용과 남은 예측비용을 함께 사용하여 조건을 만족할 때 최소비용 경로를 보장합니다.

예상문제 20선

1. 경험적 탐색에 대한 설명으로 가장 적절한 것은?

① 모든 상태를 같은 순서로 조사하는 탐색이다. ② 경험적 규칙을 이용하여 목표상태를 더 신속하게 찾으려는 탐색이다. ③ 평가함수를 사용하지 않는 무정보 탐색이다. ④ 항상 최적해를 보장하는 규칙만 사용하는 탐색이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
경험적 탐색은 경험적 규칙을 평가함수에 반영하여 목표상태를 더 효과적으로 탐색한다. 경험적 규칙은 대부분의 경우 잘 맞지만 항상 옳다고 보장되는 규칙은 아니다.

2. 평가함수의 구성요소에 관한 설명으로 옳은 것은?

① g(n)은 n에서 목표노드까지의 실제 비용이다. ② h(n)은 출발노드에서 n까지의 누적비용이다. ③ ĥ(n)은 출발노드에서 n까지의 비용 예측치이다. ④ g(n)은 출발노드에서 n까지의 경로비용이고 ĥ(n)은 n에서 목표노드까지의 예측비용이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
g(n)은 이미 지나온 경로의 실제 비용이며, ĥ(n)은 현재 노드에서 목표까지 앞으로 필요할 비용을 경험적 지식으로 예측한 값이다.

3. 언덕오르기 탐색이 다음 확장 노드를 선택하는 기준은?

① 현재 노드의 후계노드 중 ĥ(n)이 최소인 노드를 선택한다. ② OPEN에서 g(n)이 가장 큰 노드를 선택한다. ③ 후계노드 중 가장 먼저 생성된 노드를 무조건 선택한다. ④ g(n)+ĥ(n)이 최대인 노드를 선택한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
언덕오르기 탐색은 현재 상태의 후계노드 가운데 목표까지의 예측비용 ĥ(n)이 최소인 노드를 고른다. 출발점에서 후계노드까지 든 g(n)은 고려하지 않는다.

4. 강의의 언덕오르기 8-퍼즐 예제에서 한 상태의 비용으로 사용한 것은?

① 모든 조각 번호의 합 ② 빈칸이 움직일 수 있는 방향의 수 ③ 목표상태와 비교하여 지정된 위치에 없는 조각의 수 ④ 출발상태부터 누적된 빈칸 이동 횟수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
언덕오르기 예제의 평가값은 목표 위치에 있지 않은 조각의 수이다. 제시된 초기상태의 비용은 4이다.

5. 언덕오르기 탐색에서 g(n)을 고려하지 않는다는 말의 의미로 옳은 것은?

① 목표까지 남은 비용도 고려하지 않는다. ② 출발노드에서 현재 후계노드까지 이미 사용한 경로비용은 선택 기준에서 제외한다. ③ 평가함수 자체를 계산하지 않는다. ④ 모든 후계노드의 비용을 같다고 본다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
언덕오르기 탐색의 선택 기준은 ĥ(n)이다. 따라서 현재 위치까지 누적된 경로비용 g(n)은 다음 노드의 선택에 반영하지 않는다.

6. 등산 문제를 계수최적화 문제로 표현할 때 목표상태로 옳은 것은?

① 출발점과 같은 고도의 상태 ② 동쪽 후계상태만 더 높은 상태 ③ 무조건 가장 먼저 방문한 상태 ④ 모든 후계상태의 고도가 현재상태보다 낮은 상태

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
강의에서는 등산가의 좌표와 고도를 상태로, 동·서·남·북 이동을 연산자로 두고 모든 후계상태의 고도가 현재보다 낮은 곳을 목표상태로 표현한다.

7. 최급상승법의 난제가 아닌 것은?

① 지역최대치 문제 ② 고원문제 ③ 중복노드가 OPEN에 존재하는 문제 ④ 능선문제

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
최급상승법의 대표적 난제는 지역최대치, 고원, 능선 문제이다. OPEN의 중복노드 처리는 A* 알고리즘에서 다루는 문제이다.

8. 지역최대치 문제에 대한 설명으로 가장 적절한 것은?

① 현재 위치 주변에서는 더 높은 상태가 없어 멈추지만 전역최대치는 다른 곳에 있는 경우이다. ② 모든 방향의 평가값이 완전히 같은 평탄면만 존재하는 경우이다. ③ 목표까지의 경로가 직선으로만 이어진 경우이다. ④ 항상 전역최대치에 도달한 경우이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
지역최대치에서는 인접한 후계상태가 모두 낮아 탐색이 종료되지만, 상태공간의 다른 곳에 더 높은 전역최대치가 존재할 수 있다.

9. 모의 담금질을 사용하는 주된 이유는?

① 평가함수를 제거하기 위해 ② 후계상태를 항상 같은 순서로 선택하기 위해 ③ 현재보다 나쁜 상태를 절대로 선택하지 않기 위해 ④ 일정 확률로 나쁜 상태도 수용하여 지역최적점에서 벗어날 가능성을 만들기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
모의 담금질은 평가값이 개선되지 않는 이동도 온도에 따른 확률로 허용한다. 이 확률적 이동이 지역최소치에 갇히는 문제를 완화한다.

10. 최소화 문제의 모의 담금질에서 ΔE=h(차기상태)-h(현재상태)<0일 때의 처리는?

① 탐색을 즉시 실패로 종료한다. ② 차기상태를 현재상태로 받아들인다. ③ 확률 e^-ΔE/T로만 받아들인다. ④ 차기상태를 반드시 폐기한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
ΔE가 음수이면 차기상태의 평가값이 더 작아진 개선 이동이므로 확률 계산 없이 차기상태를 수용한다.

11. 모의 담금질에서 ΔE≥0인 차기상태를 받아들이는 확률은?

① e^-ΔE/T ② g(n)+ĥ(n) ③ ΔE×T ④ 1-ĥ(n)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
평가값이 개선되지 않을 때의 수용확률은 e^-ΔE/T이다. ΔE가 클수록 낮아지고 같은 ΔE에서는 온도가 높을수록 커진다.

12. 모의 담금질에서 온도 T가 시간에 따라 0에 가까워질 때 나타나는 변화는?

① 나쁜 이동의 수용확률이 커진다. ② 평가함수 계산을 중단하고 무조건 이동한다. ③ 나쁜 이동의 수용확률이 작아져 탐색이 점차 안정된다. ④ 모든 후계노드를 동시에 확장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
온도가 낮아질수록 e^-ΔE/T가 작아져 나쁜 이동을 수용하기 어려워진다. T가 0이면 현재상태를 반환한다.

13. A* 알고리즘의 평가함수 f̂(n)으로 옳은 것은?

① ĥ(n)-g(n) ② g(n)×ĥ(n) ③ g(n)만 사용 ④ g(n)+ĥ(n)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
A*는 출발노드에서 n까지 실제로 든 비용 g(n)과 n에서 목표까지의 예측비용 ĥ(n)을 더한 f̂(n)을 사용한다.

14. A* 알고리즘에서 OPEN과 CLOSED의 역할에 대한 설명으로 옳은 것은?

① OPEN에는 확장할 후보가 있고, 선택되어 확장되는 노드는 CLOSED로 옮긴다. ② OPEN에는 목표노드만 저장하고 CLOSED는 사용하지 않는다. ③ CLOSED에는 아직 생성되지 않은 노드를 저장한다. ④ 두 목록은 평가값과 관계없이 무작위로 교환한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
A*는 OPEN에서 f̂가 최소인 노드를 꺼내 CLOSED에 넣고 목표 여부를 확인한 뒤 확장한다. OPEN은 앞으로 고려할 후보를 관리한다.

15. 동일 상태의 두 노드가 모두 OPEN에 있을 때 A*의 처리로 옳은 것은?

① 두 노드를 모두 즉시 확장한다. ② 평가함수 f̂가 큰 노드를 제거한다. ③ g(n)이 큰 노드를 반드시 남긴다. ④ 먼저 생성된 노드는 평가값과 무관하게 남긴다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
동일 상태라면 목표까지의 예측값은 같고 아직 어느 쪽도 확장되지 않았다. 따라서 전체 예측비용 f̂가 큰 경로의 노드를 제거한다.

16. 동일 상태 n_old가 CLOSED에 있고 f̂(n_old)≤f̂(n_new)일 때의 처리는?

① n_old의 모든 후계노드를 삭제한다. ② n_old를 OPEN으로 되돌린다. ③ 새로 생성된 n_new를 제거한다. ④ 두 노드의 부모 포인터를 서로 바꾼다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
이미 확장한 n_old의 경로가 새 경로보다 좋거나 같으므로 새로 생성된 n_new를 제거하면 된다.

17. 동일 상태 n_old가 CLOSED에 있고 f̂(n_old)>f̂(n_new)일 때 필요한 조치는?

① 새 경로를 무시하고 아무것도 하지 않는다. ② 목표노드를 제거한다. ③ n_old만 삭제하고 탐색을 종료한다. ④ n_old의 부모를 새 경로의 부모로 바꾸고 n_old와 후계노드들의 평가값을 갱신한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
새 경로가 더 저렴하므로 기존 상태의 부모 포인터를 새 경로 쪽으로 수정하고, 변경된 비용이 전파되도록 기존 노드와 그 후계노드의 평가함수를 갱신한다.

18. A*가 최소비용 경로를 보장하도록 하는 예측비용의 조건은?

① 모든 n에서 ĥ(n)≥h(n) ② 모든 n에서 ĥ(n)=0이어서는 안 됨 ③ 모든 n에서 ĥ(n)≤h(n) ④ 모든 n에서 g(n)≤ĥ(n)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
목표까지의 예측비용 ĥ(n)이 실제비용 h(n)을 넘지 않는 허용적 조건, 즉 ĥ(n)≤h(n)이 항상 성립하면 A*는 최소비용 경로를 보장한다.

19. 강의의 A* 8-퍼즐 예제에서 g(n)과 ĥ(n)의 연결로 옳은 것은?

① g(n)은 빈칸 이동 횟수이고 ĥ(n)은 제 위치에 없는 조각의 수이다. ② g(n)은 제 위치에 없는 조각의 수이고 ĥ(n)은 빈칸 이동 횟수이다. ③ 둘 다 퍼즐 조각 번호의 합이다. ④ 둘 다 목표까지의 실제 최단비용이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
A* 8-퍼즐 예제는 누적 빈칸 이동 횟수를 g(n), 목표상태와 비교해 지정 위치에 없는 조각 수를 ĥ(n)으로 사용한다.

20. 강의의 도시 경로 탐색 예제에서 A*가 찾은 a에서 g까지의 최소비용 경로는?

① a-b-e-g, 비용 15 ② a-c-d-f-g, 비용 12 ③ a-c-e-g, 비용 15 ④ a-b-d-f-g, 비용 18

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
평가함수가 작은 순서로 a, c, d, f, g가 확장되며 경로비용은 4+3+3+2=12이다. 따라서 최소비용 경로는 a-c-d-f-g이다.