방송대 인공지능 2강: 상태공간 탐색과 DFS·BFS·균일비용 탐색

방송대 인공지능 2강: 상태공간 탐색과 DFS·BFS·균일비용 탐색

같은 출발점과 목표를 주어도 깊이우선 탐색, 너비우선 탐색과 균일비용 탐색은 서로 다른 경로를 선택할 수 있다. 문제를 상태·연산자·비용으로 모델링한 뒤, OPEN의 변화와 경로비용을 직접 계산하여 세 탐색의 보장과 실패 조건을 구분한다.

대표 문제: 배송 로봇은 어느 경로를 택해야 할까

배송 로봇이 출발지 S에서 목적지 G로 이동한다고 하자. 이동 가능한 연결과 비용은 S-A=2, A-G=8, S-B=1, B-C=2, C-G=2다. 자식은 A를 B보다 먼저 생성한다고 가정한다. 가능한 두 경로는 S-A-G와 S-B-C-G다.

경로	간선 수	총비용	특징
S-A-G	2	2+8=10	단계는 짧지만 비용이 큼
S-B-C-G	3	1+2+2=5	단계는 길지만 비용이 작음

DFS는 먼저 생성된 A 방향을 깊게 따라 S-A-G를 찾을 수 있다. BFS는 가장 얕은 목표를 찾으므로 두 간선인 S-A-G를 선택한다. UCS는 누적비용을 비교해 세 간선이지만 비용이 5인 S-B-C-G를 선택한다. “최단”이라는 말이 최소 간선 수인지 최소비용인지 먼저 정해야 하는 이유다.

판단 핵심: 해 하나가 필요한가, 이동 단계가 가장 적어야 하는가, 비용의 합이 가장 작아야 하는가를 먼저 정한다. 목표 기준이 달라지면 올바른 탐색도 달라진다.

탐색 전에 문제를 계산 가능한 언어로 번역한다

문제풀이(problem solving)는 직관만으로 해결하기 어려운 문제를 파악하고 해에 이르는 방법을 찾는 과정이다. 컴퓨터는 막연한 시행착오나 통찰을 그대로 사용할 수 없으므로 현재 상황, 가능한 변화, 성공 조건을 명시적으로 표현해야 한다.

상태(state)는 문제의 한 장면이다. 처음 주어진 장면이 초기상태, 해결된 장면이 목표상태다. 상태를 컴퓨터가 처리할 자료구조로 표현한 것이 상태묘사(state description)이고, 한 상태를 다른 상태로 바꾸는 변환이 연산자(operator)다.

요소	배송 문제	8-퍼즐 문제
상태묘사	현재 위치를 나타내는 도시 기호	3×3 조각 배열과 빈칸 좌표
초기상태	S	처음 주어진 퍼즐 배열
목표상태	G	완성하려는 퍼즐 배열
연산자	연결된 다음 지점으로 이동	빈칸을 상·하·좌·우로 이동
비용	도로별 거리·시간·요금	조각 또는 빈칸의 이동 횟수

이 다섯 요소가 정해지지 않으면 알고리즘을 실행해도 동일 상태를 비교할 수 없고, 불법 이동을 걸러 내지 못하며, 무엇을 해로 인정할지도 불분명하다. 알고리즘 선택보다 문제 표현이 먼저다.

좋은 상태묘사는 자연스러움과 처리 효율을 함께 갖춘다

상태묘사는 기호열, 벡터, 다차원 배열, 트리와 리스트 등으로 만들 수 있다. 문제 상황을 이해하기 쉬운 표현이어야 하면서 한 상태에서 다른 상태로 변환하는 연산도 효율적이어야 한다. 8-퍼즐의 판을 3×3 배열에 저장하면 배치를 자연스럽게 볼 수 있지만, 이동할 때마다 빈칸을 찾기 위해 배열 전체를 훑어야 할 수 있다.

배열과 함께 빈칸의 x·y 좌표를 저장하면 이동 가능 조건을 빠르게 검사할 수 있다. 예를 들어 ‘빈칸 위로 이동’은 빈칸이 맨 윗줄이 아닐 때만 실행하며, 바로 위의 조각을 현재 빈칸으로 옮긴 뒤 빈칸 좌표를 한 칸 위로 갱신한다. 조건 검사, 배열 변경과 좌표 갱신이 한 연산 안에서 일관되어야 한다.

