Searching the state space - Best-first search (Prohledávání stavového prostoru - informované prohledávání upřednostňující „slibné“ stavy)

ComparatorState.java

package ui.logic;

import ui.entities.IState;
import java.util.Comparator;

public class ComparatorState implements Comparator<IState> {

    @Override
    public int compare(IState o1, IState o2) {
        return o1.compareTo(o2);
    }
}

ISolution.java

package ui.entities;

import java.util.List;

public interface ISolution<T extends IState> {

    public List<T> getSolutionStates();

    public boolean isSolution();
}

IState.java

package ui.entities;

import java.util.List;

public interface IState extends Comparable<IState> {

    public int getStep();

    public List<IState> expand();

    public IState getParent();

    public boolean hasParent();

    public Object getWay();
}

ITask.java

package ui.entities;

public interface ITask<T extends IState> {

    public T getInitialState();

    public boolean IsSolution(T state);
}

Solution.java

package ui.logic;

import java.util.ArrayList;
import java.util.List;
import ui.entities.ISolution;
import ui.entities.IState;

public class Solution<T extends IState> implements ISolution {

    private List<T> states;

    public Solution() {
        states = new ArrayList<T>();
    }

    public Solution(List<T> states) {
        this.states = states;
    }

    @Override
    public List<T> getSolutionStates() {
        return states;
    }

    @Override
    public boolean isSolution() {
        return !states.isEmpty();
    }
}

UISpaceStateProblemSolver.java

package ui.logic;

import algorithm.PriorityQueue;
import java.util.ArrayList;
import java.util.List;
import ui.entities.ISolution;
import ui.entities.IState;
import ui.entities.ITask;

public class UISpaceStateProblemSolver<T extends IState> implements Runnable {

    private ITask<T> task;
    private volatile boolean resolved;

    public UISpaceStateProblemSolver(ITask<T> task) {
        this.task = task;
        resolved = false;
    }

    public synchronized boolean isResolved() {
        return resolved;
    }

    public ISolution solve() {
        if (task.getInitialState() == null) {
            resolved = true;
            return new Solution<T>();
        }

        PriorityQueue<T> openStates = new PriorityQueue<T>(new ComparatorState());
        PriorityQueue<T> closedStates = new PriorityQueue<T>(new ComparatorState());

        openStates.add(task.getInitialState());
        while (!openStates.isEmpty()) {
            T currentState = openStates.poll();

            if (task.IsSolution(currentState)) {
                resolved = true;
                return new Solution<T>(makeSolutionWay(task.getInitialState(), currentState));
            }
            List<T> expandList = (List<T>) currentState.expand();
            for (T s : expandList) {
                if (!openStates.contains(s) && !closedStates.contains(s)) {
                    openStates.add(s);
                } else if (openStates.contains(s)) {
                    if (s.compareTo(openStates.get(s)) < 0) {
                        openStates.remove(openStates.get(s));
                        openStates.add(s);
                    }
                }
            }
            closedStates.add(currentState);
        }
        resolved = true;
        return new Solution<T>();
    }

    private List<T> makeSolutionWay(T startState, T currentState) {
        List<T> solutionWay = new ArrayList<T>();
        T current = currentState;
        while (current.hasParent()) {
            solutionWay.add(0, current);
            current = (T) current.getParent();
        }
        solutionWay.add(0, startState);
        return solutionWay;
    }

    @Override
    public void run() {
        solve();
    }
}