Problem-Solving Agents 1. 어떤 Agent든 "Sensor"를 통해서 인식하는 정보들이 존재할 것이다 :: Percept 2. Percept 정보와 State(직전 상태) 정보를 결합(Update-State)함으로써 새로운 State를 정의한다 ※ Sequence(Sequence Of Action)가 없다면? Sequence가 없다는 의미는 현재 "계획"이 없다는 의미이다 >> 따라서 계획을 먼저 수립해야 한다 1) 현재 State로부터 먼저 Goal을 정한다 Goal은 1) Agent가 스스로 정할 수 있고, 2) 외부에서 Agent에게 정해줄 수 있다 2) 현재 State & Goal을 통해서 Problem을 formulate한다 (탐색 대상이 될 수 있는 Problem으로 만들기..

BFS(stack) VS DFS(queue) BFS : 깊이 우선 탐색 - stack or 순환으로 구현 DFS : 너비 우선 탐색 - queue로 구현 #include #include // 인접 리스트(BFS - 스택 / DFS - 큐) #define MAX_VERTEX 50 #define TRUE 1 #define FALSE 0 typedef int element; // 그래프 구현 typedef struct graphnode { int vertex; struct graphnode* link; }graphnode; typedef struct graph { int n; graphnode* list[MAX_VERTEX]; }graph; int visited[MAX_VERTEX]; void init_vis..

BFS(stack) VS DFS(queue) BFS : 깊이 우선 탐색 - stack or 순환으로 구현 DFS : 너비 우선 탐색 - queue로 구현 #include #include // 인접 행렬 (BFS-스택 / DFS-큐) #define MAX_VERTEX 50 #define TRUE 1 #define FALSE 0 typedef int element; typedef struct graph { int n; // 정점 개수 int vertex[MAX_VERTEX]; // 정점 저장 배열 int matrix[MAX_VERTEX][MAX_VERTEX]; }graph; int visited[MAX_VERTEX]; void init_visited(int arr[]) { for (int i = 0; i <..

BFS - 너비 우선 탐색 - 원형큐로 구현 - 인접 행렬 : O(n²) (정점 n개) - 인접 리스트 : O(n+e) (정점 n개, 간선 e개) 시작 정점으로부터 거리가 d인 정점들을 모두 방문 (d=1) 그 다음에 거리가 d+1인 정점들을 모두 방문 d+2 / d+3,.... 정점들을 차례대로 방문 거리가 0인 시작 정점(v)을 방문 v로부터 거리가 1인 정점 모두 방문 v로부터 거리가 2인 정점 모두 방문 마지막 정점 방문할 때 까지.,.... 인접 행렬로 구현한 BFS Queue : bfs_mat_queue(graph* g, int v) 큐 생성 v 방문완료 표시 v를 큐에 enqueue 큐에서 dequeue (정점 v dequeue) -- (1) dequeue된 정점 v의 인접 정점(w)들을 방..

그래프 탐색 방법 DFS (Depth First Search) : 깊이 우선 탐색 BFS (Breath First Search) : 너비 우선 탐색 DFS ≒ 전위/중위/후위 순회 BFS ≒ 레벨 순회 DFS (Depth First Search) - 깊이 우선 탐색 - 한 방향으로 끝까지 진행 - 더 이상 갈 곳이 없으면, 가장 가까운 곳으로 다시 되돌아가서(backtracking) 해당 지점에서부터 다시 탐색을 시작 ▶ 구현 방법 1. 인접 행렬 2. 인접 리스트 순환 호출 사용 stack 사용 : 인접 정점들을 stack에 저장했다가 꺼내서 다시 탐색 BFS (Breath First Search) - 너비 우선 탐색 - 현재 정점으로부터 가장 가까운 노드를 먼저 방문 - 멀리 떨어져 있는 정점은 나중..