외판원 순회 문제를 백트래킹, 브루트포스로 해결하려면 O(N!)까지도 걸린다. (외판원 순회 문제 자체에 대한 내용은 2098 외판원 순회 참고)
비트마스킹과 DP를 사용하면 O(N^2 * N^2)로 줄일 수 있댄다.
첫 출발한 도시를 제외하면 도시의 중복 방문이 허용되지 않기 때문에 visited 배열이 필요하다. 일반적으로 visited 배열은 boolean 배열로 구현하는데, 이 문제를 해결하기 위해서는 모든 케이스가 각자의 visited 배열을 가지고 있어야 해서 메모리 크기가 천정부지로 치솟는다. 따라서 메모리 사용량을 줄이기 위해 비트마스킹을 사용하는 것. 물론 시간적인 이득도 있다.
즉, 단순한 boolean 배열의 사용까지 허용하지 않는 최적화가 필요하다는 얘기고, 비슷하게 단순 visited를 가지고 있어야 하는 경우에는 정수 하나로 해결할 수 있다는 얘기다.
최적화 기법적인 내용이라서 외판원 순회 자체의 핵심적인 내용은 아니지만, 애당초 극한의 최적화 알고리즘이라서 외판원 순회를 해결하면서 비트 마스킹을 같이 사용하게 되는 경우가 많다.
자료구조는 비트마스킹으로 해결했다고 치고, 시뮬레이션의 구현 자체는 별거 없이 DFS로 해결한다. 또, 최소 비용을 산출하기 위해서 DP를 사용한다.
“외판원 순회”라는 공학적 상황을 해결하기 위해 이런 저런 방법들이 모인 것이지, 사실 뜯어보면 벨만-포드, 위상 정렬처럼 어떤 특정한 “알고리즘”이라고 부르기 애매하다. 알고리즘이라고 부를만한건 DPS랑 DP 정도이고 비트마스킹은 그냥 자료구조니까… 외판원 순회 문제를 해결할 수 있는 특정한 알고리즘에 대한 내용이 아니라는 것이다. 비유하자면 일종의 조합식 같은 느낌?