나는 백 트랙킹 알고리즘 설계 기술에 대해 읽었습니다. 그것은 다음과 같이 언급됩니다.백 추적 알고리즘 설계 기술 정의
역행은 체계적으로 모든 사용할 수있는 옵션 중에서 문제에 대한 해결책을 검색하는 무력 방법의 정교화하고있다. 이는 솔루션이 이고 벡터가 (v1, v2, ..., vm)이고 깊이가 가장 먼 방법으로 인 경우 해결책이 발견 될 때까지 벡터의 도메인이 있다고 가정합니다. .
위의 텍스트에 대한 내 질문은 다음과 같습니다.
솔루션에 의한 작성자 평균은 벡터로 표시되는 것은 무엇입니까?
벡터 도메인별로 작성자는 무엇을 말합니까?
주셔서 감사합니다.
8 개의 여왕 문제를 예로 들어 봅시다.
솔루션은 8 개 위치의 벡터로 각 여왕마다 1 개씩 있습니다. 벡터는 공간 : ([0,7]x[0,7])^8에 속합니다. 이것은 매우 큰 공간이므로 역 추적 알고리즘은 해답이 존재하는 더 작은 '도메인'(부분 공간 ([0,7]x[0,7])^8)으로 제한하기 위해 '여왕은 다른 여왕을 확인하지 않아야합니다.'라는 조건을 사용합니다.
이 경우 알고리즘은 1 차 여왕에 대해 허용 된 값 중 하나를 시도하여 해답 벡터를 만듭니다. 벡터는 [ (0,0), X, X, X ...]입니다. 그런 다음 조건을 사용하여 두 번째 위치를 검색해야하는 부분 공간을 제한하고 적합한 벡터를 찾을 때까지 계속 수행합니다.
깊이 우선 의미하는 알고리즘 [ (0,0), X, X, X ...]
[ (0,1), X, X, X ...] 용액의 도메인으로 이동하기 전에