학사/아주대 융시공

[3학년][1학기][인공지능시스템][3w]

jaeseokk963 2024. 3. 23. 20:02

Search & Optimization

Search

  • 어떤 문제가 있을 때, 해 공간에서 최적의 해를 찾기 위한 방법
  • 해공간(Solution space): 해의 후보들을 모아놓은 집합
  • 해: 일련의 동작 또는 하나의 상태
  • 탐색의 문제
  1. Missionary-cannibal problem: 늑대와 양 강 건너기 문제
  2. Tic-tac-toe problem: 순서대로 x와o를 놓는 문제
  3. Rubik’s cube
  4. 8-puzzle problem: 8개의 숫자와 1개의 빈칸이 있는 퍼즐을 숫자 순서대로 맞추는
  5. TSP: 주어진 도시들을 한 번씩 거쳐서 다시 돌아오

1. State space & Search(상태공간과 탐색)

  • State: 특정 시간에 주어진 문제가 당면해 있는 상황
  • World: 문제에 포함된 객체와 처한 상태 등 필요한 정보
  • State space: 문제를 해결하기 위해 필요한 object, state, world 등의 정보, 초기 상태, 문제 해결의 상태, 가능한 모든 상태의 집합
    • Initial state/goal state

State Space Graph

  • 상태 공간에서 각 행동에 따른 상태의 변화를 나타낸 그래프
    • 노드: 상태, 링크: 행동
    • Solution: initial state에서 goal state로 도달하기 위한 path
  • 일반적인 문제에서 상태 공간 매우 큼
    • 미리 상태 공간 그래프를 만들기 어려움
    • 탐색 과정에서 그래프 생

2. Uninformed search(맹목적 탐색) = Blind search

  • 정해진 순서에 따라 상태 공간 그래프를 탐색하는 방법
  • 현재 상태에서 목표 상태까지의 노드의 개수를 알지 못하고 해를 찾아 나가는 탐색 방법
  • DFS, BFS, Depth-limited search 등 여러 종류
  • 문제에 따라 적합한 탐색 방법의 선택
  • 탐색 방법의 평가
    • Complete: 해를 찾아 주는가?
    • Optimal: 찾은 해가 최적해임을 보장하는가?
    • Time & space Complexity: 알고리즘의 시간, 공간 복잡

DFS

  • 깊이 우선 탐색
  • 초기 노드에서부터 깊이 방향으로 탐색
  • 목표 노드에 도달 시 종료
  • 더이상 진행 불가하면 BackTracking
  • 방문한 노드는 재방문 X
  • Complexity → 복잡도 질문하기, O(V+E) 아닌가?
    • time: O(b^m)
    • space: O(bm)
    • m: state space에서 가장 깊은 depth
  • ex) 8-puzzle 문제: 루트 노드에서 현재 노드까지 경로 하나만 유지

BFS

  • 너비 우선 탐색
  • 초기 노드에서 시작하여 모든 자식 노드를 확장하여 생성
  • 목표 노드가 없으면 단말노드에서 다시 자식 노드 확장
  • Complexity
    • time: O(b^d)
    • space: O(b^d)
    • b: child node 개수
    • d: goal state의 depth
  • ex) 8-puzzle 문제: 전체 트리를 메모리에서 관리

Depth-limited search

  • 깊이에 제한을 둔 DFS 알고리즘
  • Completeness: No
  • Optimality: No
  • Complexity
    • time: O(b^L)
    • space: O(bL)
    • L: 깊이 제한

Iterative-deepening search

  • 반복적 깊이심화 탐색
  • 깊이 한계가 있는 깊이 우선 탐색을 반복적으로 적용

Bi-directional search

  • 양방향 탐색
  • 초기 노드와 목표 노드에서 동시에 너비 우선 탐색을 진행
  • 중간에 만나도록 하여 초기 노드에서 목표 노드로의 최단 경로를 찾는 방법

