긱스포 긱스

전제조건:

• 재귀
• 복잡도 분석

역추적은 어떤 시점에서든 문제의 제약 조건을 충족시키지 못하는 솔루션을 제거하면서 한 번에 하나씩 점진적으로 솔루션을 구축함으로써 문제를 재귀 적으로 해결하는 알고리즘 기술입니다(여기서는 검색 트리의 모든 수준에 도달 할 때까지 경과 된 시간을 말합니다).

위키 정의에 따르면,

역추적은 계산 문제를 해결하기 위해 가능한 모든 조합을 검색하는 것을 고려하는 일반적인 알고리즘 기법으로 정의 할 수 있습니다.

역추적에는 세 가지 유형의 문제가 있습니다–

1. 결정 문제-이,우리는 가능한 솔루션을 검색 할 수 있습니다.
2. 최적화 문제-이,우리는 최고의 솔루션을 검색 할 수 있습니다.
3. 열거 문제-이,우리는 가능한 모든 솔루션을 찾을 수 있습니다.

역추적을 사용하여 문제를 해결할 수 있는지 확인하는 방법은 무엇입니까?

일반적으로 객관적인 솔루션에 대해 명확하고 잘 정의 된 제약 조건이있는 모든 제약 조건 만족 문제는 후보자가 유효한 솔루션으로 완료 될 수 없다고 판단되는 즉시 후보자를 솔루션에 점진적으로 구축하고 후보자를 포기(“역 추적”)하는 역 추적으로 해결할 수 있습니다. 그러나 논의되는 대부분의 문제는 입력 크기 순서의 대수,선형,선형-로그 시간 복잡성의 동적 프로그래밍 또는 욕심 많은 알고리즘과 같은 다른 알려진 알고리즘을 사용하여 해결할 수 있으므로 모든 측면에서 역 추적 알고리즘을 능가합니다(역 추적 알고리즘은 일반적으로 시간과 공간 모두에서 지수 적이기 때문에). 그러나 몇 가지 문제는 여전히 남아,그 단지 지금까지 그들을 해결하기 위해 알고리즘을 역 추적했다.

당신 앞에 세 개의 상자가 있고 그 중 하나만 금화를 가지고 있지만 어느 것을 알지 못하는 상황을 생각해보십시오. 그래서,동전을 얻기 위해,당신은 상자 하나 하나를 모두 열어야합니다. 이 동전을 포함하지 않는 경우 먼저 첫 번째 상자를 확인합니다,당신은 당신이 동전을 찾을 때까지 그래서 그것을 닫고 두 번째 상자를 확인해야합니다. 이 역 추적이 무엇인지,즉,최상의 솔루션에 도달하기 위해 하나씩 모든 하위 문제를 해결하는 것입니다.

알고리즘은 빈 솔루션 세트로 시작하여 솔루션을 구축하기 시작합니다. 에스= {}

1. 아직 남아 있는 첫 번째 이동을에 추가합니다(가능한 모든 이동은에 하나씩 추가됩니다). 이제 알고리즘의 검색 트리에 새 하위 트리이 생성됩니다.
2. 의 각 제약 조건을 만족하는지 확인하십시오.
   • 예인 경우 하위 트리은”자식”을 더 추가 할 수 있습니다.
   • 그렇지 않으면 전체 하위 트리은 쓸모가 없으므로인수를 사용하여 1 단계로 되돌아갑니다.
3. 새로 형성된 하위 트리의”자격”이있는 경우,인수를 사용하여 1 단계로 되돌아갑니다.전체 데이터에 대한 솔루션이라는 것을 반환하는 경우
4. . 프로그램을 출력하고 종료하십시오.
   그렇지 않은 경우 현재에서 솔루션이 불가능하다는 것을 반환하고 폐기하십시오.

재귀와 역추적의 차이:

재귀에서 함수는 기본 케이스에 도달할 때까지 자체를 호출합니다. 역 추적에서 우리는 재귀를 사용하여 문제에 대한 최상의 결과를 얻을 때까지 모든 가능성을 탐구합니다.

역추적을 위한 의사 코드:

1. 재귀 역 추적 솔루션.

void findSolutions(n, other params) : if (found a solution) : solutionsFound = solutionsFound + 1; displaySolution(); if (solutionsFound >= solutionTarget) : System.exit(0); return for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); findSolutions(n+1, other params); removeValue(val, n);

2. 솔루션이 존재하는지 여부 찾기

boolean findSolutions(n, other params) : if (found a solution) : displaySolution(); return true; for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); if (findSolutions(n+1, other params)) return true; removeValue(val, n); return false;

표준 역 추적 문제를 해결해 보겠습니다.
‘엔퀸’은 체스판 위에’엔퀸’을 놓는 문제다. 예를 들어,다음 4 여왕 문제에 대한 솔루션입니다.

예상 출력은 퀸즈가 배치되는 블록에 대해 1 을 갖는 이진 행렬입니다. 예를 들어,다음은 위의 4 퀸 솔루션에 대한 출력 행렬입니다.

{ 0, 1, 0, 0}{ 0, 0, 0, 1}{ 1, 0, 0, 0}{ 0, 0, 1, 0}

역 추적 알고리즘:아이디어는 가장 왼쪽 열에서 시작하여 퀸즈를 하나씩 다른 열에 배치하는 것입니다. 우리는 열에 여왕을 배치 할 때,우리는 이미 배치 여왕과 충돌을 확인. 현재 열에서 충돌이 없는 행을 찾으면 이 행과 열을 솔루션의 일부로 표시합니다. 우리는 충돌로 인해 이러한 행을 찾을 수없는 경우 우리는 역 추적 및 거짓 반환.

1) Start in the leftmost column2) If all queens are placed return true3) Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this as part of the solution and recursively check if placing queen here leads to a solution. b) If placing the queen in leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this (Backtrack) and go to step (a) to try other rows.3) If all rows have been tried and nothing worked, return false to trigger backtracking.

위의 접근 방식을 완벽하게 구현하려면 역 추적|세트 3(엔 퀸 문제)에 대한 기사를 참조 할 수 있습니다.
역추적 문제 추가:

• 역 추적/세트 1(기사의 투어 문제)
• 역 추적/세트 2(미로의 쥐)
• 역 추적/세트 4(하위 집합 합계)
• 역 추적|세트 5(엠 색칠 문제)
• –> 더