2 적합성이 강하게 연결된 구성 요소 위상 지정 순서

Question

SCC에 대한 만족 가능성 문제를 해결하고 토폴로지 정렬에 대한 질문이 있습니다. 내가 이것을 기반으로하는 알고리즘은 SCC를 역 위상 구조로 처리하는 것입니다. SCC가 모두 연결되어 있으면 좋을 것입니다. 내 알고리즘은 다음과 같은 경우에 파괴되어이이처럼 보이는 그래프를 만드는

3 3 
-2 3 
1 -2 
-2 -1 

:

두 가지 소스와이 그래프에 두 개의 싱크는, 당신이 거기 시작 위치에 따라 여러 개의 토폴로지 정렬이 있으므로 두 가지 가능한 최종 노드가 있습니다. 사이클이 없으므로 각 노드는 SCC입니다. 소스에서 싱크까지 여러 경로가 있으므로 토폴로지 순서를 반대로 할 때 싱크 x3 또는 싱크 x2에서 시작할 수 있습니다. 나에게 정확한 답을 줄 경로는 1, -2, -3 또는 -1, -2, -3이되는! x2에서 시작하는 것입니다. 둘 다 솔루션입니다. 그러나 제가 x3에서 시작한다면 가능한 해결책은 -1,2,3입니다.

그래서 두 개의 싱크대를 볼 때 어떻게 마지막으로 위상을 결정할 수 있습니까? 분명히 대답은! x2이지만 알고리즘이이를 어떻게 결정할 지 알아 내려고합니다. 나는 네 가지 아이디어를 참조하십시오!

• 가 선도 그것으로 더 많은 노드를 가지고 있기 때문에 X2는 마지막
는 각각의 진리 값을 설정합니다 긴 경로
• 의 끝 부분에 있기 때문에
• X2는 마지막입니다! 모든 것을 처리하기 전에 싱크대를 찾으십시오.
• 마지막으로 어떤 것인지 알 수있는 방법이 없으므로 가능한 모든 솔루션을 만들고 작동하는지 확인하기 위해 각각을 테스트하십시오.

또는 토폴로지별로 SCC를 주문하는 것에 대해 뭔가가 있습니까? 이것은 이전 코스에서 강하게 연결된 구성 요소 지정을 전달하는 데 사용한 알고리즘을 기반으로하므로 완전히 잘못 될 수 없습니다.

Answer 1

코드를 보지 못해도 확신 할 수 없지만, 리터럴을 처리 할 때 값을 설정하고 나중에 토폴로지 순서에서 부정을 만났을 때 뒤집습니다. 핵심은 일단 변수를 설정하면 다시 변수를 변경하지 않는다는 것입니다. 이미 설정된 값이있는 변수의 리터럴을 건너 뜁니다.

편집 추가 : 귀하의 의견에 나는 문제가 있다고 생각합니다. ! x2가 역 토폴로지 정렬에서 첫 번째 일 때 변수 x2를 true로 설정하는 것에 대해 언급합니다. 리터럴! x2를 true로 설정해야합니다. 즉, 변수 x2를 false로 설정해야합니다. 그렇게하면 솔버가 어떤 싱크대로 시작하든 관계없이 작동해야합니다.