Post

[Study]Chapter 3, 검색을 통한 문제해결

Posted Updated
By Eastk1te
39 min read

개인적인 정리를 위한 내용으로 해당 도서에서는 다양한 예시를 통해 상세하고 직관적인 이해가 가능합니다.

CHAPTER 3. 검색을 통한 문제 해결

에이전트는 목표 상태로의 경로를 형성하는 일련의 동작들, 즉 동작열을 고찰해야한다. 이런 에이전트를 문제 해결 에이전트라고 부르고 수행하는 계산 과정을 “검색\(_{Search}\)“이라고 한다. 상태들의 분해된 표현이나 구조적 표현을 사용하는 목표기반 에이전트를 흔히 계획 수립 에이전트라 부

1. 문제 해결 에이전트

에이전트는 다음과 같은 4단계 문제 해결 절차ㅣ에 따라 문제를 해결

목표 형식화 → 문제 형식화 → 검색 → 실행

목표가 있으면 목적들이 제한되고, 에이전트가 고려할 동작들이 제한되므로 행동의 조직화가 수월해짐. 목표에 도달하는 데 필요한 상태들과 동작들의 명세를 고안한다. 이는 목표 달성과 관련된 세계의 한 부분의 추상모형에 해당한다. 실제 세계에서 동작을 취하기 전에 에이전트는 목표에 도달하는 동작열이 발견될 떄까지 여러 동작열을 자신의 모형 안에서 모의 실행한다. 해답을 찾았다면 에이전트는 동작들을 하나씩 실행한다.

  • 에이전트가 검색을 시작하려면 먼저 잘 정의된 문제를 형식화 해야한다.

환경의 가능한 상태들로 이루어진 집합 이를 상태공간이라고 부른다.

  • 문제의 요소
    1. 초기 상태
    2. 동작들의 집합
    3. 그 동작들의 결과를 서술하는 전이 모형
    4. 목표 상태들의 집합
    5. 동작비용 함수
  • 문제의 환경은 하나의 상태 공간 그래프로 표현된다.
  • 상태 공간 안에서 초기상태에서 목표 상태로 가는 경로(일련의 동작들, 즉 동작열)가 바로 해답이다.
  • 보통의 경우 알고리즘은 상태들과 동작들을 원자적으로 취급한

표현에서 세부사항을 제거하는 절차를 추상화라고 부른다. 문제 형식화가 좋으려면 그 세부 수준이 적절해야한다. 적절한 추상 수준을 좀 더 정밀하게 정의할 수는 없을까?임의의 추상적 해답을 좀 더 상세한 세계의 한 해답으로 확장할 수 있다면 그 추상은 유효\(_{valid}\)하다. 만일 추상회된 문제의 해답에 있는 각 동작을 원래 문제의 것보다 더 쉽게 수행할 수 있다면, 그 추상화는 유용\(_{useful}\)하다. 좋은 추상화에는 유효성을 유지하고 추상적 동작들을 쉽게 실행할 수 있음을 보장하는 한도안에서 세부사항을 최대한 제거하는 것이 관여한다. 이러한 능력이 없다면 지능적 에이전트는 현실 세계에 완전히 매몰될 것이다.

문제 해결 접근방식은 광범위한 과제 환경에 적용된 바 있고, 가장 잘 아려진 과제 환경을 표준화된 문제와 실세계 문제로 구분해서 나열한다. 표준화된 문제들은 문제해결 방법의 이해 또는 연습을 목적으로 한 것이고, 실세계 문제들은 사람들이 그 해답을 실제로 사용하는, 형식화가 표준화되지 않은 독특한 문제이다.

표준화된 문제 : 격자 세계 진공청소기 예제, 소코반 퍼즐, 슬라이딩 타일 퍼즐 8-퍼즐, 도널드 커누스가 고안한 제곱근 바닥, 계씅 연산 반복 정수 도달. 실세계 문제들 : 노선찾기 문제, 순회문제(외판원문제,TSP) VLSI 배치 문제, 로봇네비게이션, 자동조립시퀀싱(단백질 설계) 등

2. 검색 알고리즘들

검색 알고리즘은 검색 문제를 입력받고 그 해답을 돌려주거나 실패를 뜻하는 어떤 값을 돌려준다. 상태공간 그래프에 검색 트리를 겹쳐서 찾아보는 형태의 알고리즘들을 논의한다.

