P1-7.1 탐색 공간(search space)과 계산 한계(computational limit)¶

Section ID: P1-7.1 Version: v2026.07.20

6장에서는 불완전한 정보와 확률적 판단을 다뤘습니다. 이제 다른 종류의 어려움을 봅니다. 어떤 문제는 정보가 부족해서 어렵기도 하지만, 가능한 선택지가 너무 많아서 어렵기도 합니다.

여기서 던지는 질문은 다음입니다.

가능한 해가 너무 많을 때, AI는 무엇을 모두 살펴볼 수 없게 되는가?

휴리스틱(heuristic)을 이해하려면 먼저 탐색(search)과 탐색 공간(search space)을 이해해야 합니다.

Part 1에서 탐색(search), 탐색 공간(search space), 계산 한계(computational limit), 완전 탐색(exhaustive search)의 기본 구분은 이 절에서 잡습니다. 6장에서는 불확실성과 확률의 문제를 먼저 봤고, 여기서는 그와 다른 종류의 어려움인 후보가 너무 많아 전부 볼 수 없는 문제를 중심으로 잡습니다. 휴리스틱(heuristic)의 구체 역할은 바로 다음 7.2에서 더 자세히 다룹니다.

6장과 7장의 차이는 같은 서비스 안에서도 한 장면으로 나란히 볼 수 있습니다.

이 표의 핵심은 모르는 것이 많아서 어려운 문제와 후보가 너무 많아서 어려운 문제를 분리하는 데 있습니다. 현실에서는 둘이 함께 나타날 수 있지만, 6장은 먼저 무엇이 참인지 확실하지 않은 문제를 다루고, 7장은 가능한 선택지를 전부 보기 어려운 문제를 다룹니다.

후보가 많아지는 순간, 문제는 정답을 아는 일이 아니라 정답을 찾아가는 일이 된다.

이 문장은 정답의 정의와 정답을 찾는 절차를 구분하는 기준입니다. 어떤 문제는 답이 맞는지 확인하기는 쉬워도, 그 답에 도달하는 경로를 찾는 일이 훨씬 더 어려울 수 있습니다.

7.1은 탐색 알고리즘을 계산하지 않습니다. 너비 우선 탐색(breadth-first search), 깊이 우선 탐색(depth-first search), A 탐색(A search)은 여기서 구현하지 않습니다.

또한 휴리스틱 함수(heuristic function)를 본격적으로 설명하지 않습니다. 휴리스틱은 7.2에서 다룹니다.

여기서는 다음 관점만 잡습니다.

문제를 풀 때 가능한 상태와 선택지가 너무 많아지면 모든 경우를 살펴보는 방식은 곧 한계에 부딪힌다.

탐색 공간이 계산 한계를 만드는 기준¶

• 탐색(search)을 “가능한 후보를 살펴보며 해를 찾는 과정”으로 이해합니다.
• 상태(state), 행동(action), 목표(goal), 경로(path), 비용(cost)을 입문 수준에서 구분합니다.
• 탐색 공간(search space)이 커질 때 계산 한계(computational limit)가 왜 생기는지 이해합니다.
• 가능한 모든 경우를 살펴보는 완전 탐색(exhaustive search)이 왜 현실적으로 어려워지는지 설명할 수 있습니다.
• 7.2의 휴리스틱(heuristic)이 왜 필요한지 준비합니다.

세 가지 기준¶

여기서는 탐색 알고리즘 구현을 배우기보다, 왜 “찾는 문제”가 어려워지는지 이해하는 데 목적을 둡니다. 아래 세 가지를 먼저 가릅니다.

탐색, 탐색 공간, 상태, 행동, 경로, 비용, 계산 한계는 초반에 비슷한 구조 설명처럼 들릴 수 있습니다. 아래처럼 자리만 짧게 구분해 둡니다.

여기서는 탐색은 찾는 과정, 탐색 공간은 후보 전체, 상태와 행동은 그 안의 단위, 계산 한계는 전부 못 보는 이유라는 자리 구분을 유지합니다.

탐색(search)은 후보를 살펴보는 문제 해결 방식이다¶

Poole과 Mackworth는 에이전트가 목표를 달성하는 방법을 찾는 문제를 그래프(graph)에서 시작 노드(start node)에서 목표 노드(goal node)까지의 경로(path)를 찾는 문제로 추상화할 수 있다고 설명합니다. AIMA도 문제 해결(problem solving)과 탐색(search)을 AI 개론의 초반 핵심 주제로 배치합니다.

Poole과 Mackworth는 이 흐름을 짧게 이렇게 표현합니다.

“Search underlies much of AI.”
— David L. Poole, Alan K. Mackworth, Artificial Intelligence: Foundations of Computational Agents

여기서는 탐색을 이렇게 이해합니다.

지금 상태에서 가능한 선택을 따라가며 목표에 도달하는 경로를 찾는 과정

예를 들어 길 찾기를 생각해 봅니다.

