;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; This file is part of "NOVA":  NOVA = search + COCOMO tools
; Copyright, 2008, Tim Menzies tim@menzies.us
;
; NOVA is free software: you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 3 of the License, or
; (at your option) any later version.
;
; NOVA is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
; GNU General Public License for more details.
; You should have received a copy of the GNU General Public License
; a long with NOVA.  If not, see <http://www.gnu.org/licenses/>.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defsearch maxwalksat ((num-tries 10) (num-changes 50) (smart% 0.9))
  (dotimes (i num-tries)
    (if *debug-search* (format t "Try #~a~%" (1+ i)))
    (with-new-path

      ;; start with a random initial solution
      (move-elts (?lots open) open closed)
      (save-state)
      (if *debug-search* (print-state (first-state? path)))
      (dotimes (j num-changes)
	(push path paths)

	;; randomly move treatments between open and closed
	(let ((treatments (?lots (append open closed))))
	  (with-new-path
	    (switch-elts treatments open closed)
	    (save-state)
	    (push path paths)))
	(let ((path2 (pop paths))
	      (path1 (pop paths)))

	  ;; if we're being random, continue on the new path
	  ;; if we're being smart, only continue on the new path if it is better
	  (when (or (< smart% (my-random 1))
		    (< (energy? (first-state? path2)) (energy? (first-state? path1))))
	    (switch-path path2)
	    (energy? (first-state? path))
	    (if *debug-search* (print-state (first-state? path))))))
      (push path paths)))

  ;; switch to the best path
  (switch-path (find (min-energy? paths) paths :key #'min-energy? :test #'equal))
  (if *debug-search* (terpri)))