[인공지능] 인공지능 탐색에 대한 나의 고찰

1) 주변에서 찾을 수 있는 실생활 탐색 문제가 무엇이 있을까?

1. 식료품 쇼핑: 최적의 식료품 쇼핑 경로를 찾는 문제. 소비자는 다양한 제품을 최저 가격에 구매하기 위해 여러 매장의 위치와 가격을 비교해야 합니다.

다양한 제품을 구매하기 위한 가격비교 하는 소비자

2. 식사 준비: 냉장고와 식료품 창고에 있는 재료를 바탕으로 식사 메뉴를 결정하고, 필요한 재료를 최소한으로 구입하는 경로를 탐색합니다.

3. 의복 구매: 패션에 관심이 있는 소비자는 최신 트렌드에 맞는 옷을 찾거나 특정 품목을 최고의 가격에 구매하기 위해 다양한 매장과 온라인 쇼핑몰을 탐색합니다.

4. 집 구하기: 적절한 가격, 위치, 크기의 주택을 찾기 위해 부동산 목록을 탐색하고, 각각의 조건에 맞는 최적의 선택을 결정해야 합니다.

5. 출퇴근 경로: 교통 상황에 따라 최소 시간으로 출퇴근할 수 있는 경로를 찾는 문제로, 다양한 교통 수단과 경로를 고려해야 합니다.

최소 시간으로 출퇴근할 수 있는 경로를 찾으려는 사람

6. 의료 서비스 접근: 필요한 의료 서비스를 제공하는 병원이나 클리닉을 찾고, 예약 가능한 시간과 가까운 거리를 고려해야 합니다.

7. 교육 기관 선택: 자녀에게 적합한 학교를 찾기 위해 학교의 위치, 명성, 교육 프로그램 등을 탐색해야 합니다.

8. 여행 계획: 여행지를 선택하고, 숙박 시설, 식당, 관광지 등을 탐색하여 경로를 계획하는 문제입니다.

9. 가구 배치: 제한된 공간 내에서 가구를 효율적으로 배치하여 최대의 사용 편의성을 달성하는 방법을 탐색합니다.

10. 요리 레시피 탐색: 특정 요리를 위한 레시피를 찾고, 해당 요리법이 요구하는 재료와 조리 방법을 이해하는 과정입니다.

 

2) 탐색 알고리즘은 어떤 것이 있는가?

 

탐색알고리즘에는 크게 2가지로 구분이 된다.

맹목적 탐색(Uninformed search)과 정보이용 탐색 (informed search)으로 구분이 되는데,

 

맹목적 탐색(Uninformed search)은

정해진 순서에 따라 상태 공간 그래프를 탐색하는 방법으로 해를 찾는다

현재 상태에서 목표 상태까지의 노드의 개수를 알지 못하고 해를 찾아 나가는 탐색 방법이다.

 

정보이용 탐색 (informed search)

State space가 매우 커질 경우 → uninformed search가 효과적이지 않음 (메모리, 시간 비효율)

상태 공간의 정보를 이용하여 모든 노드를 탐색하지 않고 해를 찾는 방법이다.

 

맹목적 탐색(Uninformed search)의 알고리즘에는

• 깊이 우선 탐색(depth-first search, DFS)

• 너비 우선 탐색(breath-first search, BFS)

• 깊이 제한 탐색 (depth-limited search)

• 점차적 깊이제한 탐색 (iterative deepening search)

• 일정량 탐색 (uniform-cost search)

• 양방향 탐색 (bidirectional search)

 

정보이용 탐색 (informed search)의 알고리즘에는

탐색 공간에서의 해 (solution) 찾을 때 Global maximum과 Local maximum을 찾을 수 있다.

 

Local maximu을 찾는 알고리즘

• 언덕 오르기 방법(hill climbing method)

• Simulated annealing

• Local beam search

• Genetic algorithms

• Best-first search

 

Global maximu을 찾을 수 있는 알고리즘

• A* search

 

3) 왜 다양한 탐색 알고리즘이 존재하는가?

다양한 탐색 알고리즘이 존재하는 이유는 문제의 특성과 요구 사항이 서로 다르기 때문입니다.

예를 들어, 어떤 문제는 탐색 공간이 매우 넓어 깊이 우선 탐색(DFS)이 적합하지 않을 수 있고, 다른 문제는 최단 경로를 찾는 것이 중요해 너비 우선 탐색(BFS)이나 A* 알고리즘이 더 적합할 수 있습니다.

또한, 문제에 따라 사용할 수 있는 정보의 양과 종류가 달라, 휴리스틱 정보를 사용하는 알고리즘이 필요할 수도 있습니다. 이처럼 각기 다른 문제 상황에 맞춰 가장 효율적인 해결책을 제공하기 위해 다양한 탐색 알고리즘이 개발되고 사용됩니다.

 

4) 탐색 알고리즘이 갖춰야 할 조건은 무엇인가?

