백 트랙킹과 분기 및 바인딩 사용의 이점

나는 DP가 TSP와 같은 많은 NP 완전한 문제에 대해 더 나은 성능을 제공한다는 것을 알고 있습니다. 필요한 공간이 크지 만 복잡성이 줄어 듭니다.백 트랙킹과 분기 및 바인딩 사용의 이점

하지만 나는 무차별 대항력 검색과 비교할 때 분기 및 바인딩 및 백 트랙킹의 효율성을 이해할 수 없었습니다.

브 루트 포스가 b & b 또는 역 추적 중 어느 하나일까요?

2012-04-08 user567879

철저한 검색이란 무차별 검색을 의미합니까? – Gangadhar

@Gangadhar 무차별 검색으로 바 꾸었습니다 – user567879

철저한 검색을 사용하면 모든 N! 가능한 노드 간의 경로. 역 추적을 사용하면 노드의 절반을 방문하는 경로를 계산할 수 있으며, 지금까지 발견 된 최상의 경로보다 이미 더 비쌉니다. 그 시점에서 부분 경로를 조사하는 것을 중지하십시오. 이렇게하면 부분 경로를 완료하여 생성 된 모든 경로를 계산하지 않으므로 철저한 검색을 통해 시간을 절약 할 수 있습니다.

출처

2012-04-08 04:35:00 mcdowella

하지만 최악의 경우 모두 N을 확인해야합니다! 조합! – user567879

@ user567879 : 수정하십시오. 은색 탄환은 없습니다. 분기 및 바운드 솔루션은 * 최악의 경우가 아니라 * 평균 * 사례에 도움이됩니다. – amit

브랜치와 브랜치에 대한 최악의 경우 경계를 TSP에서 알 수 없습니다. 필자가 보았던 모든 writeups (필자가 작성한 지나친 단순화 된 예제보다 더 나은 분기 기능과 더 나은 바운딩 함수 선택)은 일반적으로 컴퓨터 실험을 통해 예상되는 동작에 집중됩니다. 그러나 이러한 실험을 통해 신중한 지사와 경계는 실제로 무언가를 더 잘 수행 할 수 있음을 보여줍니다 (예 : http://www.tsp.gatech.edu/sweden/compute/compute.htm). 일부 핸드 튜닝 - 내 눈을 사로 잡았다. – mcdowella

백 트랙킹과 분기 및 바인딩 사용의 이점

답변

관련 문제