Best First Search

-------------------------------------
Description
-------------------------------------
Best First Search(BFS) is a Breath First Search that limits each level to a maximum of 10 treatments. Each level adds one new value to the parent treatment. At each level, for each partial treatment at that level, (10 * the number of unset attributes) childeren are created. After all partial treatments have been expanded, and the childeren scored, all but the 10 highest are pruned from a maximum of 500. The result is then passed to a back select.

------------------------------------
Pseudo-code
------------------------------------
BFS(type)
  Start with an empty treatment in the processing list
  
  Until the processing list is empty
    Foreach treatment in the processing list
      If the score is greater than the parent
        Foreach unset attribute
	  Do 10 times
             Add the new treatment (the old treatment + new attribute) to the pending list

    Score each treatment in the pending list
    
    Add the 10 top treatments from the pending list to the processing list
    Empty the pending list
  
  Perform a back select on the best treatment

-----------------------------------
Actual Code
-----------------------------------
(defun best (type)
  (let ((parameters (list 'DYNAMISIM 'CRITICALITY 'CULTURE 'TEAMSIZE 'SIZE 'TEAM-ALPHA))
	(valuesOfEach 10)
	(valuesToKeep 10)
	(listOfTrials (list))
	(nextListOfTrials (list))
	(level 0))
    (push (list (list) (copy-list parameters) 0 0) nextListOfTrials)
    (while (not (null nextListOfTrials))
      (setf nextListOfTrials (mapcar #'(lambda(x)
					 (list (first x) (second x) (runPom2 type (first x)) (fourth x)))
				     nextListOfTrials))
      
      (setf nextListOfTrials (sort nextListOfTrials #'> :key #'third))
      (setf nextListOfTrials (ldiff nextListOfTrials (nthcdr valuesToKeep nextListOfTrials)))

      (setf listOfTrials nextListOfTrials)
      (setf nextListOfTrials nil)
      
      (dolist (trial listOfTrials)
	(if (> (third trial) (fourth trial))
	    (progn
	      (dotimes (x valuesOfEach)
		(dolist (parameter (second trial))
		  (push (list (append (list (list parameter (our-sample parameter))) (first trial))
			      (remove-if #'(lambda (x) (equal x parameter)) (copy-list (second trial)))
			      0 (third trial))
			nextListOfTrials)))))))
    (let ((best (first (sort listOfTrials #'> :key #'third))))
      (backselect (first best) type))))


-------------------------------------
Policy Commitment
-------------------------------------
1. Each level of the tree, one more attribute is fixed.
2. The algorithm does not restart, but different subtrees can be taken based on
   performance.
3. BFS fixes attributes to a set value, although fixing attributes to a range 
   could be done.
4. This algorithm is stochastic, although the random affects of local compleations
   are filtered out. To accomplish this filtering, random values are chosen for 
   the non-compleated attributes randomly until the mean score stabilizes.
6. There is no cache.
7. Early termination occurs if the none of the childeren perform better than the 
   parent.
8. The total best treatment is passed to a back select function. This back select
   function returns the best combination of values for each conjunction of size 
   k = 1 to n where n is the size of the total compleation.