잘못된 구현: 배열의 조각만 바꾸고 빈칸 좌표를 갱신하지 않는다. 다음 연산은 오래된 좌표를 사용해 실제 판과 다른 상태를 만든다. 검산: 연산 후 배열 안에 빈칸이 정확히 하나인지, 저장 좌표가 그 위치를 가리키는지 확인한다.

연산자는 표로 저장하거나 일반 규칙으로 계산한다

연산자를 정의하는 첫 방법은 모든 입력 상태마다 가능한 출력 상태를 변환표에 저장하는 것이다. 상태 수가 작으면 단순하지만 상태공간이 커질수록 목록이 급격히 늘어난다. 두 번째 방법은 적용 조건과 변환을 일반화한 함수로 정의하는 것이다. 8-퍼즐의 네 방향 이동은 이 방식이 적합하다.

연산자를 한 상태에 적용해 생긴 상태를 후계상태라고 한다. 상태를 노드, 연산자 적용을 방향성 간선으로 나타내면 부모상태와 후계상태의 관계가 그래프가 된다. 정의된 연산자 집합으로 초기상태에서 도달할 수 있는 모든 상태의 집합이 상태공간(state space)이다.

범위 판정: 모양상 가능한 상태라고 모두 상태공간에 들어가는 것은 아니다. 현재 정의된 연산자를 반복해 초기상태에서 실제로 도달할 수 있어야 한다.

상태공간 탐색과 문제축소는 해를 조직하는 방식이 다르다

상태공간 탐색은 초기상태에서 목표상태까지 이어지는 연산자 순서를 찾는다. 그래프 관점에서는 시작 노드에서 목표 노드로 가는 경로 탐색이다. 8-퍼즐에서는 빈칸 이동의 연속, 배송 문제에서는 지점 이동의 연속이 풀이가 된다.

문제축소(problem reduction)는 큰 문제를 부분문제로 나눈다. 하노이 탑에서 큰 원판을 1번 기둥에서 3번 기둥으로 옮기려면 ① 위의 작은 원판들을 2번으로 옮기고, ② 큰 원판을 3번으로 옮기며, ③ 작은 원판들을 2번에서 3번으로 옮긴다. 각 부분문제는 다시 같은 구조로 축소된다.

상태공간 탐색은 “다음 상태는 무엇인가?”를, 문제축소는 “먼저 해결할 하위 목표는 무엇인가?”를 묻는다. 하노이 탑도 상태공간으로 표현할 수 있지만, 강의의 문제축소 관점은 재귀적인 하위 문제 관계를 드러내는 데 초점이 있다.

OPEN·CLOSED·부모 포인터가 탐색 기록을 만든다

탐색은 정해진 기준으로 노드 하나를 선택하고, 적용 가능한 모든 연산자로 후계노드를 생성하는 확장을 반복한다. OPEN은 앞으로 확장할 후보를 저장하고, CLOSED는 이미 확장한 노드를 저장한다. 선택된 노드는 OPEN에서 제거되어 CLOSED로 이동하며 새 후계노드는 탐색 정책에 맞는 OPEN 위치에 들어간다.

각 후계노드에는 부모노드를 가리키는 포인터를 붙인다. 목표를 발견한 뒤 목표에서 부모를 거꾸로 따라가면 출발점까지의 풀이 경로를 복원할 수 있다. 부모 포인터는 어느 노드를 먼저 확장할지 정하지 않으며, 성공한 경로를 재구성하는 기록이다.

1. 출발노드를 OPEN에 넣는다.
2. 정책에 따라 OPEN의 다음 노드를 선택해 CLOSED로 옮긴다.
3. 적용 가능한 연산자로 후계노드를 만들고 부모 포인터를 붙인다.
4. 목표를 검사하고, 아니면 새 노드를 OPEN의 알맞은 위치에 넣는다.
5. 목표를 찾거나 OPEN이 빌 때까지 반복한다.

DFS 풀이: 한 갈래를 먼저 끝까지 계산한다

깊이우선 탐색(depth-first search, DFS)은 가장 최근에 생성된 노드를 먼저 확장한다. 후계노드를 OPEN의 앞에 넣기 때문에 OPEN은 후입선출 스택처럼 동작한다. 대표 배송 문제에서 A를 B보다 먼저 생성하고 그 순서대로 깊게 탐색하면 S-A-G를 먼저 찾아 비용 10의 경로에서 멈출 수 있다.

