일부 저널에 WSAT (Walking SAT) 알고리즘은 SAT 문제 해결에 Simulated Annealing 알고리즘보다 우수한 성능을 제공합니다.WSAT가 Simulated Annealing보다 성능이 우수한 이유는 무엇입니까?
제 질문은 누군가가 친절하게 왜 우리가이 결과를 얻었는지 설명 할 수 있습니까? SA가 범용 알고리즘과 비슷하기 때문일 수 있습니까?
편집 : Here 어쩌면 내가 읽어 가장 관련 문서.
시뮬레이트 된 어닐링은 무작위로 선택된 이웃을 평가합니다. 항상은 물리에서 직감을 따라 더 나은 경우 이웃으로 이동합니다. 하지만 WalkSAT가 더 나은 경우에도 가끔 이 아니라 이웃으로 이동합니다.
WalkSAT로 만족스러운 3-CNF를 시작하면 : 또는 이미 문제를 해결했거나 일부 절이 만족스럽지 않습니다. 절이 만족스럽지 않다는 사실은 해당 절의 변수 중 적어도 하나가 솔루션을 찾기 위해 반전되어야 함을 의미합니다. 길이가 3 인 조항에서 변수를 임의로 선택하면 각 플립이 33 % 이상의 올바른 확률로 쉽게 볼 수 있습니다 [1].
SA는
이 WalkSAT가 SA보다 낫다 왜 자신을 설명 할 방법이지만, 아마이 ... 성공하는 등 높은 확률을 가지고 로컬 최대에 갇혀되는 높은 위험을 가지고하지 않습니다 이미이 문제에 관한 연구;) this paper [2]와 SA와 WalkSAT 간의 자세한 비교를 제공해야합니다.
[1] Papadimitrou, C. H., & Steiglitz, K. (1982). 조합 최적화 : 알고리즘 및 복잡성. 출판사 : Prentice Hall.
[2] Selman, B., Kautz, H.A., & Cohen, B. (1994). 지역 검색 개선을위한 소음 전략. AAAI (Vol. 94, pp. 337-343).
세부 사항을 추가해주세요. '내가 읽은 저널'은 매우 특이하지 않습니다. 이 작업에 대한 테스트 및 기타 세부 정보가이 질문에 대답해야합니다. – MrSmith42
내 질문을 편집하고 Selman, Kautz 문서 중 하나에 대한 링크를 추가했습니다. 감사합니다. @ MrSmith42 – Jose