1. 완전성(Completeness): 모든 가능한 탐색 공간 내에서 해답을 찾을 수 있는지를 보장해야 합니다. 해답이 존재한다면, 알고리즘은 반드시 그 해답을 찾아낼 수 있어야 합니다.

2. 시간 효율성(Time Efficiency): 알고리즘은 가능한 한 빠르게 해답을 찾아야 합니다. 이는 알고리즘의 실행 시간이 합리적인 범위 내에서 완료될 수 있음을 의미합니다.

3. 공간 효율성(Space Efficiency): 알고리즘은 메모리 사용량을 최소화하여야 합니다. 이는 탐색 과정에서 사용하는 저장 공간이 시스템의 제약 사항을 초과하지 않도록 함을 의미합니다.

4. 최적성(Optimality): 가능하다면, 알고리즘은 최적의 해답을 찾아야 합니다. 즉, 목표를 달성하기 위한 최소 비용이나 최단 경로와 같은 최적의 결과를 제공해야 합니다.

5. 적용 가능성(Applicability): 알고리즘은 다양한 문제에 적용 가능해야 합니다. 즉, 범용성을 갖추어 다양한 상황과 조건에서 사용될 수 있어야 합니다.

 

5) 정보가 있는 탐색과 정보가 없는 탐색의 차이는 무엇인가? 각각에 대하여 하나의 예제를 찾아서 탐색 문제 정의에 차이가 무엇인지 알아보자. 

 

정보가 없는 탐색(Uninformed Search): 이 방법은 문제의 구조나 목표에 대한 특별한 지식 없이 탐색을 수행합니다.

대표적으로 브레드-퍼스트 탐색(Breadth-First Search, BFS)이 있으며, 이는 모든 노드를 균등하게 탐색하여 해답을 찾습니다. 예를 들어, 미로 찾기 문제에서 출발점에서 시작하여 가능한 모든 경로를 동일한 순서로 탐색하여 출구를 찾는 경우입니다. 

 

정보가 있는 탐색(Informed Search): 이 방법은 목표에 도달하기 위한 경로를 찾는 데 도움이 되는 추가 정보나 휴리스틱을 사용합니다. A* 탐색 알고리즘은 대표적인 예로, 각 단계에서 목표까지의 예상 거리를 고려하여 탐색을 진행합니다. 예를 들어, 도시 간 최단 경로를 찾는 문제에서, 각 도시 사이의 실제 거리와 목표 도시까지의 직선 거리(휴리스틱)를 사용하여 탐색을 가이드합니다.

 

정보가 있는 탐색과 정보가 없는 탐색의 차이는, 정보가 있는 탐색이 목표 달성을 위해 추가적인 지식이나 휴리스틱을 사용하여 탐색 과정을 가이드한다는 점입니다. 반면, 정보가 없는 탐색은 이러한 추가 정보 없이 탐색 공간을 규칙대로 탐색합니다.

 

6) A* 알고리즘의 사용 예제 찾기/ 적용된 heuristic 함수는 무엇인가?

 

사용 예제: 경로 찾기(Pathfinding) 문제, 특히 지도 상에서 한 지점에서 다른 지점으로 가는 최단 경로를 찾는 문제에서 A* 알고리즘이 널리 사용됩니다. 예를 들어, GPS 내비게이션 시스템은 사용자의 현재 위치에서 목적지까지의 최단 경로를 계산하기 위해 A* 알고리즘을 사용할 수 있습니다.

 

적용된 휴리스틱 함수: 유클리드 거리(혹은 맨해튼 거리) GPS 경로 찾기 문제에서 휴리스틱 함수로 종종 사용되는 것은 유클리드 거리입니다. 이는 현재 노드에서 목표 노드까지의 직선 거리를 나타내며, 실제 이동할 때 발생할 수 있는 모든 장애물이나 도로의 구불구불함을 고려하지 않고 계산합니다.

 

7) 8-puzzle 문제의 heuristic function을 정의해 보자

 

휴리스틱 함수: 맨해튼 거리 8-puzzle 문제에서 가장 널리 쓰이는 휴리스틱 함수는 맨해튼 거리입니다. 맨해튼 거리는 각 타일이 목표 위치까지 이동하기 위해 필요한 최소 수평 및 수직 이동 횟수의 총합으로, 이는 각 타일을 목표 위치로 이동시키기 위해 필요한 최소 이동 횟수를 추정합니다.

 

맨해튼 거리 휴리스틱은 8-puzzle 문제에서 admissible하다고 간주됩니다. 이는 맨해튼 거리가 실제 해결까지 필요한 이동 횟수를 절대 과대 평가하지 않기 때문입니다. 다른 타일들의 위치 때문에 실제로는 더 많은 이동이 필요할 수 있지만, 맨해튼 거리는 이러한 상황을 고려하지 않고 각 타일을 직선으로 목표 위치까지 이동시킬 수 있다고 가정합니다. 따라서, 이 휴리스틱은 최적 경로의 길이를 결코 과대 평가하지 않으므로 A* 탐색에서 최적 해를 보장합니다.