상태 공간과 검색 트리를 구분하는 것이 중요. 상태 공간은 세계의 상태들의 집합과 한 상태에서 다른 상태로의 전이를 유발하는 동작들을 서술한다. 검색 트리는 그런 상태들 사이의 경로들을 서술한다.

검색 자료 구조 우선순위 대기열 priority queue 비용이 최소인 노드를 먼저 뽑음. FIFO queue LIFO stack

중복경로 cycle 순환마디. 순환마디는 중복경로의 한 특수 사례이다. 이러한 중복 경로를 제거한다면 검색을 더 빠르게 수행할 수 있다. 흔히 하는 말로, 역사를 잊은 알고리즘은 그 역사를 반복한다. 이 문제에 대한 접근방식은 크게 세가지이다. 모든 도달된 상태를 기억 - 점검하지 않는 부류의 검색알고리즘들을 트리류 검색, 트리 같은 검색 알고리즘이라고 부른다. 역사 반복에 신경을 쓰지않는것 - 둘 이상의 경로가 같은 상태에 도달하는 것이 드물거나 불가능한 문제 형식화들이 있따. 이렇게 중복 경로들을 점검하는 부류의 검색 알고리즘들을 그래프 검색 알고리즘이라 부른다.

순환마디들은 점검하되 중복경로들은 대체로 점검하지 않는 타협안

  • 검색 트리(search tree)
    • 노드(node): 검색 공간의 한 상태
    • 간선(edge): 동작
    • 자식노드(child node), 후행자노드(successor node): 상태에서 가능한 동작들에 RESULT 함수를 적용해 각 동작의 결과를 산출하고 각 결과 상태를 생성함으로써 확장(expansion)되는 노드
    • 전선(frontier): 하나의 노드를 확장하기로 결정했을 때 새로 생성된 노드를 포함해서 확장되지 않은 노드들을 가리키는 상태 (도달되었지만 아직 확장되지 않은 노드들의 집합)
  • 검색 알고리즘 품질 평가지표
    1. 완결성(completeness; 완전성, 완비성): 문제에 해답이 존재할 때 알고리즘이 해답을 반드시 찾아내는가? 그리고 해답이 없을 때 실패를 제대로 보고하는가?
    2. 비용 최적성(cost optimality): 모든 해답중 경로 비용이 가장 낮은 해답을 찾아내는가?
    3. 시간 복잡도(time complexity): 해답을 찾는데 얼마나 시간이 걸리는가?
    4. 공간 복잡도(space complexity): 검색을 수행하는데 메모리가 얼마나 필요한가?

    인공지능 문제들에서 그래프를 초기 상태와 동작들, 전이 모형을 통해서 암묵적으로만 표현할 때가 많은데, 암묵적인 상태 공간에서는 복잡도를 목표 노드의 깊이이자 최적해의 동작 개수인 d나 임의의 경로의 최대 동작수 m, 또는 고려할 최대 자식 노드 수의 분기계수 b로 표현한다.

    \[1+b+b^2+\cdot\cdot\cdot+b^d=O(b^d)\]

3. 정보 없는 검색 전략

  • 정보 없는 검색(uninformed search) : 주어진 한 상태가 목표(들)와 얼마나 가까운지에 관해 아무런 단서도 없다.
    • 문제의 정의에만 접근할 수 있다.
    • 이 부류의 알고리즘들은 검색 트리를 구축해서 해답을 찾는다.
    • 어떤 노드를 확장하느냐에 따라 다음과 같은 알고리즘들이 있다.
      1. 최선 우선 검색
      2. 너비 우선 검색
      3. 균일 비용 검색
      4. 깊이 우선 검색
      5. 반복 심화 검색

