100000 리터럴에 대해 2-SAT 문제를 구현하고 싶습니다. 따라서 200000 개의 정점이 있습니다. 그래서 나는 각 버텍스로부터 모든 도달 가능한 버텍스들, 공간 복잡성 O(200000^2)의 배열을 갖는 것에 박차를 가하고 있습니다. 그래서 이것을위한 해결책을 제안하십시오. 그리고 2-SAT 문제의 효과적인 실행에 대한 어떤 생각을 던져주십시오. wikipedia에서2-Satisfiability 문제에서 구현 문제
:
는... 2 satisfiability는 다항식 시간에 해결할 수 있습니다. Aspvall, Plass & Tarjan (1979)이 관찰됨에 따라, 2 개의 적합성 인스턴스는 인스턴스의 모든 변수가 동일한 변수의 부정과 함축적으로 서로 다른 강하게 연결된 구성 요소에 속하는 경우에만 해결할 수 있습니다. 강하게 연결된 구성 요소는 깊이 우선 탐색에 기반한 알고리즘에 의해 선형 시간으로 발견 될 수 있기 때문에 동일한 선형 시간 제한이 2 적합성에도 적용됩니다.
그 단락의 대부분을 이해하는 척하지 않겠지 만 (이 2 SAT 문제를 해결하는 데 사용할 수있는 알고리즘이며, 그것은 그 참조 문서에 설명되어 나타납니다 A linear-time algorithm for testing the truth of certain quantified boolean formulas). 그것은 대략 $ 20 USD를 위해 온라인으로 명백하게 구매 될 수있다. 그게 도움이되는지 아닌지는 확실하지 않지만 거기에 있습니다!
이 전체 스레드는 약간 엉망입니다. 예, 선형 시간으로 2-sat를 풀 수는 있지만, 많은 변수에 대해 풀 수는 없습니다. 2-sat를 풀 때의 시간은 함축적으로 200 000 개의 변수가 (200000 * 199999)/2까지 도달 할 수있는 함축에 비례합니다. 그리고이 솔루션을 사용하면 비슷한 양의 메모리가 필요합니다 . 또 다른 해결책이 있습니다 (느린 속도이지만 많이 필요한 메모리가 필요없는 강하게 연결된 구성 요소를 사용하지 마십시오).
종이에 대한 링크가 있습니까? 부디. – avd
http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf – liori
대단히 감사합니다. BTW 어떻게 검색합니까? 나는 검색을 위해 1 시간을 낭비했지만 얻을 수 없었다. – avd