이 구조는 길 찾기에만 쓰이지 않습니다. 일정 짜기, 퍼즐 풀기, 게임 수 읽기, 코드 수정 순서 정하기, 문서 목차 후보 비교에도 비슷한 관점을 적용할 수 있습니다.

탐색 공간(search space)은 가능한 상태와 선택지의 전체다¶

탐색 공간(search space)은 문제를 풀 때 고려할 수 있는 상태(state)와 이동(action)의 전체 구조입니다.

간단한 예시를 봅니다.

아침에 할 일을 정한다. 후보: 운동, 독서, 이메일 확인 그다음 후보: 출근, 회의 준비, 장보기

처음 선택지가 3개이고, 그다음 선택지도 3개라면 가능한 조합은 9개입니다. 선택 단계가 늘어나면 후보는 빠르게 커집니다.

아래 그래프는 같은 숫자를 위치로 다시 보여 줍니다. 단계마다 선택지가 3개로 고정되어 있어도, 단계 수가 늘어나면 후보 조합은 직선처럼 조금씩 늘지 않고 빠르게 위로 휘어 올라갑니다.

이 표는 수학을 깊게 하려는 것이 아닙니다. 중요한 감각은 이것입니다.

선택지가 조금씩만 늘어도 가능한 조합은 빠르게 커진다.

이런 증가 때문에 “전부 살펴보면 되지 않을까?”라는 생각은 곧 어려워집니다.

완전 탐색(exhaustive search)은 왜 어려워지는가¶

완전 탐색(exhaustive search)은 가능한 경우를 빠짐없이 살펴보는 방식입니다. 작은 문제에서는 좋은 기준이 될 수 있습니다. 하지만 후보가 많아지면 시간과 메모리가 빠르게 부족해집니다.

예를 들어 다음 문제들을 생각해 봅니다.

Poole과 Mackworth는 검색의 어려움이 문제 해결의 핵심이며, 효율적으로 해를 알아볼 수 있어도 효율적으로 찾는 방법이 없는 문제가 존재한다고 설명합니다. 여기서 중요한 점은 “정답을 확인하는 일”과 “정답을 찾는 일”이 다를 수 있다는 것입니다.

예를 들어 어떤 퍼즐의 완성 상태를 보면 정답인지 확인하기는 쉽습니다. 하지만 그 완성 상태에 도달하는 순서를 찾는 일은 어려울 수 있습니다.

해를 알아보는 것은 쉬울 수 있다. 해를 찾아가는 것은 어려울 수 있다.

계산 한계(computational limit)는 단순히 컴퓨터가 느리다는 뜻이 아니다¶

계산 한계(computational limit)는 컴퓨터 성능이 부족하다는 단순한 불평이 아닙니다. 문제 구조상 가능한 후보가 너무 빠르게 늘어나면, 아무리 빠른 컴퓨터라도 모든 경우를 현실적인 시간 안에 살펴보기 어렵습니다.

다음처럼 구분할 수 있습니다.

물리적 성능 향상은 중요합니다. 더 빠른 CPU, GPU, 더 많은 메모리, 병렬 처리(parallel processing)는 더 큰 문제를 다룰 수 있게 합니다. 하지만 성능 향상이 모든 탐색 문제를 없애지는 않습니다.

문제가 커지는 속도가 계산 자원 증가보다 훨씬 빠를 수 있기 때문입니다.

더 빠른 컴퓨터는 더 멀리 보게 해 주지만, 모든 길을 다 보게 해 주지는 않는다.

현대 사례: AlphaDev와 FunSearch¶

탐색 공간(search space)과 계산 한계(computational limit)는 오래된 AI 교재에만 남은 표현이 아닙니다. 현대 AI 연구에서도 “무엇을 탐색할 것인가”와 “가능한 후보가 너무 많을 때 어떻게 줄일 것인가”는 계속 등장합니다.

Google DeepMind의 AlphaDev 사례는 탐색 공간이 너무 큰 현대 사례로 볼 수 있습니다. AlphaDev는 더 빠른 정렬 알고리즘을 찾기 위해 어셈블리 명령 조합을 탐색했습니다. DeepMind는 이 문제가 어려운 이유를 다음 구절로 설명합니다.

“enormous number of possible combinations of instructions”
— Google DeepMind, AlphaDev discovers faster sorting algorithms

이 문구는 7.1의 탐색 공간 감각과 잘 맞습니다. 가능한 명령 조합이 너무 많으면 모든 조합을 살펴보는 방식은 현실적으로 어렵습니다.

FunSearch는 조금 다른 사례입니다. FunSearch는 정답 하나를 직접 찾기보다, 문제를 푸는 함수(function) 또는 프로그램(program)을 탐색 대상으로 삼습니다.

“functions written in computer code”
— Google DeepMind, FunSearch: Making new discoveries in mathematical sciences using Large Language Models