3.1. 최선 우선 검색(best-first search; 최적 우선검색)

  • 확장할 노드를 평가함수를 이용해서 선택
  • 어떤 평가 함수(evaluation function) $f(n)$이 최솟값이 되는 노드 n 선택
  • 만일 해당 상태가 목표 상태이면 그 노드를 반환하고 그렇지 않으면 EXPAND를 적용해서 자식 노드들을 생성
  • 목표로의 경로를 나타내는 노드를 돌려주거나 실패를 뜻하는 값을 돌려준다
  • $f(n)$을 어떻게 설정하는지에 따라서 서로 다른 종류의 최선 우선 검색 알고리즘이 만들어진다.
  • 가장 얕은 노드를 먼저 확장
  • 먼저 뿌리 노드를 확장하고 뿌리 노드의 모든 자식 노드를 확장하고, 그 자식 노드들의 자식 노드들을 확장하는 식으로 …
  • 노드에 도달하는 동작의 수를 평가함수로 두고 BEST-FIRST-SEARCH를 호출 + (우선순위 대기열 → FIFO 대기열) + (reached를 상태와 노드의 mapping이 아닌 상태들의 집합으로 두기)
    • FIFO 대기열을 사용하는 것의 의미: 새로운 노드들이 뒤에 추가되고 오래된 노드들이 항상 먼저 확장되기 때문에 우선순위 대기열보다 빠르다
    • reached를 상태들의 집합으로 두는 것의 의미: 한 상태에 도달했다면 그 상태로의 더 나은 경로는 더 이상 찾을 수 없다 → 주어진 노드가 해답인지 생성 시점에 판단 → 이른 목표 판정(early goal test) 가능 (↔ 최선 우선 검색 알고리즘에서는 늦은 목표 판정)
  • 모든 동작의 비용이 같은 문제들에 대해서 최적 알고리즘 (그렇지 않은 문제에서는 최적이 아님)
  • 시간 및 공간복잡도: $O(b^d)$ (모든 상태에 후행자가 $b$개, 해답은 깊이 $d$에 존재) → 너무 크다. 시간도 시간이지만 메모리 요구량이 너무 크다
  • 경로비용 $g(n)$이 가장 낮은 노드를 확장
  • 동작들의 비용이 같지 않을 때 최적
  • 루트에서 현재 노드로의 경로 비용을 평가함수로 두고 최선 우선 검색 적용 (PATH-COST를 평가함수로 두고 BEST-FIRST-SEARCH를 호출)
  • 경로 비용이 같은 노드들을 차례로 훑는다
  • 시간 및 공간 복잡도: $O(b^{1+[C^/\epsilon]})$ ($C^$: 최적해의 비용, $\epsilon$: 각 동작 비용의 하한)
  • 완결적
  • 첫 번째로 찾아내는 해의 비용이 전선의 다른 어떤 노드의 비용보다 크지 않으므로 비용 최적성도 충족
  • 모든 경로를 비용 증가순으로 체계적으로 탐색함
  • 무한 경로에 빠지는 일이 결코 없음 (모든 동작 비용 $\epsilon$ >0라면..)
  • 검색 트리의 전선에서 가장 깊은 노드를 제일 먼저 확장 (즉 아직 확장되지 않은 가장 깊은 노드를 먼저 확장)
  • 완결적이지도 않고 최적도 아니지만 공간 복잡도가 선형
    • 공간복잡도(메모리 복잡도): $O(bm)$ ($b$: 분기 계수, $m$: 트리의 최대 깊이)
  • 깊이의 음수값을 평가함수로 두고 BEST-FIRST-SEARCH를 호출하는 방식으로 구현
  • 보통은 그래프 검색 방식이 아니라 트리류 검색으로 구현
  • 트리류 검색이 적합한 문제에서 깊이 우선 탐색은 메모리 효율성이 좋다.
  • 시간복잡도: 상태의 수에 비례
  • 깊이 우선 검색이 무한한 경로를 따라 헤매는 것을 방지하는 방법으로 깊이 제한 검색(depth-limited search)가 있다
    • 깊이 한계 $l$을 정해두고 깊이가 $l$인 노드들은 마치 후행자가 하나도 없는 것처럼 취급
  • 깊이 우선 검색의 한 변형으로 역추적 검색\(_{backtracking}\)이 있다.
  • 모든 깊이 한계를 시험함으로써 최장의 깊이 한계 $l$을 찾는 문제를 해결
  • 목표가 나올 때까지 깊이 한계를 증가하면서 깊이 우선 검색을 호출
  • 모든 동작의 비용이 같은 문제들에 대해 최적성을 충족, 유한 비순환 상태 공간에 대해 완결적, 경로 끝까지 거슬러 올라가면서 모든 순환마디 점검하면 모든 유한 상태 공간에 대해 완결적
  • 메모리 요구량이 적당: 해가 존재할 때는 $O(bd)$, 해가 없는 무한 상태 공간에서는 $O(bm)$
  • 시간 복잡도: 해가 존재할 때는 $O(b^d)$, 없으면 $O(b^m)$

일반저긍로, 검색 상태 공간이 메모리에 담을 수 있는 크기보다 크고 해답의 깊이가 알려지지 않을 때의 정보 없는 검색방법으로 바람직하다.