DFS의 목표는 일반적으로 최소비용이나 최소 단계 보장이 아니라 한 경로를 깊게 시도해 해를 찾는 것이다. 목표가 없는 깊은 갈래나 순환에 빠질 수 있어 깊이제한(depth bound)을 둘 수 있다. 제한에 도달하거나 더 진행할 수 없으면 이전 분기점으로 되돌아가 다른 경로를 선택한다.

깊이제한의 양면: 끝없는 전진을 막지만 실제 해가 제한보다 깊다면 존재하는 해를 놓친다. “제한을 두면 항상 올바른 해를 찾는다”가 아니라 “탐색 범위와 실패 조건이 달라진다”고 이해해야 한다.

BFS 풀이: 레벨을 비교해 최소 단계를 찾는다

너비우선 탐색(breadth-first search, BFS)은 먼저 생성된 노드를 먼저 확장한다. 후계노드를 OPEN의 뒤에 넣으므로 OPEN은 선입선출 큐처럼 동작하고, 깊이 0, 깊이 1, 깊이 2의 순서로 레벨을 소진한다.

대표 배송 문제에서 깊이 1의 A와 B를 처리한 뒤 깊이 2의 목표 G를 발견하므로 S-A-G를 반환한다. 해가 존재하면 간선 수가 가장 적은 경로를 보장한다. 그러나 이 경로의 비용은 10이고, 세 간선을 거치는 S-B-C-G의 비용은 5다. 간선 비용이 모두 같을 때만 최소 단계와 최소비용이 일치한다.

용어 검산: BFS의 ‘최단길이’는 기본적으로 최소 간선 수다. 도로 거리·시간·요금처럼 간선마다 값이 다르면 총비용 최적화는 UCS가 담당한다.

UCS 풀이: OPEN을 누적비용 순으로 다시 정렬한다

균일비용 탐색(uniform-cost search, UCS)은 출발점에서 노드 n까지의 누적 경로비용 g(n)이 가장 작은 노드를 먼저 확장한다. n에서 후계노드 n_i로 이동하는 비용을 C(n,n_i)라 하면 다음 식으로 새 비용을 계산한다.

g(n_i) = g(n) + C(n,n_i)

대표 배송 문제의 OPEN 변화를 계산하면 비용이 더 큰 목표 후보가 나중에 교체되는 이유가 보인다.

확장	확장 뒤 OPEN	계산과 처리
S(0)	B(1), A(2)	비용 오름차순으로 B를 먼저 배치
B(1)	A(2), C(3)	g(C)=1+2=3
A(2)	C(3), G(10)	목표가 생성되어도 최소 후보는 C
C(3)	G(5)	g(G)=3+2=5이므로 기존 G(10)을 교체
G(5)	-	S-B-C-G를 최소비용 경로로 확정

목표를 생성한 순간 종료하면 비용 10을 잘못 확정한다. 비음수 비용의 UCS에서는 목표가 OPEN의 최소비용 노드로 선택되는 시점에 경로를 확정한다. 현재 간선 하나가 아니라 출발점부터의 누적비용을 비교해야 한다.

중복 상태는 더 싼 도달 경로만 남긴다

같은 상태가 OPEN에 이미 있는데 새 경로로 다시 생성되었다면 두 g값을 비교한다. 새 경로가 더 싸면 기존 항목을 새 항목으로 대체하고, 더 비싸거나 같으면 새 항목을 버린다. 같은 상태에서 앞으로 가능한 연산은 같으므로 비싼 도달 경로를 유지할 이유가 없다.

예를 들어 S-A-X의 비용이 2+7=9여서 X(9)가 OPEN에 먼저 들어갔다고 하자. 뒤이어 S-B-C-X의 비용이 1+2+1=4로 계산되면 X라는 이름이 같다는 이유로 새 항목을 버려서는 안 된다. 기존 X(9)를 X(4)로 바꾸고 부모도 A에서 C로 갱신해야 최종 경로가 S-B-C-X로 복원된다. 반대로 뒤늦게 발견한 경로의 비용이 11이라면 X(9)를 유지한다. 이처럼 중복 검사는 단순 삭제가 아니라 상태 비교 → 누적비용 비교 → 항목과 부모 포인터 동시 갱신의 세 단계 계산이다.

강의의 UCS 알고리즘에서는 동일 상태가 CLOSED에 있다면 새 항목을 제거한다. 비음수 경로비용에서 최소 g 노드를 먼저 확장했으므로 이미 CLOSED에 들어간 상태보다 더 싼 경로가 나중에 생길 수 없다는 전제가 있기 때문이다. 마지막으로 OPEN을 g의 오름차순으로 정렬한다.

