인공지능은 탐색을 이용해 논리적으로 문제를 해결할 수 있다.

1) 인공지능과 탐색

인공지능이 문제를 해결하려면 우선 '문제'가 무엇인지 정의할 수 있어야 하며, 문제를 해결하기 위해서는 문제 해결 과정을 절차적으로 표현할 수 있고, 문제 상황을 논리적으로 또는 수학적으로 표현할 수 있어야 한다. 이때, 이러한 문제를 해결할 수 있는 도구가 바로 탐색이다.  탐색은 기계가 문제를 해결할 때 정답을 찾아가기 위해 활용된다.
탐색을 통해 문제의 해답을 찾는 과정에서 거치게 되는 여러 상황들 각각을 상태라고 하며 상태를 모아 놓은 공간을 상태 공간이라고 한다. 문제를 해결하기 시작한 상태를 초기 상태라고 하고, 목표가 되는 상태를 목표 상태라고 한다. 궁극적으로 탐색은 초기 상태에서 목표 상태에 이르기까지 최적의 경로를 찾는 것으로 정의할 수 있다.

3) 탐색 트리

컴퓨터에서 그래프는 데이터 간의 관계를 점과 선으로 나타낸 것으로, 점은 데이터를 나타내고 선은 데이터 간의 관계를 나타낸다.  트리는 이러한 그래프의 일종으로 나무를 뒤집은 모습과 닮아 있으며, 가계도처럼 계층 구조를 표현할 때 사용한다. 또한 점과 선으로 이루어져 있지만 서로 다른 두 점을 잇는 길은 하나뿐이다.

탐색 기법은 크게 문제에 관한 정보가 있는지 없는지에 따라 나눌 수 있다.

경우의 수가 아주 많은 문제의 경우 문제 해결을 위한 트리가 매우 복잡한 모양이 됨
따라서 복잡한 트리를 빠른 시간 내에 효과적으로 탐색할 수 있는 방법이 필요함

탐색 방법은 상태 공간에 내재된 정보가 문제 해결 과정에 영향을 주는지 주지 않는지에 따라 무정보 탐색과 휴리스틱 탐색으로 나뉨

무정보 탐색은 상태 공간에 관한 정보 없이 기계적인 순서로 트리를 탐색하는 방법이다.

1) 깊이 우선 탐색

탐색 트리에서 길이 있는 한 앞으로 계속 전진하여 탐색하는 방법
분기점에 도착했을 때 방문하지 않은 곳을 골라 앞으로 나아가는 과정을 통해 목표에 도달함
막다른 길, 길이 없는 경우는 이전 상태 중 다른 경로로 갈 수 있는 분기점까지 되돌아가 다시 탐색

2) 너비 우선 탐색

트리를 탐색하다 분기점에 도착했을 때 동일한 깊이의 상태 공간을 모두 방문하는 방법
목표 지점까지 가로 방향으로 나아가며, 방문한 적이 있는 분기점은 재방문하지 않음
얕은 깊이에 있는 노드부터 모두 탐색함

휴리스틱 탐색은 정보를 활용하여 트리의 일부만 탐색하는 방법이다.

휴리스틱 탐색은 경험이나 지식을 활용하여 빠르고 효울적으로 결과를 얻을 수 있을 것이라는 근거에 기반함
예시로, 어느 지점에서 출발하여 목적지에 도착해야 할 때 교통 상황을 잘 알고 있다면 차가 막힐 무렵에는 다른 길로 돌아가는 것이 좋다고 경험적으로 판단할 수 있음

다음 두 가지 상황에서 실현 가능한 결정을 위해 사용함
탐색 공간이 너무 넓어 탐색 공간을 모두 방문할 수 없을 때
해가 정확하게 존재하지 않을 때

1) 언덕 등반 탐색

매번 한 노드에서 다음 노드로 이동할 때 이동 가능한 노드 중 그 평가 함숫값이 가장 큰 노드로 이동하며 경로를 탐색하는 방법

알고리즘
단계 1. 현재 상태를 확인한다.
단계 2. 목표 상태에 도달하거나 현재 상태가 더 이상 변하지 않을 때까지 반복한다.
2-1. 현재 상태의 자식 노드를 구하고, 각각에 평가 함숫값을 부여한다.
2-2. 자식 노드의 평가 함숫값이 현재 상태의 평가 함숫값보다 좋은 것이 있으면 그 노드로 이동한다.

현재 노드보다 더 큰 평가 함숫값을 가지는 자식 노드가 나타나지 않으면 목표 상태가 아닌 곳에서 탐색을 멈출 수도 있다는 문제가 있음

2) 최고 우선 탐색

언덕 등반 탐색의 단점을 보완한 탐색 방법
open 리스트와 closed 리스트를 적절히 사용함
탐색을 시작할 때 open 리스트에 출발점(초기 상태)을 넣은 후 첫 탐색 주기를 시작
매 주기의 시작때 그 당시 open 리스트에 있는 노드 중 평가 함숫값이 가장 큰 노드로 이동하여 그 노드를 closed 리스트로 옮김

언덕 등반 탐색은 하나의 노드가 선택되면 같은 레벨의 다른 노드는 다시 고려하지 않지만, 최고 우선 탐색에서는 지나간 노드도 계속 비교하여 추후 선택될 수 있다

알고리즘
단계 1. open = (A/5), closed = ()
- 초기 상태 노드 A에서 시작한다.
단계 2. open = (B/6, C/4, D/3), closed = (A/5)
- B와 B의 형제 노드(C/4, D/3)를 모두 open 리스트에 포함한다.
- A의 자식 노드 B, C, D 중 평가 함숫값이 가장 큰 B로 이동한다.
- B를 closed 리스트에 넣는다.
단계 3. open = (C/4, D/3, E/3, F/2), closed = (B/6, A/5)
- B의 자식 노드를 open 리스트에 추가한다.
- open 리스트에서 평가 함숫값이 가장 큰 C로 이동한다.
- C를 closed 리스트에 넣는다.
단계 4. open = (H/8, G/7, D/3, E/3, F/2), closed = (C/4, B/6, A/5)
- C의 자식 노드를 open 리스트에 추가한다.
- open 리스트에서 평가 함숫값이 가장 큰 H로 이동한다.
- H를 closed 리스트에 넣는다.
단계 5. open = (G/7, D/3, E/3, F/2), closed = (H/8, C/4, B/6, A/5)
- 목적지 H를 찾았다.

최고 우선 탐색은 경우에 따라 정답을 찾지 못하는 언덕 등반 탐색의 문제는 해결하지만 어떤 평가 함수를 사용하느냐에 따라 성능이 많이 달라질 수 있다.

3) A* 알고리즘

가장 효율적으로 목표 상태를 찾는 것을 목적으로 함
앞선 최고 우선 탐색과는 달리 일상생활 속 문제에서는 목표 상태뿐만 아니라 최단 경로까지 찾아야 할 때도 있는데, 이러한 경우 목표 상태와 최단 경로를 찾는 상황을 고려한 평가 함수를 사용해야 한다.

g(n) = 현재 위치에 도달할 때까지 실제 이동 거리
h(n) = 현재 위치에서 목적지까지의 거리 추정 최소치
이 두 함수를 이용하여 최적의 경로를 통해 목표 상태에 도달할 수 있다.

기존의 지식에서 추론을 통해 새로운 지식을 얻을 수 있다.

1) 명제 논리 추론

연역적 추론은 전제에 이미 포함된 결론을 도출해 내는 추론 방식으로 새로운 것을 발견할 수 없는 한계를 가지고 있음

귀납적 추론은 개별적인 특별한 사실이나 현상에서 그러한 사례까지 포함된 일반적 결론으로 이끌어 내는 방식

(1) 명제의 연역적 추론
연역적 추론은 두 가지 이상 존재하는 참인 명제를 동치와 추론 규칙을 활용하여 새로운 명제를 만들어 냄

명제 논리 추론에는 긍정 논법, 삼단 논법 등이 있음

(2) 명제 논리 증명
명제 논리의 증명은 다음의 명제가 주어졌을 때 추론 규칙에 따라 추론된 사실이 참이 됨으 증명하는 것임
명제1 - 계절이 여름이면 메밀꽃이 핀다.
명제2 - 계절이 여름이다.
추론된 사실 - 메밀꽃이 핀다.

기호로 표현하면
p
p → q
∴ q

2) 술어 논리 추론

술어 논리는 서술어를 사용하는 논리이며 앞의 전칭 한정 기호와 존재 한정 기호를 사용하여 논리를 식으로 표현함
명제 논리와 다르게 전칭 기호와 존재 기호를 사용하여 양적인 표현을 동반한 추론을 할 수 있음