단방향 검색에서 다양한 버전이 있는것처럼, 양방향 검색에서도 다양한 버전이 있지만 양방향 최선우선검색을 설명.

  • 초기 상태에서 순방향으로 진행하는 검색과 목표에서 시작하는 역방향 검색을 동시에 진행
  • 두 전선이 만나는 경우 해답이 발견된 것으로 검색을 종료

4. 정보 있는 검색 전략

  • 정보 있는 검색(informed search)
    • 목표들의 위치에 관한 영역 특화(domain-specific) 힌트들을 사용하는 검색 전략
    • 정보 없는 전략보다 좀 더 효율적으로 해들을 찾아내는 이유와 방법을 설명
    • 힌트는 $h(n)$으로 표기하는 발견적 함수(heuristic function) 형태로 주어진다.
      • $h(n)$= 노드 $n$의 상태에서 목표 상태로 가는 최저 비용 경로의 비용 추정치
  • $h(n)$이 가장 작은 노드(즉, 목표와 가장 가깝다고 추정되는 노드)를 제일 먼저 확장
  • 가정: 목표에 가장 가까운 노드를 확장하면 해답에 빨리 도달할 가능성이 크다
  • 최적은 아니나 효율적인 경우가 많다

4.2 A* 검색

  • $f(n)=g(n)+h(n)$이 최소인 노드를 확장
    • $g(n)$: 초기 상태에서 노드 $n$으로의 경로 비용, $h(n)$은 $n$에서 목표로의 최단 경로의 추정 비용
    • $f(n)$: $n$을 거쳐 목표로 나아가는 최선의 경로의 추정 비용
  • $h(n)$이 허용 가능일 때 완결적이고 최적
  • 허용 가능한 발견적 함수를 사용한 A* 검색이 실전에서 잘 작동한다.
  • 여러 문제에서 공간 복잡도 한계가 존재 (메모리를 너무 많이 사용한다)

검색을 시각화하는 유용한 방법 중 하나는 지형도에서 흔히 보는 등고선\(_{contour}\)과 비슷한 선을 상태공간에 그리는 것이다.

Figure 1 : 등고선

A* 검색에서 등고선들은 목표 상태를 향해 확장되며, 최적경로 부근에서 좀 더 좁게 집중된다. 하나의 경로를 확장할때 g 비용들이 단조 증가임은 명확하다. 그런데 f 비용은 단조 증가인지는 ㅁ자명하지 않다. 만일 발견적 함수가 일관적이어야 단조 증가이다. 일관성 있는 발견적 함수를 사용하는 A*를 최적으로 효율적 이라고 부른다. 해당 알고리즘이 효율적인 이유는 최적해를 발견하는 데 필요하지 않은 검색 트리 노드들을 대거 잘라내는 가지치기를 활용하기 떄문이다.

만족 검색 : 비허용 발견적 함수와 가중 A* 비허용 발견적함수, 즉 비용을 과대팡가할 수도 있는 발견적 함수를 A에 사용하면 최적해를 놓칠 위험이 있지만 대신 발견적 함수가 좀 더 정확할 수 있으며, 따라서 확장되는 노드들의 수가 줄어든다. 도로 기술자들이 사용하는 개념으로 우회 지수라는 것이 있는데, 도로의 전형적인 곡률을 고려해서 직선 거리에 곱하니 하나의 계수가 된다. 이러한 개념을 적용해 아래와 같은 수식으로 나탄낸 긋이 가중 A 검색이라고 부른다.

  • 발견적 함수의 값을 더욱 중요시 ($f(n)=g(n)+W \times h(n)$)
  • 목표 방향으로의 검색에 집중하기 때문에 더 적은 노드를 확장하지만 대신 최적성을 보장하지는 않는다.

준최적화 검색 알고리즘들은 다양하다. 이를 준최적 해의 품질이 어느정도냐에 따라 분류할 수 있따. 최적 비용에 상수 계수 W를 곱한 값 이내의 해를 돌려줌을 보장하는 유계\(_{bounded}\) 준최적 검색, 어떤 상수 C보다 낮은 비용의 해를 찾는 비용\(_{bounded-cost}\) 유계 검색, 빨리 찾을 수 있다면 그 어떤 비용의 해도 허용하는 비용 무계\(_{unbounded-cost}\)검색으로 소위 스피디 검색\(_{speedy-search}\)가 있다.

메모리 제한 검색.

