problemsolver_width.java

来自「puzzle game with java.very good !」· Java 代码 · 共 70 行

/*
 * 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.Iterator;
import java.util.LinkedList;

/**
 * This ProblemSolver will search for the 'best' solution using a search algorithm that searches in the 'width'.
 */
public class ProblemSolver_Width extends ProblemSolver {
	
	private LinkedList open = new LinkedList(), closed = new LinkedList();
	
	public PuzzleState getSolution(PuzzleState start, PuzzleState target)
	{
		solutionFinderStarted();
		
		this.clearLists();
		open.addFirst(start.clone());//save a clone of the startposition.

		while(open.size() > 0)
		{
			PuzzleState toExpand = (PuzzleState)open.getFirst();

			Iterator iterator = toExpand.getSuccessors().iterator();
			while(iterator.hasNext())
			{
				intNumberOfNodesExpanded++;
				
				Object obj = iterator.next();
				
				if(target.equals(obj))
				{
					//If true => we have found the solution.
					createSolutionList((PuzzleState)obj);
					return getFirst();
				}
					
				
				if(!closed.contains(obj) && !open.contains(obj))//als deze toestand nog niet voorkomt bij de closed of open statussen
				{
					// if this PuzzleState is not yet present in the closed or open PuzzleState lists, 
					// add it to the open list (add it at the end)
					open.addLast(obj);
				}
			}
			//Now remove the expanded Puzzle state from the open list and add it to the closed list.
			closed.addFirst(open.removeFirst());
		}	
		return null;
		
	}
	
	protected void clearLists()
	{
		super.clearLists();
		open.clear();
		closed.clear();
	}
	


}