오답 원인: 노드 이름만 보고 중복을 없애면서 비용과 부모 포인터를 비교하지 않으면 더 비싼 경로가 남을 수 있다. 중복 제거는 상태 동일성, g값과 경로 복원 정보를 함께 처리해야 한다.

강의의 도시 그래프로 최소비용을 재검산한다

강의의 a부터 g까지 도시 그래프에서 UCS는 누적비용 순으로 a, c, b, d, f, g를 확장한다. 선택된 경로는 a-c-d-f-g이며 비용은 4+3+3+2=12다.

비교 경로 a-b-e-g는 6+6+3=15이고 a-c-e-g는 4+8+3=15다. a-b-d-f-g도 6+7+3+2=18이다. 간선 수만 보면 a-b-e-g가 세 간선으로 짧지만 네 간선인 a-c-d-f-g의 총비용이 더 낮다.

경로	비용 계산	판정
a-c-d-f-g	4+3+3+2=12	최소비용
a-b-e-g	6+6+3=15	간선은 적지만 더 비쌈
a-c-e-g	4+8+3=15	c 이후 선택이 비쌈
a-b-d-f-g	6+7+3+2=18	누적비용이 가장 큼

맹목적 탐색과 경험적 탐색의 경계

맹목적 탐색(blind search)은 목표의 위치와 관련된 경험적 정보를 쓰지 않는다. DFS는 생성 시점, BFS는 깊이, UCS는 지금까지 실제로 든 비용으로 노드를 정하지만 “목표가 어느 방향에 가까운가”라는 추정은 사용하지 않는다.

경험적 탐색(heuristic search)은 항상 옳지는 않지만 많은 경우 목표에 가까울 가능성을 알려 주는 경험적 정보를 이용한다. 언덕오르기, 최적우선, 모의 담금질과 A*가 이 범주다. 임의 경로 탐색과 최적 경로 탐색이라는 목적 축, 경험 정보 사용 여부라는 정보 축을 분리해야 한다.

분류 핵심: UCS가 비용을 사용한다고 경험적 탐색이 되는 것은 아니다. g는 이미 이동한 실제비용이고, 목표까지 남은 거리를 추정한 휴리스틱이 아니다.

목적과 조건으로 탐색을 선택한다

조건	우선 선택	확인할 위험
해 하나가 필요하고 한 경로를 깊게 시도하려 함	DFS	순환, 무한 깊이, 깊이제한보다 깊은 해
모든 이동 비용이 같고 최소 이동 횟수가 중요함	BFS	넓은 레벨의 큰 메모리 사용
이동마다 비용이 다르고 총비용 최소가 중요함	UCS	누적비용 계산과 중복 경로 교체
목표 방향의 유용한 추정 정보를 사용할 수 있음	다음 차시의 경험적 탐색	추정값이 항상 정확하다고 가정하는 오류

자가 점검: “환승 횟수가 가장 적은 경로”와 “총요금이 가장 싼 경로”를 각각 어떤 탐색으로 모델링할지 설명해 보자. 환승을 간선 하나로 보고 모든 간선 비용을 같게 두면 BFS가 맞고, 요금을 간선 비용으로 두면 UCS가 맞다.

핵심 개념 정리

1. 표현: 상태묘사, 초기상태, 목표상태, 연산자와 필요하면 경로비용을 정의한다.
2. 기록: OPEN은 확장 후보, CLOSED는 확장 완료 노드, 부모 포인터는 풀이 경로를 관리한다.
3. 선택: DFS는 최근 생성, BFS는 얕은 깊이, UCS는 최소 누적비용을 우선한다.
4. 검산: 최소 간선 수와 최소비용을 구분하고 중복 상태에서는 더 싼 도달 경로를 남긴다.
5. 확장: 목표 방향의 추정치를 사용하면 맹목적 탐색에서 경험적 탐색으로 넘어간다.

문제풀이 순서는 “무엇이 상태인가 → 어떤 연산이 합법적인가 → 원하는 해는 임의 경로·최소 단계·최소비용 중 무엇인가 → OPEN을 어떤 순서로 운용할 것인가 → 중복 상태와 부모 포인터를 어떻게 관리할 것인가”다. 알고리즘 이름보다 문제의 목표와 OPEN의 우선순위를 연결해 설명할 수 있어야 한다.

예상문제 10선

