인공 지능의 정보에 입각한 검색에 관한 모든 것

정보 검색은 도메인별 지식을 사용하여 문제 공간을 통해 검색을 안내하는 검색 알고리즘 유형입니다. 내비게이션 시스템에서 게임 플레이, 자연어 처리, 공급망 관리 및 인공 지능의 보다 정보에 입각한 검색에 이르기까지 다양한 문제를 해결하는 데 필요한 시간과 컴퓨팅 리소스가 크게 줄었습니다.

도메인별 지식을 사용하여 검색을 안내함으로써 정보에 입각한 검색 알고리즘은 관련이 없거나 덜 유망한 경로를 신속하게 제거하여 검색이 가장 유망한 옵션에 집중할 수 있도록 합니다. 이를 위해 AI의 이러한 유형의 검색 알고리즘은 휴리스틱을 사용하여 검색의 효율성과 속도를 향상시킵니다.

세계 최고의 대학에서 제공하는 기계 학습 과정 에 등록하십시오 . Master, Executive PGP 또는 Advanced Certificate Program을 취득하여 경력을 빠르게 쌓으십시오.

이 기사에서는 인공 지능의 정보 ​​검색 개념 , 휴리스틱 기능, 알고리즘의 예, 장단점에 대해 설명합니다.

휴리스틱스 기능

간단히 말해서 휴리스틱 함수는 검색 문제에서 목표 상태까지의 거리 또는 비용을 추정하기 위해 경험 법칙 또는 "최선의 추측"을 사용하는 문제 해결 방식입니다. 휴리스틱 함수는 목표 상태가 현재 상태에서 얼마나 떨어져 있는지 추정하여 목표를 향한 검색 알고리즘을 안내하는 데 사용할 수 있습니다.

정보 검색 알고리즘은 이러한 기능을 추가 정보 소스로 사용하여 어떤 경로를 선택할지 정보에 입각한 결정을 내립니다. 이러한 이유로 휴리스틱 기능은 정보 검색 알고리즘에서 필수적입니다.

휴리스틱스 함수의 실제 사례

휴리스틱 기능을 더 잘 이해하기 위해 다음은 몇 가지 실제 사례입니다.

• 고전적인 "슬라이딩 타일 퍼즐" 게임에서 간단한 경험적 기능은 목표 구성과 비교하여 현재 구성에서 제자리에 있지 않은 타일 수를 계산하는 것일 수 있습니다. 더 많은 타일이 제자리에 없을수록 현재 상태가 목표 상태에서 멀어집니다.
• 체스에서 휴리스틱 기능은 상대 강도와 위치에 따라 보드의 각 조각에 값을 할당하고 해당 값의 합계를 사용하여 현재 플레이어의 장점 또는 단점을 추정하는 것일 수 있습니다. 이 휴리스틱 기능을 사용하여 검색 알고리즘을 더 나은 위치에 도달할 가능성이 있는 이동 방향으로 안내할 수 있습니다.

이 문제가 해결되면 이제 계속 진행하여 인공 지능에서 정보에 입각한 검색 알고리즘의 가장 많이 사용되는 몇 가지 예를 이해해 봅시다.

정보에 입각한 검색 알고리즘의 예

가장 일반적으로 사용되는 두 가지 정보 검색 알고리즘에는 최상의 우선 검색과 A* 검색이 있습니다. 몇 가지 예, 장점, 단점 및 Python 구현과 함께 이 두 알고리즘을 이해해 봅시다.

1. 베스트 퍼스트 서치

베스트 퍼스트 서치는 휴리스틱(heuristic) 함수에 따라 가장 유망한 노드를 먼저 확장하는 서치 알고리즘이다. 알고리즘은 초기 노드에서 시작하여 탐색할 다음 노드로 휴리스틱 값이 가장 낮은 자식을 선택하여 모든 자식 노드를 검사합니다. 이 프로세스는 목표 노드를 찾거나 모든 노드를 탐색할 때까지 계속됩니다.

