Cs50 인공지능 교실 체험 제2부분 인공지능 테마 검색

전날 나는 상태 공간, 에이전트, 동작, 상태 등 검색의 기본 구성 요소에 대해 토론했다. 현재 나는 교과서에서 서로 다른 검색 알고리즘을 배운 경험을 이야기하고 있다.
검색의 문제는 미궁 경로를 사용하여 검색하는 것입니다. 예를 들어 미궁에서 경로를 찾으려는 에이전트로 간주할 수 있습니다.

깊이 우선 검색(DFS) 및 폭 우선 검색(BFS):

내가 본 첫 번째 알고리즘은 DFS 또는 깊이 우선 검색이다. 나는 그것을 가장 좋아한다. 왜냐하면 그것은 결과를 깊이 있게 찾을 수 있기 때문이다.그것은 창고 데이터 구조를 이용하여 모든 접근 노드나 경로/결정점을 저장하고 막다른 골목까지 깊이 들어가 이전 점으로 되돌아간다. 거기서 이런 방식으로 시작하여 미궁이 시작점에서 끝점까지의 경로를 찾았다.

#####B#
##### #
####  #
#### ##
     ##
A######

이것은 예시적인 미궁이다. 우리는 다음과 같은 경로를 얻었다

검은색은 벽, 녹색은 끝, 빨간색은 프록시, 노란색 블록은 프록시의 검색 경로입니다.
이것은 내가 그것을 더욱 복잡하게 만들면 간단한 미궁이다.

###                 #########
#   ###################   # #
# ####                # # # #
# ################### # # # #
#                     # # # #
##################### # # # #
#   ##                # # # #
# # ## ### ## ######### # # #
# #    #   ##B#         # # #
# # ## ################ # # #
### ##             #### # # #
### ############## ## # # # #
###             ##    # # # #
###### ######## ####### # # #
###### ####             #   #
A      ######################

이제 DFS를 사용하여 탐색하는 에이전트의 경로로 보이는 빨간색 네모난 블록이 있고 이전 지점으로 돌아갑니다.

현재 경로 비용이라는 개념이 있는데, 194보다 약간 높지만, 만약 우리가 BFS나 광도 우선 검색을 응용한다면, 우리는 그것을 가장 잘 실현할 수 있다.여기서 DFS는 끝날 때까지 깊이 들어가지만 bfs는 깊이 들어가고 경로를 검색합니다.
당신은 DFS를 훈련으로 비교할 수 있습니다. BFS는 문어입니다. 이 문어는 촉수를 사용하여 더 많은 구역을 덮어주고 상술한 미로 BFS에 사용하는 것이 가장 좋은 선택입니다.

현재 이 문제는 비교적 낮은 원가로 해결되고 있다. 예를 들어 전체 경로 원가의 77과 같이 이것은 더욱 최적화된 것이다.그러나 때로는 bfs가 부족하다.
나는 비디오 bfs와 dfs가 어떻게 작동하는지 틀어 놓았다.

 Dfs working

Bfs working

현재 우리는 더욱 최적화하기 위해 인공지능 검색 중의 두 가지 검색 유형을 이해할 것이다.

알기 검색: 그곳에서 우리는 환경에 대한 정보를 가지고 있으며, 우리는 그것을 사용하여 문제를 더욱 최적화시킬 수 있다.

예: 미궁 문제는 만약에 우리가 목표점 좌표와 원점 좌표를 가지고 있다면 그것들을 비교하여 그것들 사이의 거리를 얻을 수 있다. 그러면 우리는 우리가 원천에서 얼마나 멀리 떨어져 있는지 알 수 있다.

정보 검색 없음: 이것은 검색일 뿐, 에이전트는 환경에 대한 정보가 없습니다.그것은 단지 목표를 달성하기 위해서일 뿐, 때로는 우리가 정보가 없는 상황에서 유용하다.이전에 bfs와 dfs는 정보를 제공하지 않은 검색 예시였다.

탐욕스러운 우선 순위 검색:

알 수 있는 검색에 대해 우리는 가장 좋은 우선 순위 검색이나 GBFS를 탐욕스럽게 여긴다. 그 중에서 우리는 계발식 함수 h(n)로 확정된 프록시 위치와 목표 경로의 거리를 얻어 미로 속의 경로를 검색한다.말 그대로 이 함수는 다음 노드가 목표와 얼마나 가까운지 추정하지만 오류가 발생할 수 있다.탐욕의 최우선 우선 알고리즘의 효율은 계발식 함수의 좋고 나쁨에 달려 있다.예를 들어 미궁에서 알고리즘은 계발식 함수를 사용할 수 있는데 이 함수는 가능한 노드와 미궁 말단 사이의 맨해튼 거리에 의존한다.맨해튼의 거리는 벽을 무시하고 한 위치에서 목표 위치까지 필요한 상하 또는 측면의 걸음 수를 계산했다.이것은 간단한 평가로 현재 위치와 목표 위치의 (x, y) 좌표에 따라 유도할 수 있다.
다음과 같은 방법으로 단순화할 수 있습니다.f(n) = h(n)다음은 응용/단점이 있습니다.

최악의 경우 비 가이드 깊이 우선 검색으로 사용할 수 있다.

DFS처럼 루프에 연결될 수 있습니다.

이 알고리즘은 가장 좋은 것이 아니다.

A* 검색

따라서 비가이드 경로 문제를 해결하기 위해 나는 같은 계발식 함수와 평가 함수를 사용하는 또 다른 경로 문제를 배웠다.
이것은 검색 알고리즘이라고 한다.
이것은 원본에서 목표까지의 h(n) 거리와 g(n) 평가 함수를 사용하여 사용하는 경로의 원가를 얻는다.
현재 위치에 있기 전에 그는 줄곧 원가를 누적하고 있다.이 두 값을 결합하면 이 알고리즘은 해결 방안의 원가를 더욱 정확하게 확정하고 운행 중에 그 선택을 최적화할 수 있다.이 알고리즘은 (지금까지의 경로 원가 + 목표의 추정 원가) 를 추적하고 이전의 특정한 옵션의 추정 원가를 초과하면 이 알고리즘은 현재의 경로를 버리고 이전의 옵션으로 돌아가 h(n) 오류를 따라 가장 길고 저효율적인 경로로 표시하는 것을 방지한다.
마찬가지로 이 알고리즘도 계발식에 의존하기 때문에 사용하는 계발식과 마찬가지로 좋다.어떤 경우, 그 효율은 탐욕의 가장 좋은 우선 검색보다 낮을 수도 있고, 심지어는 정보를 제공하지 않은 알고리즘보다 낮을 수도 있다.* 검색이 가장 우수하도록 계발식 함수 h(n)는 다음과 같아야 합니다.
실제 비용을 과소평가하거나
일치성, 이것은 이전 노드에서 새 노드로 이행하는 비용을 제외하고 새 노드 목표로의 추정 경로 원가가 이전 노드 목표의 추정 경로 원가보다 크거나 같다는 것을 의미한다.이를 방정식 형식으로 전환한다. 만약에 각 노드 n과 후속 노드 n에 대해 단계 원가가 c, h(n)이면 h(n)는 일치한다≤ h(n’)+c.
검색의 시각화.
나는 이 부분을 여기에 두었다. 다음 부분은 곧 올 것이다.
끊임없이 탐색하고, 끊임없이 공부하다.

참조:

https://cs50.harvard.edu/ai/2020/

https://www.javatpoint.com/ai-informed-search-algorithms

정말 감사합니다.