의견.png

"역추적검색"의 두 판 사이의 차이

해시넷
이동: 둘러보기, 검색
잔글 (→‎개요)
6번째 줄: 6번째 줄:
 
==휴리스틱==
 
==휴리스틱==
 
역추적검색을 빠르게 만드는 휴리스틱은 어떤 값을 할당할 것인지 선택할 때 어떤 값이 최소 개수의 미래의 값들을 제약하는지 보는 전방향 체크를 사용한다. 전방향 체크는 해를 더 빨리 얻을 것 같은 값을 선택하는 것이다. 섬세한 역추적검색은 분기 함수(bounding function)를 사용한다. 분기 함수는 해를 얻는 것이 가능한지 확인하기 위해 검사되는 문제에 만들어 모든 할당 단계에서 작동한다. 그래서 간단한 테스트를 통해 실패할 것 같은 부분적인 해를 찾아내 탐색 대상의 99%까지 제외하기도 한다. 분기 함수는 종종 지수적 탁샘공간인 모든 단계에서 작동하기 때문에, 계산하기 쉬워야 한다.
 
역추적검색을 빠르게 만드는 휴리스틱은 어떤 값을 할당할 것인지 선택할 때 어떤 값이 최소 개수의 미래의 값들을 제약하는지 보는 전방향 체크를 사용한다. 전방향 체크는 해를 더 빨리 얻을 것 같은 값을 선택하는 것이다. 섬세한 역추적검색은 분기 함수(bounding function)를 사용한다. 분기 함수는 해를 얻는 것이 가능한지 확인하기 위해 검사되는 문제에 만들어 모든 할당 단계에서 작동한다. 그래서 간단한 테스트를 통해 실패할 것 같은 부분적인 해를 찾아내 탐색 대상의 99%까지 제외하기도 한다. 분기 함수는 종종 지수적 탁샘공간인 모든 단계에서 작동하기 때문에, 계산하기 쉬워야 한다.
 +
 +
==프로그램 코드==
 +
다음은 모든 경우 탐색을 위해 깊이 우선 탐색을 사용하고 특정 조건을 isValid()로 처리한 프로그램 코드이다.
 +
package main
 +
import (
 +
    "fmt"
 +
)
 +
func main() {
 +
    var N int
 +
    fmt.Scanf("%d", &N)
 +
    grid := make([][]bool, N)
 +
    for i := 0; i < N; i++ {
 +
      grid[i] = make([]bool, N)
 +
    }
 +
    fmt.Println(dfs(grid, 0))
 +
}
 +
 +
func dfs(grid [][]bool, x int) int {
 +
    if x == len(grid) {
 +
      return 1
 +
    }
 +
    var cnt = 0
 +
    for i := 0; i < len(grid); i++ {
 +
      if isValid(grid, x, i) {
 +
          grid[i][x] = true
 +
          cnt += dfs(grid, x+1)
 +
          grid[i][x] = false
 +
      }
 +
    }
 +
    return cnt
 +
}
 +
 +
func isValid(grid [][]bool, x, y int) bool {
 +
    var diff int
 +
    for j := x-1; j >= 0; j-- {
 +
      diff++
 +
      if grid[y][j] || (y-diff >= 0 && grid[y-diff][j]) || (y+diff < len(grid) && grid[y+diff][j]) {
 +
          return false
 +
      }
 +
    }
 +
    return true
 +
}
  
 
{{각주}}
 
{{각주}}

2020년 7월 29일 (수) 10:03 판

역추적검색(Backtracking)은 제약조건 만족 문제(Constraint Satisfaction Problem)를 해결하기 위한 알고리즘이다. 역추적검색은 문제를 해결하기 위해 모든 해를 나열한다.

개요

