검색문제

Search problem

계산 복잡성 이론과 계산 가능성 이론에서, 검색 문제는 이진 관계로 대표되는 계산 문제의 한 유형이다. 필드(R) ) ⊆ ⊆과+ T가 튜링 기계와 같은 2진수 관계인 경우, T는 다음과 같은 경우 R을 계산한다.

  • 만약 x가 R(x, y)과 같은 y가 있다면, T는 출력 z와 함께 x를 받아들여서 R(x, z) (여러 y가 있을 수 있고, T는 그 중 하나만 찾으면 된다)
  • 만약 x가 R(x, y)과 같은 y가 없다면, T는 x를 거부한다.

직관적으로 문제는 물체 "x"에서 구조 "y"를 찾는 데 있다. 알고리즘은 적어도 하나의 해당 구조가 존재하고, 그 다음 이 구조의 발생이 출력되면 문제를 해결한다고 하며, 그렇지 않으면 알고리즘이 적절한 출력("Item not found" 또는 이와 유사한 메시지)으로 정지한다.

이러한 문제는 그래프 이론에서 매우 빈번하게 발생한다. 예를 들어 그래프에서 특정 일치, 패거리, 독립 집합 등과 같은 구조를 찾는 것이 관심의 대상이다.

부분함수의 그래프는 2진수 관계이며, T가 부분함수를 계산하면 최대 1개의 가능한 출력이 있다는 점에 유의한다.

R관계는 검색 문제로 볼 수 있으며, R을 계산하는 튜링 기계도 이를 해결한다고 한다. 모든 검색 문제에는 해당하는 의사결정 문제, 즉

이 정의는 여러 문자열을 하나의 문자열로 압축할 수 있는 적절한 인코딩(예: 구분 기호로 연속적으로 나열)을 사용하여 n-ari 관계로 일반화할 수 있다.

정의

검색 문제는 다음과 같이 정의된다.[1]

목표

문제를 해결하기 위한 알고리즘이 주어지지 않고 솔루션이 어떻게 보이는지 명세만 제시했을 때 솔루션을 찾으십시오.[1]

검색방법

  • 일반 검색 알고리즘: 그래프, 시작 노드 및 목표 노드가 주어지며 시작 노드에서 경로를 점진적으로 탐색한다.
  • 탐색한 시작 노드로부터 경로의 경계를 유지한다.
  • 검색이 진행됨에 따라, 프런티어는 목표 노드가 마주칠 때까지 미개척 노드로 확장된다.
  • 국경의 확장방식은 검색전략을 정의한다.[1]
   입력: 그래프, 시작 노드 집합, n이 목표 노드인지 테스트하는 부울 절차 목표(n)    프런티어 := {s : s는 출발 노드}이다. 프런티어가 비어 있지 않은 동안: 프런티어로부터 경로 <n0, ..., nk>를 선택 및 제거한다. 목표(property)가 <n0, ..., nk>를 반환하는 경우, nk의 모든 이웃 n은 프런티어 에 <n0, ..., nk, nk, nk>을 추가한다; 도중에 종료한다.

참고 항목

참조

  1. ^ a b c Leyton-Brown, Kevin. "Graph Search" (PDF). ubc. Retrieved 7 February 2013.

이 글에는 크리에이티브 커먼스 귀속/공유-알리케 라이센스에 따라 라이센스가 부여된 PlanetMath의 검색 문제 자료가 통합되어 있다.