Summary

  • DFS
    • 메모리 공간 사용 효율적
    • 최단 경로 해 탐색 보장 불가
  • BFS
    • 최단 경로 해 탐색 보장
    • 메모리 공간 사용 비효율
  • 반복적 깊이심화 탐색(IDS)
    • 최단 경로 해 보장
    • 메모리 공간 사용 효율적
    • 반복적인 깊이 우선 탐색에 따른 비효율성
    • 실제 비용이 크게 늘지 않음
    • 각 노드가 10개의 자식노드를 가질 때, 너비 우선 탐색 대비 약 11%정도 추가 노드 생성
    • 맹목적 탐색 적용 시 우선 고려대상

3. Informed search: Heuristic 탐색

  • 정보 이용 탐색
    • State space가 매우 커질 경우 uninformed search가 효과적이지 않음(메모리, 시간 비효율)
    • 상태 공간의 정보를 이용하여 모든 노드를 탐색하지 않고 해를 찾는 방법
    • 휴리스틱 탐색
    • 언덕오르기, 최상 우선 탐색, 빔 탐색, A* 알고리즘 등
  • 휴리스틱
    • 시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나
    • 굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 어림짐작 하는 것
    • 실험/경험
    • ex) 최단 경로 문제
  • 탐색 공간에서의 해 찾기
    • Global maximum
    • Local maximum
  • Local Maximum을 찾는 알고리즘
    • 언덕 오르기, simulated annealing, local beam, genetic, best-first 등
  • Global Maximum을 찾을 수 있는 알고리즘
    • A* search

Hill climging method

  • 지역 탐색, 휴리스틱 탐색
  • 현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드 하나를 확장해가는 탐색 방법
  • 국소 최적해에 빠질 가능성
  • 알고리즘
    • 현재 노드 선택
    • 현재에서 가장 높은 값을 갖는 이웃 선택하여 현재보다 값이 크면 현재 노드를 이웃노드로 선택
    • 위를 반복하되, 이웃노드가 현재 노드보다 크지 않으면 종료
  • Issue
    • 지역 최적해를 찾게 됨
    • Ridges(산등성이)
    • Plateaux: 해를 찾을 때 변화가 없는 평평한 값에 빠질 때 해 찾기 어려움

Best-First Search

  • 일반적인 트리 탐색 또는 그래프 탐색 알고리즘으로 평가함수 h(n)에 따라 탐색 확장
  • Depth-first search와 유사한 방법
  • 현재에 가장 좋은 것으로 선택하는 방법
  • Non-optimal
  • Incomplete
  • 탐색 방법의 평가
    • Complete: 해를 찾아주는가?
    • Optimal: 찾은 해가 최적해임을 보장하는가?
  • 확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색
  • 남은 거리를 정확히 알 수 없으므로 heuristic 사용

A* 알고리즘

  • Estimated total cost hat f(n)을 최소로 하는 노드로 확장해 가는 방법
  • f(n): 노드 n을 경유하는 전체 비용
    • 현재 노드 n까지 이미 투입된 비용 g(n)과 목표 노드까지의 남은 비용 h(n)의 합
    • f(n) = g(n) + h(n)
  • h(n): 남은 비용의 정확한 예측 불가
    • hat h(n): h(n)에 대응하는 휴리스틱 함수
  • hat f(n): 노드 n을 경유하는 추정 전체 비용
    • hat f(n) = g(n) + hat h(n)
  • A* 탐색은 Optimal
    • h(n)이 Admissible heuristic이면 optimal
    • Admissible: 주어진 state에서 goal에 도달하기까지 비용이 높게 추산되지 않음
  • A* 탐색은 complete

Informed search

  • 해 공간이 커서 모든 상태를 탐색할 수 없을 때
  • 맹목적 탐색으로 해를 찾기 어렵거나 시간이 오래 걸리는 문제
  • Heuristic한 방법으로 해를 탐색

Heuristic Algorithm

  • Hill-climbing
  • Best-first search
  • A* algorithm