최고의 첫 번째 검색 – 삽화가 있는 예

다음은 최상의 첫 번째 검색을 설명하는 간단한 예입니다.

집에서 가까운 식료품점까지의 최단 경로를 찾으려고 한다고 가정합니다. 근처의 몇몇 위치에서 식료품점까지의 거리를 알고 있지만 정확한 경로는 알지 못합니다. 최선 우선 검색을 사용하여 이 문제를 해결하려면 다음을 수행할 수 있습니다.

1. 집 위치에서 시작하여 식료품점까지의 거리를 기준으로 인근 각 위치의 휴리스틱 값을 계산합니다.
2. 휴리스틱 값이 가장 낮은 인근 위치를 탐색할 다음 노드로 선택합니다.
3. 가까운 위치에서 각 하위 위치에 대한 휴리스틱 값을 계산하고 탐색할 다음 노드로 휴리스틱 값이 가장 낮은 위치를 선택합니다.
4. 식료품점에 도착할 때까지 이 과정을 반복합니다.

최고의 첫 번째 검색 – Python 구현

Python에서 최고의 첫 번째 검색 알고리즘을 구현하는 방법은 다음과 같습니다.

힙 가져오기

def best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# 프론티어 및 탐색 세트 초기화

프론티어 = [(heuristic_func(시작_상태, 목표_상태), 시작_상태)]

탐색 = 세트()

# 경로와 비용 초기화

경로 = {}

비용 = {}

경로[시작_상태] = 없음

비용[시작_상태] = 0

동안 국경:

# 프론티어에서 휴리스틱 값이 가장 낮은 노드를 가져옵니다.

(h, current_state) = heapq.heappop(프론티어)

현재_상태 == 목표_상태인 경우:

# 목표 상태에 도달하면 경로를 반환

복귀 경로

탐색됨.추가(현재_상태)

# 현재 상태에서 가능한 작업 생성

actions_func(current_state)의 작업:

next_state = 동작(현재_상태)

# 새 경로의 비용을 계산합니다.

new_cost = 비용[현재_상태] + cost_func(현재_상태, 작업, 다음_상태)

next_state가 탐색되지 않고 next_state가 [프론티어의 (h, state)에 대한 상태]에 없는 경우:

# 프론티어에 새 주를 추가합니다.

heapq.heappush(프론티어, (heuristic_func(다음_상태, 목표_상태), 다음_상태))

경로[다음_상태] = 현재_상태

비용[다음_상태] = 새_비용

# 목표 상태에 도달할 수 없으면 None을 반환합니다.

반환 없음

보다시피 다음 함수를 정의해야 합니다.

• heuristic_func(current_state, goal_state): 이 함수는 현재 상태와 목표 상태를 입력으로 사용하고 현재 상태에서 목표 상태에 도달하는 비용의 추정치를 반환합니다.
• actions_func(current_state): 이 함수는 현재 상태를 입력으로 받아 현재 상태에서 취할 수 있는 조치 목록을 반환합니다.
• cost_func(current_state, action, next_state): 이 함수는 현재 state, action, next state를 입력으로 받아 현재 state에서 다음 state까지 action을 취하는 비용을 반환합니다.

최상의 우선 검색의 예

시작_상태 = (0, 0)

목표_상태 = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(현재_상태[0] – 목표상태[0]) + abs(현재상태[1] – 목표상태[1])

def actions_func(current_state):

행동 = []

current_state[0] > 0인 경우:

actions.append(람다 상태: (상태[0]-1, 상태[1]))

current_state[0] < 4인 경우:

actions.append(람다 상태: (상태[0]+1, 상태[1]))

current_state[1] > 0인 경우:

actions.append(람다 상태: (상태[0], 상태[1]-1))

current_state[1] < 4인 경우:

actions.append(람다 상태: (상태[0], 상태[1]+1))

반품 조치

def cost_func(current_state, action, next_state):

반환 1

경로 = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

만약 경로:

