탐색 1

03 May 2018

탐색과 인공지능

문제를 해결하는 과정을 ‘상태탐색문제’로 형식화한다면,

  '상태'는 문제 풀이과정 중 특정한 상황이고,
  '전이(transitsion)'는 가능한 답을 포함한 '상태'들의 공간을 실행하고, 문제를 푸는 과정이다.
  '행동'은 상태 전이를 일으키는 연산자이다.  
  

문제의 해결과정은 초기 상태에서 출발하여 탐색을 통해 목표 상태에 도달한다.
인공지능은 데이터로부터 추론을 통한 문제해결을 하기 때문에, 컴퓨터가 다를 수 있게 인간의 지능 또는 지식을 표현할 수 있어야 한다.

알고리즘

데이터를 어떻게 잘 저장(가공)하고 어떻게 답을 잘 찾는가?

문제를 해결하기 위한 논리, 답을 잘 찾는 방식을 ‘알고리즘’이라 한다.

• 탐색 알고리즘 : 필요한 데이터를 찾기 (선형/ 이진/ 트리)
• 정렬 알고리즘 : 기준에 맞게 나열하기

알고리즘 평가

알고리즘의 효율성을 평가하기 위해 시간 복잡도와 공간 복잡도를 사용한다. 특정 데이터가 아닌, 데이터의 수에 따른 수행 속도의 변화 정도를 사용한다.

탐색과 해결 가능한 문제

기본적 탐색 기법

경로를 선택할 때는

1. 경로가 짧은가
2. 탐색의 비용이 적은가
3. 해가 있다면, 반드시 찾을 수 있는가를 고려해야 한다.

해결 가능한 문제의 종류

1. 경로 탐색 문제
2. 게임 문제
3. 제약 조건 만족 문제

탐색 (데이터의 개수는 n이라 가정 )

1. 순차 탐색

2. 이진 탐색

3. 트리 탐색 (DFS/ BFS)

	DFS	BFS
최단 경로 보장	O	X
자료 구조	Stack	Queue
Space Complexity	low	high

DFS
BFS

최단 경로 알고리즘 : 탐색 그래프 상에서 각 지점을 노드, 지점간 거리를 가중치로 계산한다 .

1. Dijkstra 알고리즘
2. Kruskal 알고리즘
3. Floyd 알고리즘

탐색 방향

• 전향 : 시작 -> 목표
• 후향 : 목표 -> 시작
• 동시 : 전향 ^ 후향

같은 알고리즘을 사용해도 어떤 추론 방향을 선택하느냐에 따라 다르다