[방송통신대학교]인공지능 - 중간과제물 공통형

1.

< 균일 비용 검색 알고리즘 >

균일 비용 검색 알고리즘은 그래프나 트리에서 최적의 경로를 찾기 위해 인공지능 분야에서 사용되는 인기 있는 알고리즘입니다.

 

균일 비용 검색 알고리즘의 목표는 그래프에서 시작 노드에서 목표 노드까지 가능한 모든 경로를 검색하는 동시에 각 경로와 관련된 비용을 고려하는 것입니다.

 

균일 비용 검색 알고리즘은 총 비용이 가장 낮은 경로를 검색하는 원리를 기반으로 합니다.

 

균일 비용 검색 알고리즘은 각 노드의 비용을 고려하면서 루트 노드에서 시작하여 다음 레벨로 이동하는 광범위한 우선 방식으로 노드를 확장합니다.

 

< 언덕오르기 탐색 알고리즘 >

언덕오르기 탐색 알고리즘은 문제에 대한 최적의 솔루션을 찾는 데 사용되는 로컬 검색 알고리즘입니다.

 

언덕오르기 탐색 알고리즘의 목표는 초기 상태에서 시작하여 가능한 솔루션을 검색하고 가장 높은 값을 가진 상태로 이동하는 것입니다.

 

언덕오르기 탐색 알고리즘은 "탐욕스러운 베스트-퍼스트"의 원칙에 기반을 두고 있으며, 이는 현재 상태에서 목표 상태까지의 비용을 추정하는 휴리스틱 함수를 기반으로 다음 상태를 선택한다는 것을 의미합니다.

 

언덕오르기 탐색 알고리즘은 검색 공간이 매우 크고 최적의 솔루션을 찾는 데 계산 비용이 많이 들 때 유용합니다.

 

< A* 알고리즘 >

A* 알고리즘은 AI에서 널리 사용되는 알고리즘으로 균일 비용 검색과 탐욕스러운 베스트-퍼스트 검색 알고리즘이 결합된 것입니다.

 

A* 알고리즘은 경로의 총 비용과 현재 노드와 목표 노드 사이의 거리를 추정하는 휴리스틱 함수를 고려하여 그래프 또는 트리에서 최적 경로를 찾는 데 사용됩니다.

 

A* 알고리즘은 시작 노드에서 현재 노드까지의 실제 비용과 현재 노드에서 목표 노드까지의 예상 비용을 모두 사용하여 확장할 다음 노드를 결정합니다.

 

A* 알고리즘은 휴리스틱 함수가 특정 조건을 만족하는 한 최적의 솔루션을 찾는 것이 보장됩니다.

 

< 각 알고리즘 비교 >

균일비용 탐색 알고리즘은 정보가 없는 검색 알고리즘입니다.

이 알고리즘은 문제 공간에 대한 사전 지식이 없으며, 각 경로의 비용이 최적의 솔루션을 찾는 유일한 요소일 때 유용합니다. 하지만 검색 공간이 크고 최적의 솔루션이 시작 노드에서 멀리 떨어져 있을 때는 속도가 느릴 수 있습니다.

 

따라서 이 알고리즘이 유용한 경우에는 비용이 최적의 솔루션을 찾는 데 유일한 요소이며, 검색 공간이 작은 경우입니다.

 

언덕오르기 탐색 알고리즘은 로컬 검색 알고리즘으로, 현재 상태의 바로 근처에서 최적의 솔루션을 찾는 것에만 관심이 있습니다. 이것은 검색 공간이 매우 크고 전역 최적을 찾는 것이 계산 비용이 많이 들 때 유용합니다. 그러나 언덕오르기 탐색 알고리즘은 로컬 최적화에 갇힐 수 있으며, 이는 글로벌 최적화를 찾지 못할 수 있음을 의미합니다.

 

따라서 이 알고리즘이 유용한 경우에는 전역 최적화를 찾는 것이 불가능하거나 계산 비용이 많이 드는 경우입니다.

 

A* 알고리즘은 균일비용 탐색 알고리즘 알고리즘과 언덕오르기 탐색 알고리즘 알고리즘이 결합된 것입니다. 이 알고리즘은 검색 공간이 넓을 때 유용하며, 각 경로의 비용과 목표 노드까지의 거리가 모두 중요한 요소입니다. A* 알고리즘은 최적의 솔루션을 찾는 것이 보장되며 일반적으로 균일비용 탐색 알고리즘 알고리즘보다 빠릅니다. 그러나 휴리스틱 함수가 허용되지 않거나 일관되지 않으면 A* 알고리즘이 항상 최적의 솔루션을 찾지 못할 수 있습니다.

 

따라서 이 알고리즘이 유용한 경우에는 검색 공간이 크며, 각 경로의 비용과 목표 노드까지의 거리가 모두 중요한 요소입니다.

 

알고리즘의 선택은 특정 문제와 검색 공간의 특성에 따라 달라집니다. 균일비용 탐색 알고리즘은 각 경로의 비용이 최적의 솔루션을 찾는 유일한 요소일 때 유용합니다. 언덕오르기 탐색 알고리즘은 검색 공간이 매우 크고 전역 최적을 찾는 데 계산 비용이 많이 들 때 유용합니다.

 

마지막으로 A* 알고리즘은 검색 공간이 클 때 유용하며, 각 경로의 비용과 목표 노드까지의 거리가 모두 중요한 요소입니다.

2. 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)

초기상태 (cost=5, h=6): f(n) = 5 + 6 = 11

1	5	2
	4	3
7	8	6

|(확장)

v

(cost=6, h=5): f(n) = 6 + 5 = 11

1		2
5	4	3
7	8	6

|(확장)

v

(cost=7, h=4): f(n) = 7 + 4 = 11

1	4	2
	5	3
7	8	6

|(확장)

v

(cost=8, h=3): f(n) = 8 + 3 = 11

1	4	2
7	5	3
	8	6

|(확장)

v

(cost=9, h=2): f(n) = 9 + 2 = 11

1	4	2
7		3
5	8	6

|(확장)

v

(cost=10, h=1): f(n) = 10 + 1 = 11

1		2
7	4	3
5	8	6

|(확장)

v

(cost=11, h=0): f(n) = 11 + 0 = 11

1	2	3
7	4	5
	8	6

|(확장)

v

(cost=12, h=1): f(n) = 12 + 1 = 13

1	2	3
7	4	5
8		6

|(확장)

v

(cost=13, h=2): f(n) = 13 + 2 = 15

1	2	3
7	4	5
8	6

| (확장)

v

목표 상태 (cost=0, h=0): f(n) = 0 + 0 = 0

1	2	3
4	5	6
7	8