# 시작 상태에서 목표 상태까지의 경로를 구성합니다.

현재_상태 = 목표_상태

current_state != 시작_상태 동안:

인쇄(현재_상태)

current_state = 경로[현재_상태]

인쇄(시작_상태)

또 다른:

print("목표 상태에 도달할 수 없습니다.")

베스트 퍼스트 서치의 장점

• 너비우선탐색에 비해 최량우선탐색의 시간복잡도는 낮다.
• 최상의 첫 번째 검색은 BFS 및 DFS 알고리즘의 장점을 모두 얻고 구현합니다.

베스트 퍼스트 서치의 단점

• 때로는 생각보다 더 많은 거리를 커버할 수 있습니다.
• 루프에 갇힐 가능성이 매우 높습니다.

검색

A* 검색은 시작 노드에서 노드에 도달하는 비용과 목표 노드에 도달하는 남은 비용의 추정치를 모두 사용하여 검색을 안내하는 검색 알고리즘입니다. 알고리즘은 초기 노드에서 시작하여 모든 하위 노드를 검사하여 결합 비용과 예상 잔여 비용이 가장 낮은 하위 노드를 탐색할 다음 노드로 선택합니다. 이 프로세스는 목표 노드를 찾거나 모든 노드를 탐색할 때까지 계속됩니다.

A* 검색 – 예시 예시

집에서 가까운 식료품점까지의 최단 경로를 찾으려는 이전 예를 다시 살펴보겠습니다. 이제 다음을 수행할 수 있습니다.

1. 집 위치에서 시작하여 집에서 해당 위치까지의 거리와 해당 위치에서 식료품점에 도달하는 데 드는 남은 예상 비용의 합계로 각 인근 위치에 도달하는 총 비용을 계산합니다.
2. 탐색할 다음 노드로 총 비용이 가장 낮은 인근 위치를 선택합니다.
3. 해당 위치에서 하위 위치까지의 거리, 시작 노드에서 해당 위치에 도달하는 비용 및 식료품점에 도달하는 데 남은 예상 비용의 합으로 각 하위 위치의 총 비용을 계산합니다. 해당 하위 위치에서. 탐색할 다음 노드로 총 비용이 가장 낮은 하위 위치를 선택합니다.
4. 식료품점에 도착할 때까지 이 과정을 반복합니다.

여기서 주목해야 할 중요한 점은 A* 검색이 목표 상태에 대한 최단 경로를 찾는 것을 보장하는 최적의 검색 알고리즘이라는 것입니다. 검색 공간이 큰 문제에 효율적이며 비디오 게임, 로봇 공학 및 경로 계획에 널리 사용됩니다. 그러나 효과적이려면 잘 정의된 휴리스틱 함수가 필요합니다. 이러한 이유로 알고리즘은 메모리를 많이 사용하고 노드가 많은 복잡한 문제에서 속도가 느려질 수 있습니다.

A* 검색 – Python 구현

다음은 Python 프로그래밍을 사용하여 A* 검색 알고리즘을 구현하는 방법입니다.

힙 가져오기

def astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# 프론티어 및 탐색 세트 초기화

프론티어 = [(heuristic_func(시작_상태, 목표_상태), 시작_상태)]

탐색 = 세트()

# 경로와 비용 초기화

경로 = {}

비용 = {}

경로[시작_상태] = 없음

비용[시작_상태] = 0

동안 국경:

# 프론티어에서 f-값이 가장 낮은 노드를 가져옵니다.

(f, current_state) = heapq.heappop(프론티어)

현재_상태 == 목표_상태인 경우:

# 목표 상태에 도달하면 경로를 반환

복귀 경로

탐색됨.추가(현재_상태)

# 현재 상태에서 가능한 작업 생성

actions_func(current_state)의 작업:

next_state = 동작(현재_상태)

# 새 경로의 비용을 계산합니다.

new_cost = 비용[현재_상태] + cost_func(현재_상태, 작업, 다음_상태)