역추적검색은 제약조건 만족 문제를 해결하기 위해 조합 알고리즘 문제에 대해 가능한 모든 해를 나열하는 것이다. 제약조건 만족 문제는 완전한 해를 가진 문제이고, 요소들의 순서는 문제 되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. 부분적인 조합을 시도해 보지 않아도 된다는 장점이 있으며, 조건을 만족할 경우 모든 경우의 수를 찾는 것보다 빠를 수 있다. 역추적검색이라는 용어는 1950년 미국의 수학자 데릭 레머(Derrick Lehmer)에 의해 만들어졌다. 역추적검색은 맞는 답을 구할 때까지 모든 가능성을 시도하는 깊이 우선 탐색이다. 탐색 도중 새로운 탐색이 제대로 작동하지 않으면 다른 새로운 탐색이 가능한 선택 포인트로 역추적해서 다음의 새로운 탐색을 시도한다. 새로운 탐색 영역이 고갈되면 이전의 선택 포인트로 돌아와 다음의 새로운 탐색을 시도한다. 더 이상의 선택 포인트가 존재하지 않으면 탐색은 실패로 끝난다. 역추적검색은 보통 각각의 인스턴스가 하나 이상의 변수를 가지고 모든 이용 가능한 값을 그 변수에 할당하는 재귀 함수 형태를 가지고, 계속되는 재귀 호출과 일치하는 값을 유지한다. 역추적검색은 깊이 우선 탐색과 유사하지만 공간 사용이 덜하며 딱 한 개의 최신 해만 유지하고, 업데이트한다. 탐색 속도를 빠르게 하기 위해서 재귀 호출을 하기 전에 값이 선택될 때, 그 알고리즘은 할당되지 않은 영역과 다투지 못하도록 그 값을 제거하는 전방향 체크(forward checking)나 새로이 할당된 값이 어떤 다른 값을 배제하는지 보기 위해 모든 제약조건을 체크하는 제약전파(constraint propagation)를 사용한다. 역추적검색은 프롤로그(Prolog) 같은 프로그램 언어에 사용되며, 텍스트 파싱(text parsing)에도 사용된다. 역추적검색으로 해결할 수 있는 문제는 여덟 개의 퀸 퍼즐, 스도쿠, 십자말풀이 등이 있다.

휴리스틱

역추적검색을 빠르게 만드는 휴리스틱은 어떤 값을 할당할 것인지 선택할 때 어떤 값이 최소 개수의 미래의 값들을 제약하는지 보는 전방향 체크를 사용한다. 전방향 체크는 해를 더 빨리 얻을 것 같은 값을 선택하는 것이다. 섬세한 역추적검색은 분기 함수(bounding function)를 사용한다. 분기 함수는 해를 얻는 것이 가능한지 확인하기 위해 검사되는 문제에 만들어 모든 할당 단계에서 작동한다. 그래서 간단한 테스트를 통해 실패할 것 같은 부분적인 해를 찾아내 탐색 대상의 99%까지 제외하기도 한다. 분기 함수는 종종 지수적 탁샘공간인 모든 단계에서 작동하기 때문에, 계산하기 쉬워야 한다.

프로그램 코드

다음은 모든 경우 탐색을 위해 깊이 우선 탐색을 사용하고 특정 조건을 isValid()로 처리한 프로그램 코드이다. 

package main
import (
   "fmt"
)
func main() {
   var N int
   fmt.Scanf("%d", &N)
   grid := make([][]bool, N)
   for i := 0; i < N; i++ {
      grid[i] = make([]bool, N)
   }
   fmt.Println(dfs(grid, 0))
}

func dfs(grid [][]bool, x int) int {
   if x == len(grid) {
      return 1
   }
   var cnt = 0
   for i := 0; i < len(grid); i++ {
      if isValid(grid, x, i) {
         grid[i][x] = true
         cnt += dfs(grid, x+1)
         grid[i][x] = false
      }
   }
   return cnt
}

func isValid(grid [][]bool, x, y int) bool {
   var diff int
   for j := x-1; j >= 0; j-- {
      diff++
      if grid[y][j] || (y-diff >= 0 && grid[y-diff][j]) || (y+diff < len(grid) && grid[y+diff][j]) {
         return false
      }
   }
   return true
}

각주

참고자료

같이 보기


  의견.png 이 역추적검색 문서는 알고리즘에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.  

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스
채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW)
매칭 알고리즘 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더
추천 알고리즘 TF-IDF • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링
고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘
대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘
제약 만족 문제 국소검색 • 역추적검색 • 제약전파
게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임
위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반
원본 주소 "http://wiki.hash.kr/index.php?title=역추적검색&oldid=326290"