Created
May 1, 2018 18:56
-
-
Save MarcusAdriano/2933f7ea0af8f116c2605d0488bff2a9 to your computer and use it in GitHub Desktop.
IA A* algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package br.ufu.ml.ia; | |
| import br.ufu.util.Executors; | |
| import br.ufu.util.OrderedList; | |
| import java.util.Date; | |
| import java.util.LinkedList; | |
| import java.util.List; | |
| import java.util.Stack; | |
| public class AStar extends Algorithm { | |
| private final LinkedList<State> visitedList = new LinkedList<>(); | |
| private final OrderedList<Node<NodeData>> list = new OrderedList<>(); | |
| private final Stack<State> result = new Stack<>(); | |
| private final Object lock = new Object(); | |
| private final Object listLock = new Object(); | |
| private final Object visitedLock = new Object(); | |
| private final Object auxLock = new Object(); | |
| private int n = 10; | |
| private void aSearch() { | |
| Node<NodeData> auxNode; | |
| System.err.printf("Run A* at %s\n", Thread.currentThread().getName()); | |
| while (result.isEmpty()) { | |
| // retrieve the first element from list | |
| // and remove it, because it's the | |
| // lower cost f(n) | |
| synchronized (listLock) { | |
| auxNode = list.pollFirst(); | |
| } | |
| assert auxNode != null; | |
| // System.out.println(auxNode.getData().getState().toString()); | |
| if (isObjective(auxNode)) { | |
| synchronized (lock) { | |
| result.addAll(makeResult(auxNode)); | |
| lock.notify(); | |
| } | |
| break; | |
| } | |
| if (auxNode.getChildren().size() == 0) { | |
| synchronized (auxLock) { | |
| expand(auxNode); | |
| } | |
| } | |
| synchronized (visitedLock) { | |
| visitedList.add(auxNode.getData().getState()); | |
| } | |
| for(Node<NodeData> item : auxNode.getChildren()) { | |
| // verify if the item was visited | |
| if (visitedList.contains(item.getData().getState())) { | |
| continue; | |
| } | |
| // otherwise, add it on the list to be visited | |
| int dist = getAgent().h(item.getData().getState()); | |
| item.getData().setCoast(item.getHeight() + dist); | |
| synchronized (listLock) { | |
| list.add(item); | |
| } | |
| } | |
| // synchronized (lock) { | |
| // if (auxNode.getHeight() > 0 && auxNode.getHeight() % n == 0) { | |
| // System.err.printf("Node on height %d was reached. " + | |
| // "There are %d node(s) on list to be visited! Next node has f(n) = %d.\n", | |
| // n, list.size(), list.peekFirst().getData().getCoast()); | |
| // n += 10; | |
| // } | |
| // } | |
| } | |
| } | |
| private void clear() { | |
| list.clear(); | |
| visitedList.clear(); | |
| } | |
| @Override | |
| protected Stack<State> search() { | |
| // show initial state | |
| System.err.println("Initial State: \n" + getRoot().getData().getState()); | |
| long initialTime = new Date().getTime(); | |
| expand(getRoot()); | |
| list.add(getRoot()); | |
| list.addAll(getRoot().getChildren()); | |
| for (int i = 0; i < 4; i++) | |
| Executors.getInstance().getThreadPool().execute(this::aSearch); | |
| Executors.getInstance().getThreadPool().shutdown(); | |
| while (result.isEmpty()) { | |
| try { | |
| synchronized (lock) { | |
| lock.wait(); | |
| } | |
| } catch (InterruptedException e) { | |
| e.printStackTrace(); | |
| } | |
| } | |
| System.err.printf("Time in seconds: %d\n", | |
| (new Date().getTime() - initialTime) / 1000); | |
| return result; | |
| } | |
| @Override | |
| protected Stack<State> makeResult(Node<NodeData> node) { | |
| Stack<State> solutionQueue = new Stack<>(); | |
| while (node != null) { | |
| solutionQueue.add(node.getData().getState()); | |
| node = node.getParent(); | |
| } | |
| return solutionQueue; | |
| } | |
| @Override | |
| protected boolean isObjective(Node<NodeData> node) { | |
| boolean partialTest; | |
| for (State state : getAgent().getObjective()) { | |
| partialTest = state.isEquals(node.getData().getState()); | |
| if (partialTest) { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| @Override | |
| public void expand(Node<NodeData> parent) { | |
| List<Action> actionList = getAgent().getActionList(); | |
| for (Action action : actionList) { | |
| NodeData childData; | |
| try { | |
| childData = new NodeData(parent.getData(), action); | |
| parent.addChild(childData); | |
| } catch (ActionException ignore) { | |
| } | |
| } | |
| } | |
| @Override | |
| protected void setup() { | |
| // setup root for tree | |
| NodeData rootData = NodeData.newRoot(getAgent().getInitialState()); | |
| // tree | |
| setRoot(new Node<>(rootData)); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment