학습내용
- 인공지능과 알고리즘
- 인공지능과 관련된 흥미로운 문제들
학습목표
- 인공지능에 문제 해결의 중요성과 A*알고리즘에 대해 설명할 수 있다.
- 인공지능과 관련된 흥미로운 문제들을 풀어볼 수 있다.
1. 인공지능과 알고리즘 1) 알고리즘이란 무엇인가?
- 문제 해결을 위한 단계들을 체계적으로 명시하는 것 - 문제를 해결하는 방법의 상세한 특징을 기술하는 것 - 표현 방법 : 순서도 / 유사 코드 / 언어적 표현 - 신경망에서의 역전파 알고리즘 등
- 알고리즘은 종류가 다양함
2) 생활 속의 알고리즘
3) 휴리스틱을 이용한 알고리즘 - 휴리스틱
→ 비슷한 문제에 대한 과거의 경험들을 바탕으로 직관적으로 판단하여 선택하 는 의사결정 방식
- 인공지능에서 휴리스틱 알고리즘이 자주 사용 - 논리적이거나 최적의방법을 보장하는 것은 아님 - 만족할만한 해결책의 비교적 빠른 실용적인 방법 - 인공지능 외에도 심리학, 경제학 분야에서 많이 사용
4) 휴리스틱의 예
- ‘경험적 지식’을 바탕으로 문제를 해결하는 휴리스틱 - 어떤 문제를 이해하기 어려우면 그림으로 그려 보기 - 해답을 얻었다고 가정하고 반대 방향으로 유도해보기 - 문제가 추상적이면 구체적인 예를 시도
5) 인공지능 A*알고리즘
- 1986년 미국의 피터 하트 외 2명이 제안 - 문제 해결에 효과적인 탐색 알고리즘
- A* 알고리즘은 최상우선 탐색 중 가장 잘 알려짐
- F = G + H
- G(Goal) 목표 : 시작 노드로부터 이 노드까지 오는데 드는 비용
- H(Heuristic) 휴리스틱 : 이 노드에서 목표까지 가는데 드는 ‘추정 비용’
- F(Fitness) 적합도 : G와 H의 합 (F값이 낮을 수록 최단 경로일 가능성이 높음)
- A*알고리즘은 최단경로를 찾아내는 다익스트라 알고리즘과 유사하지만, A* 알 고리즘은 완전한 최단 경로를 찾는 것이 아닌 최단 경로의 근사 값을 찾아내는 것이 목표
- 다익스트라 알고리즘에 비해 훨씬 빠름
6) 8-Queens 문제
- 8-Queens 문제는 체스에서 유래
- 서로를 공격하지 않는 위치에 8개의 퀸 배치
- 퀸은 수평, 수직, 대각선 방향으로 원하는 칸수만큼 이동 가능 - 모든 퀸은 서로 공격 당하지 않는 위치에 놓임
- 64개의 칸을 가진 8-Queens 문제의 경우의 수 → 4,426,165,368(약 44억 가지의 경우의 수) - 인공지능 방법으로 순식간에 해답을 구함
2. 인공지능과 관련된 흥미로운 문제들 1) 인공지능 문제 해결을 위한 중요 단계
→ 3회의 이동으로 가능 → 3번 상자를 C에 이동
→ 1번 상자 위에 2번 상자를 쌓고 그 다음 3번 상자를 쌓기
- 상자 쌓기 문제 인공지능적 풀이
→ 규칙기반 시스템의 지식베이스와 추론 규칙을 만들어 적용
→ A 위에는 1, 3이 차례로 있고, B 위에는 2가 있음 C위에는 아무것도 없다는 사실을 지식베이스에 저장
- 추론 규칙
→ “상자를 하나씩 옮긴다.”
→ “작은 번호의 상자가 큰 번호의 상자 밑으로 놓인다.”
- 목표상태
→ “A위에 1, 2, 3의 상자가 차례대로 놓인다.”
나. 물통 문제
- 주어진 사실과 규칙들을 적용하여 문제 해결
- 물통 문제에서 사용할 수 있는 규칙이나 동작 → 물통에 물을 가득 채우기
→ 물통의 물을 전부 다 비우기
→ 물통에 남은 물을 다른 물통에다 붓기
→ 물통의 물을 다른 물통이 가득 찰 때까지 붓기 - 물통 문제 풀이
→ 3리터 물통에 물 가득 채우기 → 3리터 물을 4리터 물통에 모두 붓기
→ 비어 있는 3리터 물통에 다시 물을 가득 채우기 → 3리터 물을 4리터 물 통이 가득 찰 때까지 붓기 → 4리터 물통에 물을 모두 비우기
→ 3리터 물통 안의 물을 4리터 물통에 모두 붓기
다. 늑대, 염소, 양배추 문제
- 사람이 늑대, 염소, 양배추와 강의 오른쪽에 있음 - 사람은 이 중 하나만 선택, 강의 왼쪽/오른쪽으로 이동 - 사람 혼자서 건널 수 있음
- 늑대와 염소만 남겨 두면 늑대가 염소를 잡아먹음 - 염소와 양배추만 남겨 두면 염소가 양배추를 먹음
→ 염소를 내려놓고 오른쪽 이동 → 늑대를 태우고 왼쪽으로 이동
→ 늑대를 내려놓고, 염소를 태우고 오른쪽으로 이동 → 염소를 내려놓고, 양배추를 태우고 왼쪽으로 이동 → 양배추를 내려놓고 혼자서 오른쪽으로 이동 → 염소를 태우고 왼쪽으로 이동
학습정리
1. 인공지능과 알고리즘 - 알고리즘이란
→ 문제 해결을 위한 단계들을 체계적으로 명시하는 것 → 문제를 해결하는 방법의 상세한 특징을 기술하는 것 → 기초적인 수학 연산 / 라면 조리법 / 일정 계획 등 - 휴리스틱 알고리즘
→ 비슷한 문제에 대한 과거의 경험을 바탕으로 직관적으로 판단하여 선택하는 의사결정 방식
- 인공지능 A* 알고리즘
→ 목표 지점을 가장 비용이 적거나 짧은 경로로 찾아나가는 것 2. 인공지능과 관련된 흥미로운 문제들
- 상자 쌓기 문제 평가하기
1. 다음 중 알고리즘에 대한 설명으로 보기 어려운 것은?
① 나무는 식물이다 라고 표현하는 것
② 문제 해결을 위한 단계들을 체계적으로 명시하는 것
③ 문제 해결 방법의 상세 특징을 기술하는 것
④ 표현방법 : 순서도, 언어적 표현 등 - 정답 : ①번
해설 : 나무는 식물이다 로 표현하는 것은 단순히 나무에 대한 정의를 알려주는 것으로 문제를 해결하는 과정으로 보기 어려움
2. 다음 중 규칙을 이용한 인공지능 기법을 통한 적절한 문제가 아닌 것은?
① 물통 문제
② 복잡한 곱셈 문제
③ 상자 쌓기 문제
④ 8-Queens 문제 - 정답 : ②번
해설 : 복잡한 곱셈 문제는 사칙연산의 규칙을 이용하여 해결하는 것은 맞으나 인공지능 기법을 통한 문제로 볼 수 없음
→ 규칙의 적용을 이용한 문제 해결
다음 주 예고
“7. AI 프레임워크” 에 대해 학습하겠습니다.
