problemsolver_greedysearch.java

puzzle game with java.very good !

/*
 * Created on 9-okt-2004
 *
 * To change the template for this generated file go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */
package logic;


import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;



/**
 * This ProblemSolver will search for the 'a' solution (not necessairily the 'best' solution like the ProblemSolver_Width)
 * It uses a search algorithm that is called the 'greedy' search.
 */
public class ProblemSolver_GreedySearch extends ProblemSolver {
	private TreeSet open;
	private ArrayList closed;
	
	public PuzzleState getSolution(PuzzleState start, PuzzleState target)
	{
		this.clearLists();
		
		//We use a TreeSet to keep the 'open' list.
		//This means the PuzzleStates will be ordered automaticually by the ManhattenComparator.
		open = new TreeSet(new ManhattanComparator(target));
		closed = new ArrayList();
		solutionFinderStarted();
		
		open.add(start.clone());
		
		while(open.size() > 0)
		{
			PuzzleState toExpand = (PuzzleState)open.first();
			
			Iterator iterator = toExpand.getSuccessors().iterator();
			while(iterator.hasNext())
			{
				intNumberOfNodesExpanded++;
				
				Object obj = iterator.next();
				
				if(target.equals(obj))
				{
					createSolutionList((PuzzleState)obj);
					return getFirst();
				}
					
				if(!closed.contains(obj) && !open.contains(obj))//als deze toestand nog niet voorkomt bij de closed
				{
					//Add each successor to the TreeSet
					//The PuzzleStates with the shortest ManhattanDistance will appear first in the list automaticually
					open.add(obj);
				}
			}
			closed.add(toExpand);
			open.remove(toExpand);
			
		}
		return target;
	}
	protected void clearLists()
	{
		super.clearLists();
		if(open != null)
			open.clear();
		if(closed != null)
			closed.clear();
	}
}