1. 상태묘사에 대한 설명으로 가장 적절한 것은?

① 목표 방향을 추정하는 경험적 값만을 뜻한다. ② 문제의 한 상태를 컴퓨터가 처리할 자료구조로 표현한 것이다. ③ 탐색이 끝난 뒤 총비용만 기록한 값이다. ④ 모든 문제에서 반드시 2차원 배열만 사용한다.

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: 목표 방향의 추정값은 경험적 탐색의 휴리스틱이며 상태 자체의 표현과 다르다.
• ② 정답: 상태묘사는 배열·벡터·기호열처럼 현재 상황을 처리 가능한 구조로 바꾼 것이다.
• ③ 오답: 총비용은 경로 속성이며 상태묘사는 탐색 전부터 각 상황을 구별하는 데 필요하다.
• ④ 오답: 문제에 따라 기호열, 트리, 리스트 등 더 적합한 자료구조를 선택할 수 있다.

2. 상태공간의 정의로 옳은 것은?

① 목표상태 하나만의 집합 ② CLOSED에 저장된 노드만의 집합 ③ 정의된 연산자로 초기상태에서 도달할 수 있는 모든 상태의 집합 ④ 컴퓨터가 표현할 수 있는 모든 자료형의 집합

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 목표는 상태공간 안의 특정 상태이며 전체 집합보다 범위가 작다.
• ② 오답: CLOSED는 탐색 중 이미 확장한 일부 상태만 담는다.
• ③ 정답: 초기상태와 연산자 집합이 도달 가능한 상태의 범위를 결정한다.
• ④ 오답: 자료형 목록이 아니라 특정 문제에서 도달 가능한 상태들의 집합이다.

3. 하노이 탑을 문제축소 관점으로 설명한 것은?

① 큰 원판 이동 문제를 작은 원판 이동과 큰 원판 이동의 부분문제로 나눈다. ② 누적비용이 가장 큰 경로부터 확장한다. ③ 목표상태를 정의하지 않고 임의로 원판을 움직인다. ④ 모든 상태를 한 번에 변환표에 저장해야만 해결한다.

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 원문제를 같은 구조의 더 작은 이동 문제로 분해하는 것이 문제축소의 핵심이다.
• ② 오답: 비용 순서는 UCS의 노드 선택 기준이며 문제를 분할하는 설명이 아니다.
• ③ 오답: 부분문제도 명확한 시작과 목표를 가져야 올바른 순서로 결합할 수 있다.
• ④ 오답: 하노이 탑은 일반화된 재귀 규칙으로 표현할 수 있어 모든 변환을 저장할 필요가 없다.

4. DFS의 깊이제한에 대한 설명으로 옳은 것은?

① 최소비용 경로를 항상 보장한다. ② 모든 노드를 같은 레벨에서 확장한다. ③ 끝없는 깊이 전진을 막지만 제한보다 깊은 해를 놓칠 수 있다. ④ 간선 비용을 모두 같은 값으로 바꾼다.

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: DFS는 기본적으로 비용 최적화를 목표로 하지 않는다.
• ② 오답: 같은 레벨을 먼저 처리하는 방식은 BFS다.
• ③ 정답: 제한은 무한 경로 위험을 줄이는 대신 더 깊은 해를 탐색 대상에서 제외한다.
• ④ 오답: 깊이제한은 탐색 깊이를 제어하며 문제의 간선 비용을 변경하지 않는다.

5. 대표 배송 문제에서 BFS가 선택하는 경로와 비용은?

① S-B-C-G, 비용 5 ② S-A-G, 비용 10 ③ S-A-G, 비용 5 ④ S-B-C-G, 비용 10

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: S-B-C-G는 비용은 작지만 간선이 3개라 BFS의 최소 단계 선택이 아니다.
• ② 정답: S-A-G는 두 간선으로 가장 얕고 비용은 2+8=10이다.
• ③ 오답: 경로는 맞지만 비용 계산에서 A-G의 비용 8을 3으로 잘못 처리했다.
• ④ 오답: S-B-C-G의 실제 비용은 1+2+2=5이고 BFS가 우선하는 경로도 아니다.

6. UCS에서 목표노드를 생성한 즉시 종료하면 안 되는 이유는?

