Talk:WalkSAT

From Wikipedia, the free encyclopedia

Bram Cohen says he invented the WalkSAT variant of GSAT and mentioned a paper on the subject he co-authored. See his blog. Has anybody got a link or reference to or the title of this paper? EdH 18:28, 19 March 2006 (UTC)

Is it B. Selman, H. Kautz, B. Cohen, Noise strategies for improving local search, Twelfth National 5 Conference on Artificial Intelligence, AAAI Press, 1994, pp. 337-343. ? EdH 18:44, 19 March 2006 (UTC)

I think this page can be improved significantly. There are fundamental differences between GSAT and WalkSAT that are not explained here, including things like freebie moves and method for candidate variable selection. It may be important to note that WalkSAT is a generic label for a class of strategies. When used to describe a single strategy it usually refers to WalkSAT(SKC). (SKC stands for Selman Kautz and Cohen from the above paper even though that paper mentions a number of different variants). I can make the changes in a few days if no one else wants too. If anyone has any opinion about discussing variants of both strategies here let me know and I can take that into consideration. Does anyone think that GSAT and WalkSAT should have seperate pages? Sharp Tac 15:08, 20 November 2006 (UTC)

In the context of local search it may also be useful to mention the PAC (Probabilistic Approximate Completeness) property, which may need its own page. Any comments welcome Sharp Tac 15:14, 20 November 2006 (UTC)