공간을 절약하는 검색 기법을 소개한다. 각 상태가 방문된 횟수를 뜻하는 참조 횟수\(_{reference-count}\)를 이용해서 더 이상의 도달 경로가 존재할 수 없는 상태들을 reached 테이블에서 제거할 수도 있다.

4.4 빔 검색(beam search; 다발 검색)

  • 전선의 크기를 제한하는 방식, 쉬운 형태의 제한 방법으로 f 점수 기준으로 상위 k개의 노드만 전선에 두는 것이다.
  • 전선의 크기를 제한하기 때문에 완결성이 깨지고 최적이 아닌해가 산출되지만
  • 많은 문제에서 빔 검색은 좋은 근최적 해를 산출함
  • 완전한 검색보다 더 빨리 실행됨

4.4 반복 심화 A* 검색(iterative-deepening A, IDA)

  • 깊이 우선 검색에 대한 반복 심화 기법과 비슷한 방식으로 A*를 변형한 것
  • 가용 메모리에 다 담을 수 없는 문제에 흔히 쓰이는 중요한 알고리즘
  • IDA*은 f의 비용을 차단 값으로 사용
    • 각 반복은 한 f-등고선의 모든 노드를 조사해서 그 등고선을 바로 넘어선 노드를 찾고 그 노드를 다음번 반복의 등고선으로 사용
  • A* 공간 복잡도 문제 해결

4.5 재귀적 최선 우선 검색(recursive best-first search, RBFS)

  • 표준 최선 우선 검색의 동작을 흉내내되 오직 선형 공간만 사용하는 간단한 재귀적 알고리즘
  • 현재 경로를 무한정 따라 내려가는 대신 $flimit$ 변수를 이용해서 현재 노드의 임의의 조상에서 시작하는 최선의 대안 경로의 f값을 추정한다.

  • 4.6 SMA* (단순화된 메모리 제한 검색)

IDA, RBFS는 메모리를 너무 적게 사용한다는 문제가 있다. 두 알고리즘은 자신이 밝혀낸 것들을 대부분 잊기 떄문에, 같은 상태들을 여러 번 다시 탐색하게 될 수도 있다. 따라서, 가용 메모리가 얼마나 남았는지 알아보고 그 가용 메모리를 모두 사용할 수 있는 방법을 찾는 합당한 알고리즘으로 MA\(_{Memory-boundtd-A*}\), SMA*\(_{simplified-MA*}\)가 있다. 이 중 더 단순한 형태를 설명한다.

  • 새 노드를 추가할 때 기존 노드를 제거해서 공간을 만든다.
  • 항상 최악의 잎 노드, 즉 f값이 가장 큰 잎 노드를 제거한다.

메모리 제약은 문제를 계산 시간의 관점에서 처리 불가능한 문제로 만들 수 있따.현재로서는 시간과 메모리의 절충을 설명해주는 이론이 ㅇ벗지만, 이것은 피할 수 없는 문제로 보인다. 유일한 탈출구는 최적성 요구조건을 포기하는 것이다.

양방향 발견적 검색

4.7 양방향 A* 검색

  • 양방향 최적 우선 검색에서도 $f(n)=g(n)+h(n)$을 사용하는 방식

지금까지 순방향 발견적 함수가 목표로의 거리를 추정하고 후방향 발견적 함수출방점으로의 거리를 추정하는 접근방식 하나를 front-to-end 검색이라 부르고 이와 달리 front-to-front 검색은 상대방 전선으로의 거리를 추정한다.

전선의 노드 수가 매우 많다면 모든 노드에 발견적 함수를 적용해서 그 최솟값을 찾는 것은 당연히 비효율적이다. 한 가지 해결책은 전선에서 몇 개의 노드들을 표본 추출하여 전선을 요약하는 것이 가능한 문제영역이라면, 전선을 감싸는 경계 상자를 점진적으로 계싼해 나가면서 그 경계상자로의 거리를 발견적 함수로 사용할 수 있따.

  • 양방향 검색이 단방향 검색보다 더 효율적일 때도 있고 그렇지 않을 때도 있다.

5. 발견적 함수

  • 발견적 검색 알고리즘의 성능은 발견적 함수의 품질에 의존한다.

발견적 함수의 품질을 측정짓는 한 가지 기준은 유효 분기 계수\(_{effective-bracnhing-factor}\) $b$이다. $b$는 깊이가 d인 균일 트리가 N+1개의 노드들을 담는 데 필요한 분기 계수와 같다.