① 목표노드는 부모 포인터를 가질 수 없기 때문이다. ② UCS는 목표상태를 사용하지 않기 때문이다. ③ 생성된 목표 경로의 간선 수가 최소인지 먼저 확인해야 하기 때문이다. ④ OPEN의 다른 경로가 같은 목표에 더 낮은 비용으로 도달할 수 있기 때문이다.

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 목표에도 부모 포인터를 붙여 실제 풀이 경로를 복원할 수 있다.
• ② 오답: UCS도 목표상태를 명시하고 선택된 노드가 목표인지 검사한다.
• ③ 오답: UCS의 확정 기준은 간선 수가 아니라 누적비용이다. 간선 수가 더 적어도 총비용은 더 클 수 있다.
• ④ 정답: 생성 시점의 목표보다 싼 후보가 OPEN에 남아 있을 수 있어 최소로 선택될 때 확정한다.

7. 대표 배송 문제에서 UCS가 확정하는 최소비용 경로는?

① S-A-G, 비용 5 ② S-B-C-G, 비용 5 ③ S-A-G, 비용 10이지만 최소비용 ④ S-B-C-G, 비용 10

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: S-A-G의 실제 비용은 2+8=10이다.
• ② 정답: S-B-C-G는 1+2+2=5로 다른 후보보다 총비용이 작다.
• ③ 오답: S-A-G는 간선 수는 적지만 비용 5인 대안이 있어 최소비용이 아니다.
• ④ 오답: 경로는 맞지만 간선 비용의 합을 5가 아닌 10으로 잘못 계산했다.

8. UCS가 맹목적 탐색으로 분류되는 이유는?

① 비용을 전혀 사용하지 않기 때문이다. ② OPEN과 CLOSED를 사용하지 않기 때문이다. ③ 임의의 노드만 무작위로 고르기 때문이다. ④ 목표 위치를 추정하는 경험적 정보가 아니라 이미 든 실제비용 g만 사용하기 때문이다.

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: UCS는 누적 경로비용을 핵심 선택 기준으로 사용한다.
• ② 오답: UCS도 OPEN과 CLOSED로 후보와 확장 완료 노드를 관리한다.
• ③ 오답: UCS는 무작위가 아니라 g의 오름차순으로 확장한다.
• ④ 정답: 실제로 지불한 비용은 알지만 목표까지 남은 방향의 휴리스틱은 사용하지 않는다.

9. ‘환승 횟수 최소’와 ‘총요금 최소’를 각각 모델링한 것으로 옳은 것은?

① 둘 다 반드시 DFS만 사용한다. ② 환승 횟수는 UCS, 총요금은 BFS만 사용한다. ③ 환승 횟수는 BFS, 총요금은 간선 비용을 둔 UCS로 탐색한다. ④ 둘 다 목표상태 없이 탐색한다.

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: DFS는 환승 횟수나 요금의 최적값을 기본적으로 보장하지 않는다.
• ② 오답: 최소 간선 수와 최소비용에 적합한 탐색을 서로 뒤바꾸었다.
• ③ 정답: 환승은 단계 수로, 요금은 간선별 실제 비용의 합으로 모델링한다.
• ④ 오답: 어느 목적이든 도착 지점을 목표상태로 정의해야 성공 여부를 판정한다.

10. 탐색 문제를 푸는 순서로 가장 적절한 것은?

① 상태·연산자 정의 → 해의 기준 결정 → OPEN 정책 선택 → 중복과 경로 복원 검증 ② 알고리즘 이름 선택 → 목표상태 생략 → 비용을 나중에 임의 변경 ③ 첫 목표 생성 즉시 확정 → 더 싼 경로 비교 생략 ④ 부모 포인터 삭제 → CLOSED만으로 경로를 추측

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 문제 표현과 최적화 목표를 먼저 정한 뒤 탐색 정책과 기록 구조를 선택해야 한다.
• ② 오답: 목표와 비용이 없으면 알고리즘이 무엇을 성공·최적으로 볼지 정할 수 없다.
• ③ 오답: UCS에서는 먼저 생성된 목표보다 더 싼 경로가 OPEN에 남아 있을 수 있다.
• ④ 오답: 부모 포인터가 없으면 목표에서 출발점까지의 구체적 풀이 경로를 복원하기 어렵다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 상태공간 모델링, 경로 계산, 오류 분석과 선택지별 문제 해설은 학습자의 이해를 돕도록 새로 구성하고 검토했습니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 컴퓨터과학과, 「인공지능」 2강 ‘문제풀이(1)’ 강의자료(2025년 제작 자료)
• 보충 자료: 별도의 외부 자료를 본문 근거로 사용하지 않았습니다.
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-08-17