이 사례는 탐색 대상 자체를 바꿀 수 있음을 보여 줍니다. 어떤 문제에서는 해답 후보를 직접 나열하는 대신, 해답을 만들어 내는 프로그램이나 함수를 탐색할 수 있습니다.

다만 이 두 사례는 경계를 분명히 해야 합니다.

따라서 이 절에서 두 사례를 사용하는 목적은 제한적입니다.

현대 AI에서도 탐색 공간은 여전히 중요하다. 하지만 탐색의 대상은 상태, 경로, 명령 조합, 함수, 프로그램처럼 문제에 따라 달라질 수 있다.

탐색은 확률과 다른 어려움을 다룬다¶

6장에서는 불확실성(uncertainty)과 확률(probability)을 다뤘습니다. 7.1의 탐색(search)은 다른 어려움에서 출발합니다.

물론 현실 문제에서는 이 셋이 함께 나타납니다. 길 찾기에서도 가능한 경로가 많고, 교통 상황은 불확실하며, 예상 시간은 데이터로 학습될 수 있습니다.

하지만 여기서는 이 셋을 먼저 구분해 두는 편이 안전합니다.

모르는 것과, 후보가 너무 많은 것과, 판단 기준을 학습해야 하는 것은 서로 연결되지만 같은 문제가 아니다.

예시: 문서 구조를 정리하는 문제로 보기¶

탐색 문제는 길찾기나 게임에만 있는 것이 아닙니다. 문서 구조를 정리할 때도 비슷한 감각이 생깁니다.

가능한 목차 조합은 매우 많습니다. 모든 후보를 만들어 비교하기는 어렵기 때문에, 보통은 큰 구조를 먼저 잡고 각 섹션의 중심 질문을 정한 뒤 세부 후보를 줄여 갑니다.

이것은 엄밀한 탐색 알고리즘은 아닙니다. 하지만 “가능한 후보를 모두 볼 수 없으므로 기준을 두고 줄인다”는 점에서 탐색과 휴리스틱을 이해하는 비유가 됩니다.

왜 휴리스틱(heuristic)이 다음에 필요한가¶

탐색 공간이 너무 크면 모든 후보를 다 볼 수 없습니다. 그러면 다음 질문이 생깁니다.

어떤 후보를 먼저 볼 것인가? 어떤 후보는 일찍 포기할 것인가? 충분히 좋은 해를 어디에서 멈출 것인가?

이 질문이 휴리스틱(heuristic)으로 이어집니다. Poole과 Mackworth는 탐색의 어려움과 사람이 일부 탐색 문제를 효율적으로 푸는 사실이, 컴퓨터 에이전트도 특수한 경우에 대한 지식을 활용해 해를 찾도록 해야 함을 시사한다고 설명합니다. 이런 추가 지식을 휴리스틱 지식(heuristic knowledge)이라고 부릅니다.

다음 절에서는 휴리스틱을 “정답을 보장하지는 않지만 탐색을 줄이는 경험적 기준”으로 다룹니다.

체크리스트¶

• 탐색(search)을 가능한 후보를 살펴보며 해를 찾는 과정으로 설명할 수 있다.
• 상태(state), 행동(action), 목표(goal), 경로(path), 비용(cost)을 길 찾기 예시로 설명할 수 있다.
• 탐색 공간(search space)이 커질수록 가능한 조합이 빠르게 늘어난다는 점을 설명할 수 있다.
• 완전 탐색(exhaustive search)이 작은 문제에서는 가능하지만 큰 문제에서는 계산 한계에 부딪힌다는 점을 설명할 수 있다.
• 불확실성(uncertainty), 탐색 공간(search space), 학습(learning)의 어려움을 구분할 수 있다.
• 탐색 공간이 커질 때 휴리스틱(heuristic)이 왜 필요해지는지 설명할 수 있다.
• 현재 문제의 상태, 행동, 목표, 비용을 직접 잡아 탐색 문제로 설명할 수 있다.
• 지금의 어려움이 불확실성인지, 학습 부족인지, 탐색 공간 폭증인지 구분할 수 있다.

출처와 참고 자료¶

• David L. Poole, Alan K. Mackworth, Artificial Intelligence: Foundations of Computational Agents, 3rd ed., Chapter 3 Searching for Solutions, 확인 날짜: 2026-06-23.
• David L. Poole, Alan K. Mackworth, 3.1 Problem Solving as Search, 확인 날짜: 2026-06-23.
• Stuart Russell, Peter Norvig, Artificial Intelligence: A Modern Approach, 4th US ed., Full Table of Contents, 확인 날짜: 2026-06-22.
• Google DeepMind, Daniel J. Mankowitz and Andrea Michi, AlphaDev discovers faster sorting algorithms, 2023-06-07, 확인 날짜: 2026-06-23.
• Google DeepMind, Alhussein Fawzi and Bernardino Romera-Paredes, FunSearch: Making new discoveries in mathematical sciences using Large Language Models, 2023-12-14, 확인 날짜: 2026-06-23.