Talk:WalkSAT

Inventor

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)[reply]

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)[reply]

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)[reply]

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)[reply]

In computer science, you see this all the time, that there's an algorithmic framework, with many policy options (placement algorithms in file systems, page replacement heuristics in caching), because the real world is a messy place, and certain variations work better in specific contexts. If WalkSAT and GSAT differ primarily along the policy dimension, I can't see them benefiting from separate pages (though I'm a splitter at heart). IMO, they would need a hefty and substantially different analytic heuristic theory underlying the policy choices to justify such a split. — MaxEnt 17:34, 16 April 2018 (UTC)[reply]

References

A very good explanation of the algorithm along with the pseudo-code is provided in Domingo's paper on LazySAT algorithm, which is an optimized version of WalkSAT. —Preceding unsigned comment added by Prasenjitmukherjee (talk • contribs) 07:44, 20 June 2008 (UTC)[reply]

I prefer WalkSat myself

I prefer WalkSat myself, but the page name is WalkSAT, and that should dictate a consistent, internal form. I'd be happy to see the page name changed, but I don't even know if that's standard usage. — MaxEnt 17:28, 16 April 2018 (UTC)[reply]