$$$N+1=1+b+(b)^2 + \cdot\cdot\cdot + (b*)^d$

  • 좋은 발견적 함수를 구축하는 방법

  1. 완화된 문제로부터 발견적 함수 생성

    동작들에 대한 제약이 더 적은 문제를 가리켜 완화된 문제라고 부른다. 완화된 문제의 최적 해의 비용을 구하는 함수는 원래 문제에 대한 허용 가능 발견적 함수

  2. 부분 문제로부터 허용 가능 발견적 함수 생성: 패턴 데이터베이스

    허용 가능 발견적 함수를 주어진 문제의 부분 문제(subproblem)의 해답 비용해서 도출 패턴 데이터베이스에 깔린 착안은 모든 가능한 부분 문제 사례의 정확한 해답비용을 저장해두어 해당 부분 문제 구성을 조회해서허용 가능 발견적 함수를 계싼한다. 이 검색의 비용은 이후 문제 사례들을 풀면서 상각\(_{amortizing}\)되므로, 풀어야할 문제가 많을것으로 예쌍되는 상황에 적합하다.

  3. 랜드마크를 이용한 발견적 함수 생성

    사전 계산(precomputation) 기법

    가능한 모든 두 정점 사이의 최적 경로 비용을 미리 계산해서 저장해두면 완벽한 발견적 함수를 만들어 낼 수 있다. → 랜드마크 지점들에 대해서만 사전계산을 수행

    현재 노드에서 도달하는 비용이 가장 낮은 랜드마크를 찾고, 그 랜드마크로의 비용과 그 랜드마크에서 목표로의 비용을 더한 것이 바로 그러한 발견적 함수이다. 몇몇 경로 찾기 알고리즘은 지름길, 즉 최적의 다중 동작 경로를 정의하는 인공적인 간선을 그래프에 추가함으로써 시간을 더울 절약한다.

    이러한 발견적 함수는 효율적이지만 허용 가능이 아니다. 차분 발견적 함수는 조금 더 효율적이면서 허용성까지 갖춘 발견적 함수를 고안할 수 있다. 이 발견적 함수는 n에서 L까지의 전체경로를 고려하고, 그중 목표에서 L까지의 부분 경로를 빼면, n에서 목표로의 정확한 경로비용이 나온다. 라고 말하는것과 같다.

    랜드마크 지점들을 선택하는 방법은 여러 가지이다. 한가지 좋은 방법의 예로 그래프의 무게중심\(_{centroid}\)를 찾고 k개의 쐐기 영역들을 그 무게중심 주위에 배치한 후 각 쐐기에서 중심에서 제일 먼 정점을 선택하는 것이다.

  4. 학습을 통한 검색 향상

에이전트가 학습을 통해서 검색을 더 개선할 수는 없알까? 답은 가능하다./ 이런 개선 방법들은 메타수준 상태공간이라고 부르는 중요한 개념에 기초한다. 메타수준 상태 공간의 각 생태는 보통의 상태공간에서 검색을 수행하는 프로그램의 내부 상태를 포착한다. 두 개념을 구분하기 위해 루마니아 지도 같은 보통의 상태공간을 객체 수준 상태 공간이라 부르자.

메타수준 학습 알고리즘은 경험들로부터 유망하지 않은 부분 트리의 탐색을 피하는 방법을 배울 수 있따.

경험을 통한 발견적 함수의 학습.

경험 이란 문제를 견본들을 활용해서 학습 알고리즘은 검색 도중 발생하는 다른 상태의 진 경로 비용을 근사하는 발견적 함수를 구축할 수 있다. 이런 접근방식들은 대부분 발견적 함수의 불완전한 근사를 배우므로 허용성이 보장되지 않을 위험이 있다. 따라서 학습 시간, 검색 실행 시간, 해답 비용 사이에는 필연적으로 절충 관계\(_{trade-off}\)가 존재한다. 몇몇 기계학습 기법들은 상태의 발견적 값을 예측하는 데 관련된 상태 특징들이 제공될 때 더 잘 작동한다. 흔히 쓰이는 선형 결합 접근방식에서 발견적 함수가 목표상태일떄 \(h(n) = 0\)이라는 조건을 충족하긴 하지만, 반드시 허용 가능 발견적 함수이거나 일관적인 발견적 함수라는 보장은 없다.

##

. REFERENCES

  1. temp
  2. temp
  3. temp
  4. temp



Study, AIMA
Study AIMA AI : A Modern Approach 4th
This post is licensed under CC BY 4.0 by the author.