빨간당무 마을

- Constraint Satisfaction Problem (CSP; 제약 만족 문제) - 사람이 수행하는 systematic적인 search를 효과적으로 할 수 있도록 하며 검색 공간을 줄여주는 방법임 - 문제를 해결하는 제약조건을 이용하여 결과를 검사하고 결과를 만들어 낼 때도 사용됨 - 체계적으로 optimal한 값을 찾으며, trace를 원할 때에는 CSP가 유리함 - 어떤 문제에 대해 제약조건만을 바꿔주면 문제를 해결할 수 있음 (독립적) - 탐색 중 제약조건을 하나라도 어긋나면 탐색을 중지하는 예측적 성향도 있음 - Best First Search (BFS; 최적 우선 탐색) - Stochastic적인 search를 하는 방법임 - Heuristic search의 한 종류로 얼마나 효과적인 ..

- Best first search - 휴리스틱에 따라 목표까지 가장 좋은 경로 상에 있다고 판단되는 노드를 우선 방문하도록 진행 Evaluation Function에 따라 다음에 확장 할 노드를 선택 (같은 값이면 무작위 선택) 다음에 확장할 노드가 Goal이면, 탐색 종료 - 한 노드로 부터 목표 노드까지 도달하기 위한 비용을 평가 함수로 함 출발노드에서 시작하여 목표노드까지 도달하는 최적의 경로를 탐색하는 것은 보장 되지 않음 - 방안 : A* algorithm - A* algorithm - 출발 노드부터 목표 노드까지의 최적경로를 탐색 - f(n) = g(n) + h(n) -> 출발 노드에서 시작하여 노드 n을 거쳐서 목표 노드까지 도달하는 비용 g(n) : 출발 노드로 부터 노드 n까지의 경로비..