*상태 공간 탐색(State Space Search) : 문제 해결 과정에서 상태와 상태 간의 전환을 시각화하고 분석하는 데 유용합니다.
질문에 답하기 위한 주요 도구로 사용됩니다.
문제를 상태 공간 그래프로 표현함으로써, 그래프 이론을 활용하여 문제와 이를 해결하는 절차의 구조와 복잡성을 분석할 수 있습니다.
*상태 공간 탐색 전략
데이터 기반 탐색 (Data-driven search) : 문제의 사실을 바탕으로 규칙과 합법적인 움직임을 적용하여 목표로 이어지는 새로운 사실을 생성합니다
전방 체인 (Forward Chaining): 데이터 기반 탐색은 종종 전방 체인이라고 불립니다.
시작점: 문제 해결자는 문제의 주어진 사실과 상태를 변경할 수 있는 합법적인 움직임이나 규칙의 집합으로 시작합니다.
탐색 과정: 규칙을 적용하여 새로운 사실을 생성하고, 이러한 새로운 사실을 다시 규칙에 사용하여 더 많은 사실을 생성합니다. 이 과정은 목표 조건을 만족하는 경로를 생성할 때까지 계속됩니다.
적합한 상황
문제의 초기 진술에서 모든 데이터 또는 대부분의 데이터가 주어졌을 때.
잠재적인 목표가 많지만, 특정 문제 상황에서 사실과 주어진 정보를 사용할 수 있는 방법이 몇 가지뿐일 때.
목표나 가설을 설정하기 어려울 때 (예: DENDRAL).
탐색 방식
문제의 주어진 데이터에서 발견된 지식과 제약 조건을 사용하여, 참으로 알려진 선을 따라 탐색을 안내합니다.
목표 기반 탐색(Goal-driven search) : 목표에 초점을 맞추고, 목표를 생성할 수 있는 규칙을 찾아서 문제의 주어진 사실로 이어지는 규칙과 하위 목표를 통해 역방향으로 연결합니다.
목표 설정: 해결하려는 목표를 설정합니다.
규칙 확인: 이 목표를 생성할 수 있는 규칙이나 합법적인 움직임을 확인합니다.
조건 결정: 이러한 규칙을 사용하기 위해 어떤 조건이 참이어야 하는지를 결정합니다.
하위 목표 설정: 이러한 조건들은 새로운 목표 또는 하위 목표가 됩니다.
탐색 과정: 하위 목표를 통해 문제의 사실로 되돌아갈 때까지 역방향으로 탐색을 계속합니다. 이는 데이터에서 목표로 이어지는 움직임이나 규칙의 체인을 찾지만, 반대 순서로 진행됩니다.
다른 이름: 목표 기반 추론 또는 역방향 체인이라고도 불립니다.
제안 조건
문제 진술에서 목표나 가설이 주어졌거나 쉽게 설정할 수 있을 때.
문제의 사실과 일치하는 많은 규칙이 있어 결론이나 목표의 수가 증가할 때.
문제 데이터가 주어지지 않고 문제 해결자가 직접 획득해야 할 때.
탐색 방식
원하는 목표에 대한 지식을 사용하여 관련 규칙을 통해 탐색을 안내하고, 불필요한 가지를 제거합니다.
*오일러 경로(Euler Path)
오일러의 관찰:
그래프에 홀수 차수를 가진 노드가 정확히 0개 또는 2개 있어야만 경로가 가능하다고 했습니다. 그렇지 않으면 경로는 불가능합니다.
쾨니히스베르크 문제:
오일러 경로 찾기 문제로 연결됩니다.
술어 논리 표현:
노드의 차수 개념을 제시하지 않습니다.
그래프 이론의 힘:
객체, 속성, 관계의 구조를 분석하는 데 사용됩니다.
*그래프 이론(오일러에 의해 발견)(방향이 있는 그래프)
시작 노드(rooted grpah = unique node)
노드 집합: 문제 해결 과정의 개별 상태를 나타냅니다(유한할 필요 x, 노드가 2개 이상 있어야 아크존재),
중복되는 노드가 있다면 loop or cycle
아크 또는 링크 집합: 노드 쌍을 연결하며, 상태 간의 전환을 나타냅니다.
방향이 없는 그래프 undirected graph
상태 공간 모델:
노드: 문제 해결 과정에서의 이산 상태를 의미합니다. 이는 논리적 추론의 결과나 게임 보드의 구성을 포함할 수 있습니다.
아크: 상태 간 전환을 나타내며, 논리적 추론이나 게임의 합법적인 움직임을 포함할 수 있습니다.
*Implementing Graph Search(상태 공간 그래프를 통해 시작 상태에서 목표로 가는 경로를 찾아야 합니다)
-Backtracking : 모든 경로를 체계적으로 시도하는 기술,추적 검색은 시작 상태에서 시작하여 목표 또는 "막다른 골목"에 도달할 때까지 경로를 추적합니다
-SL : 주 목록의 경우는 현재 시도 중인 경로의 상태를 나열합니다. 목표가 발견되면 SL은 솔루션 경로의 순서대로 나열된 상태 목록을 포함합니다
-NSL : 새 주 목록의 경우는 평가를 기다리는 노드, 즉 아직 생성 및 검색되지 않은 하위 노드를 포함합니다.(나중에 검색될 후보들 포함)
-DE : 또는 막다른 골목는 후손이 목표 노드를 포함하지 않은 상태를 나열합니다. 이러한 상태가 다시 발생하면 DE의 요소로 감지되어 즉시 고려 대상에서 제외됩니다.(나중에 갈 곳에서 제외)
-Backtrack : 스타트에서 시작해서 목표을 만날때까지 진행
-depth-first : 모든 자녀와 그 후손은 형제자매보다 먼저 검사를 받습니다(B^n)
-시작 상태에서 목표까지 최단 경로를 찾을 수 있습니다(최단 경로 보장)
-후손이 많아질수록 조합론 증가(복잡도 증가)
-메모리 낭비 O
-breadth-first : 동등한 레벨을 먼저 검사하고 후손을 검사(B*n)
-상태가 처음 발견되었을 때 상태로 가는 최단 경로를 찾을 수 있다는 보장은 없습니다
너비 우선 검색 알고리즘을 수정하여 만들 수 있습니다(Queue -> stack)
메모리 낭비 x
-best-first : 위에 것과 비슷하지만 가장 가능 가능성이 높은 것을 먼저 조사한다(stack과 queue가 아니다)
*하이퍼그래프:
N: 노드의 집합.
H: 하이퍼아크의 집합. 이는 다음과 같은 순서쌍으로 정의됩니다:
첫 번째 요소는 집합 N의 단일 노드입니다.
두 번째 요소는 N의 부분집합입니다.
일반 그래프는 하이퍼그래프의 특수한 경우로, 자손 노드 집합의 크기가 1인 경우를 말합니다. 즉, 일반 그래프의 간선은 정확히 두 개의 노드를 연결하지만, 하이퍼그래프에서는 하나의 간선(하이퍼아크)이 두 개 이상의 노드를 연결할 수 있습니다.