next_state가 탐색되지 않고 next_state가 [프론티어의 (f, state)에 대한 상태]에 없는 경우:

# 프론티어에 새 주를 추가합니다.

heapq.heappush(프론티어, (new_cost + heuristic_func(next_state, goal_state), next_state))

경로[다음_상태] = 현재_상태

비용[다음_상태] = 새_비용

elif next_state in [state for (f, state) in frontier] 및 new_cost < 비용[next_state]:

# 프론티어에 있는 기존 상태의 비용을 업데이트합니다.

인덱스 = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

frontier[인덱스] = (new_cost + heuristic_func(next_state, goal_state), next_state)

경로[다음_상태] = 현재_상태

비용[다음_상태] = 새_비용

# 목표 상태에 도달할 수 없으면 None을 반환합니다.

반환 없음

최고의 기계 학습 과정 및 온라인 AI 과정

A* 검색의 예

다음은 이러한 함수와 함께 astar_search 함수를 사용하는 방법의 예입니다.

시작_상태 = (0, 0)

목표_상태 = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(현재_상태[0] – 목표상태[0]) + abs(현재상태[1] – 목표상태[1])

def actions_func(current_state):

행동 = []

current_state[0] > 0인 경우:

actions.append(람다 상태: (상태[0]-1, 상태[1]))

current_state[0] < 4인 경우:

actions.append(람다 상태: (상태[0]+1, 상태[1]))

current_state[1] > 0인 경우:

actions.append(람다 상태: (상태[0], 상태[1]-1))

current_state[1] < 4인 경우:

actions.append(람다 상태: (상태[0], 상태[1]+1))

반품 조치

def cost_func(current_state, action, next_state):

반환 1

경로 = astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

만약 경로:

# 시작 상태에서 목표 상태까지의 경로를 구성합니다.

현재_상태 = 목표_상태

current_state != 시작_상태 동안:

인쇄(현재_상태)

current_state = 경로[현재_상태]

인쇄(시작_상태)

또 다른:

print("목표 상태에 도달할 수 없습니다.")

A* 검색의 장점

• 대표적인 휴리스틱 기법 중 하나입니다.
• A* 검색을 활용하여 복잡한 검색 문제를 해결할 수 있습니다.

최신 기계 학습 기술

A* 검색의 단점

• A* 검색 성능은 휴리스틱 알고리즘의 정확도에 크게 의존합니다.
• 검색 효율이 낮습니다.

인기 있는 AI 및 ML 블로그 및 무료 과정

테이크 아웃

정보 검색 알고리즘은 컴퓨터가 목표 상태를 효율적이고 효과적으로 검색할 수 있도록 하기 때문에 인공 지능에서 필수적입니다. 이러한 알고리즘은 휴리스틱 기능을 사용하여 가능한 각 이동의 비용을 추정하고 검색 프로세스를 목표 상태로 안내합니다. Best First Search와 A* Search는 다양한 분야에서 널리 사용되는 정보 검색 알고리즘의 예입니다. 그러나 잘 정의된 휴리스틱 함수는 정보 검색 알고리즘의 성공에 매우 중요합니다.

인공 지능 및 기계 학습에 대해 자세히 알아보려면 리버풀 존 무어스 대학교에서 제공하는 upGrad의 기계 학습 및 인공 지능 석사 프로그램을 확인하십시오 . 이 프로그램은 정보 검색과 같은 알고리즘을 포함하여 다양한 기계 학습 및 AI 주제를 다룹니다. 이 프로그램을 수강하면 다양한 AI 관련 경력에서 성공하는 데 필요한 기술과 지식을 얻을 수 있습니다.

관리, 데이터 과학, 기계 학습, 디지털 마케팅 및 기술 분야에서 upGrad가 제공하는무료 과정을확인할 수도 있습니다. 이 모든 과정에는 최고 수준의 학습 리소스, 주간 라이브 강의, 업계 과제 및 과정 수료증이 모두 무료입니다!