notebooks/ClassicalSearch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Classical Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook serves as a supporting material for the chapter **Solving Problems by Searching**. The notebooks illustrate the use of the code repository and demonstrate how the code can be extended to solve various search related problems. The discussion of problem solving begins with a precise implementation of **problems** and their **solutions**. Then we move onto various **informed** and **uninformed** search strategies for solving problems."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a73b7822-0a54-4624-8bb1-162d723fc3db",
       "version_major": 2,
       "version_minor": 0
      },
      "method": "display_data"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%classpath add jar ../out/artifacts/aima_core_jar/aima-core.jar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Solving Agents\n",
    "\n",
    "The process of looking for a sequence of **actions** that reaches the **goal** is called **search**.\n",
    "A search algorithm takes a problem as input and returns a solution in the form of an action\n",
    "sequence. Once a solution is found, the actions it recommends can be carried out. This\n",
    "is called the execution phase. Thus, we have a simple “formulate, search, execute” design\n",
    "for the agent, as shown in Figure 3.1 of the textbook. After formulating a goal and a problem to solve,\n",
    "the agent calls a search procedure to solve it. It then uses the solution to guide its actions,\n",
    "doing whatever the solution recommends as the next thing to do—typically, the first action of\n",
    "the sequence—and then removing that step from the sequence. Once the solution has been\n",
    "executed, the agent will formulate a new goal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's have a look at the pseudocode of a simple problem solving agent and then see it's java implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### AIMA3e\n",
       "__function__ SIMPLE-PROBLEM-SOLVING-AGENT(_percept_) __returns__ an action  \n",
       "&emsp;__persistent__: _seq_, an action sequence, initially empty  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_state_, some description of the current world state  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_goal_, a goal, initially null  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_problem_, a problem formulation\n",
       "\n",
       "&emsp;_state_ &larr; UPDATE-STATE(_state_, _percept_)  \n",
       "&emsp;__if__ _seq_ is empty __then__  \n",
       "&emsp;&emsp;&emsp;_goal_ &larr; FORMULATE-GOAL(_state_)  \n",
       "&emsp;&emsp;&emsp;_problem_ &larr; FORMULATE-PROBLEM(_state_, _goal_)  \n",
       "&emsp;&emsp;&emsp;_seq_ &larr; SEARCH(_problem_)  \n",
       "&emsp;&emsp;&emsp;__if__ _seq_ = _failure_ __then return__ a null action  \n",
       "&emsp;_action_ &larr; FIRST(_seq_)  \n",
       "&emsp;_seq_ &larr; REST(_seq_)  \n",
       "&emsp;__return__ _action_  \n",
       "\n",
       "---\n",
       "__Figure__ ?? A simple problem-solving agent. It first formulates a goal and a problem, searches for a sequence of actions that would solve the problem, and then executes the actions one at a time. When this is complete, it formulates another goal and starts over."
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%python\n",
    "from notebookUtils import *\n",
    "pseudocode('Simple Problem Solving Agent')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The implementation of the above pseudocode can be viewed [here](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/agent/SimpleProblemSolvingAgent.java). This agent is implemented as an abstract agent which can be extended to construct other agents."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Well-defined problems and solutions\n",
    "We will first formally define a problem. Then, we will have a look at how the code from the repository can be used to formulate new problems. Then, we will have a look at various toy problems which are already present in the code repository.\n",
    "\n",
    "As per the textbook, a **problem** can be defined formally by five components. The initial state, applicable actions, the transition model, the goal test and the path cost function. This five component structure is implemented as an interface named [Problem.java](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/framework/problem/Problem.java) in the repository. Let's have a look at the implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "````java\n",
    "public interface Problem<S, A> extends OnlineSearchProblem<S, A> {\n",
    "\n",
    "    /**\n",
    "     * Returns the initial state of the agent.\n",
    "     */\n",
    "    S getInitialState();\n",
    "\n",
    "    /**\n",
    "     * Returns the description of the possible actions available to the agent.\n",
    "     */\n",
    "    List<A> getActions(S state);\n",
    "\n",
    "    /**\n",
    "     * Returns the description of what each action does.\n",
    "     */\n",
    "    S getResult(S state, A action);\n",
    "\n",
    "    /**\n",
    "     * Determines whether a given state is a goal state.\n",
    "     */\n",
    "    boolean testGoal(S state);\n",
    "\n",
    "    /**\n",
    "     * Returns the <b>step cost</b> of taking action <code>action</code> in state <code>state</code> to reach state\n",
    "     * <code>stateDelta</code> denoted by c(s, a, s').\n",
    "     */\n",
    "    double getStepCosts(S state, A action, S stateDelta);\n",
    "\n",
    "    /**\n",
    "     * Tests whether a node represents an acceptable solution. The default implementation\n",
    "     * delegates the check to the goal test. Other implementations could make use of the additional\n",
    "     * information given by the node (e.g. the sequence of actions leading to the node). A\n",
    "     * solution tester implementation could for example always return false and internally collect\n",
    "     * the paths of all nodes whose state passes the goal test. Search implementations should always\n",
    "     * access the goal test via this method to support solution acceptance testing.\n",
    "     */\n",
    "    default boolean testSolution(Node<S, A> node) {\n",
    "        return testGoal(node.getState());\n",
    "    }\n",
    "}\n",
    "````"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The states and actions are represented by the generic variables `S` and `A` respectively. Clearly, the methods represent the\n",
    "five components of a particular problem as follows:\n",
    "* initial state &larr; `getInitialState()`\n",
    "* applicable actions &larr; `getActions(S state)`\n",
    "* the transition model &larr; `getResult(S state, A action)`\n",
    "* the goal test &larr; `testGoal(S state)`\n",
    "* path cost function &larr; `getStepCosts(S state, A action, S stateDelta)`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example Problems\n",
    "\n",
    "A **toy problem** is intended to illustrate or exercise various problem solving methods. Let's extend the `Problem` interface to implement a toy problem. Let's implement the **8 puzzle problem** which consists of a 3x3 board with eight numbered tiles and a blank space. It has the following five components:\n",
    "* **States**: A state description specifies the location of each of the eight tiles and the blank in one of the nine squares.\n",
    "* **Initial state**: Any state can be designated as the initial state. Note that any given goal can be reached from exactly half of the possible initial states. (proved in Exercise 3.4)\n",
    "* **Actions**: The simplest formulation defines the actions as movements of the blank space Left, Right, Up, or Down. Different subsets of these are possible depending on where the blank is.\n",
    "* **Transition model**: Given a state and action, this returns the resulting state.\n",
    "* **Path cost**: Each step costs 1, so the path cost is the number of steps in the path.\n",
    "\n",
    "Let's look at the implementation:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we implement the states and actions applicable to the problem. The actions can be implemented as an enum whereas the states can be represented as an array of ints."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "aima.notebooks.classicalsearch.EightPuzzleProblem"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "package aima.notebooks.classicalsearch;\n",
    "\n",
    "import java.util.ArrayList;\n",
    "import java.util.Arrays;\n",
    "import java.util.List;\n",
    "import aima.core.search.framework.problem.Problem;\n",
    "\n",
    "public class EightPuzzleProblem implements Problem<int[], EightPuzzleProblem.Action> {\n",
    "\n",
    "    // This array represents the state\n",
    "    int[] initialState = new int[9];\n",
    "    \n",
    "    /**\n",
    "    * This enum represents the Action datatype\n",
    "    */\n",
    "    public enum Action {\n",
    "        LEFT, RIGHT, UP, DOWN\n",
    "    }\n",
    "    \n",
    "    // A constructor for the problem\n",
    "    public EightPuzzleProblem(int[] initialState){\n",
    "        this.initialState = initialState;\n",
    "    }\n",
    "\n",
    "    // Component One : The initial state.\n",
    "    @Override\n",
    "    public int[] getInitialState() {\n",
    "        return initialState;\n",
    "    }\n",
    "\n",
    "    // Component Two : Applicable Actions\n",
    "    @Override\n",
    "    public List<Action> getActions(int[] state) {\n",
    "        List<Action> actions = new ArrayList<>();\n",
    "        if (this.canMoveGap(state, Action.UP))\n",
    "            actions.add(Action.UP);\n",
    "        if (this.canMoveGap(state, Action.DOWN))\n",
    "            actions.add(Action.DOWN);\n",
    "        if (this.canMoveGap(state, Action.LEFT))\n",
    "            actions.add(Action.LEFT);\n",
    "        if (this.canMoveGap(state, Action.RIGHT))\n",
    "            actions.add(Action.RIGHT);\n",
    "        return actions;\n",
    "    }\n",
    "\n",
    "    // Component Three : Transition Model\n",
    "    @Override\n",
    "    public int[] getResult(int[] state, Action action) {\n",
    "        int[] result = state.clone();\n",
    "\n",
    "        if (Action.UP.equals(action) && canMoveGap(state, Action.UP))\n",
    "            moveGapUp(result);\n",
    "        else if (Action.DOWN.equals(action) && canMoveGap(state, Action.DOWN))\n",
    "            moveGapDown(result);\n",
    "        else if (Action.LEFT.equals(action) && canMoveGap(state, Action.LEFT))\n",
    "            moveGapLeft(result);\n",
    "        else if (Action.RIGHT.equals(action) && canMoveGap(state, Action.RIGHT))\n",
    "            moveGapRight(result);\n",
    "        return result;\n",
    "    }\n",
    "    \n",
    "    // Component Four : Goal Test\n",
    "    @Override\n",
    "    public boolean testGoal(int[] state) {\n",
    "        return Arrays.equals(state, new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8});\n",
    "    }\n",
    "\n",
    "    // Component Five : Path cost function\n",
    "    @Override\n",
    "    public double getStepCosts(int[] state, Action action, int[] stateDelta) {\n",
    "        return 1.0;\n",
    "    }\n",
    "\n",
    "    private void moveGapRight(int[] result) {\n",
    "        int gapPos = getGapPosition(result);\n",
    "        int x = gapPos / 3;\n",
    "        int y = gapPos % 3;\n",
    "        if (!(y == 2)) {\n",
    "            int valueOnRight = result[x * 3 + y + 1];\n",
    "            setValue(result, x, y, valueOnRight);\n",
    "            setValue(result, x, y + 1, 0);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // All the methods below are just helper methods which aid the above necessary methods.\n",
    "    \n",
    "    // To move the gap to the left.\n",
    "    private void moveGapLeft(int[] result) {\n",
    "        int gapPos = getGapPosition(result);\n",
    "        int x = gapPos / 3;\n",
    "        int y = gapPos % 3;\n",
    "        if (!(y == 0)) {\n",
    "            int valueOnLeft = result[x * 3 + (y - 1)];\n",
    "            setValue(result, x, y, valueOnLeft);\n",
    "            setValue(result, x, y - 1, 0);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // To move the gap to the cell below.\n",
    "    private void moveGapDown(int[] result) {\n",
    "        int gapPos = getGapPosition(result);\n",
    "        int x = gapPos / 3;\n",
    "        int y = gapPos % 3;\n",
    "        if (!(x == 2)) {\n",
    "            int valueOnBottom = result[(x + 1) * 3 + y];\n",
    "            setValue(result, x, y, valueOnBottom);\n",
    "            setValue(result, x + 1, y, 0);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // To get the current location of the gap\n",
    "    private int getGapPosition(int[] state) {\n",
    "        return getPositionOf(state, 0);\n",
    "    }\n",
    "\n",
    "    // To get the position of any particular number.\n",
    "    private int getPositionOf(int[] state, int val) {\n",
    "        for (int i = 0; i < 9; i++)\n",
    "            if (state[i] == val)\n",
    "                return i;\n",
    "        return -1;\n",
    "    }\n",
    "\n",
    "    // To check if we can move the gap to the position specified by where\n",
    "    public boolean canMoveGap(int[] state, Action where) {\n",
    "        boolean retVal = true;\n",
    "        int absPos = getPositionOf(state, 0);\n",
    "        if (where.equals(Action.LEFT))\n",
    "            retVal = (absPos % 3 != 0);\n",
    "        else if (where.equals(Action.RIGHT))\n",
    "            retVal = (absPos % 3 != 2);\n",
    "        else if (where.equals(Action.UP))\n",
    "            retVal = ((absPos / 3) != 0);\n",
    "        else if (where.equals(Action.DOWN))\n",
    "            retVal = ((absPos / 3) != 2);\n",
    "        return retVal;\n",
    "    }\n",
    "\n",
    "    // To move the gap to the cell above.\n",
    "    public void moveGapUp(int[] result) {\n",
    "        int gapPos = getGapPosition(result);\n",
    "        int x = gapPos / 3;\n",
    "        int y = gapPos % 3;\n",
    "        if (!(x == 0)) {\n",
    "            int valueOnTop = result[(x - 1) * 3 + y];\n",
    "            setValue(result, x, y, valueOnTop);\n",
    "            setValue(result, x - 1, y, 0);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // To set the value of a particular cell.\n",
    "    private void setValue(int[] result, int x, int y, int valueOnTop) {\n",
    "        int absPos = x *3 + y;\n",
    "        result[absPos] = valueOnTop;\n",
    "    }\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, in this way we can implement a Problem. Now let us see our problem class in action"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial State = [5, 4, 0, 6, 1, 8, 7, 3, 2]\n",
      "Available Actions = [DOWN, LEFT]\n",
      "Resulting State = [5, 4, 8, 6, 1, 0, 7, 3, 2]\n",
      "isGoal\tfalse\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.notebooks.classicalsearch.EightPuzzleProblem;\n",
    "import java.util.*;\n",
    "\n",
    "int [] initialState = new int[] { 5, 4, 0, 6, 1, 8, 7, 3, 2 };\n",
    "\n",
    "EightPuzzleProblem problem = new EightPuzzleProblem(initialState);\n",
    "\n",
    "System.out.println(\"Initial State = \" + Arrays.toString(problem.getInitialState()));\n",
    "System.out.println(\"Available Actions = \" + problem.getActions(initialState).toString());\n",
    "System.out.println(\"Resulting State = \" + Arrays.toString(problem.getResult(initialState,problem.getActions(initialState).get(0))));\n",
    "System.out.println(\"isGoal\\t\"+ problem.testGoal(initialState));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have seen how we can implement the existing problem interface to create and define our own custom problems. The flexibility to define our own custom problem is necessary for experimentation. However, the code repository already includes robust implementations of a variety of search problems and their environments. For all the future purposes we will use the existing implementations as they are more robust and complex and have been thoroughly tested for errors. Now let's have a look at some of the common search problems and how they can be directly used from the code repository."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [`GeneralProblem`](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/framework/problem/GeneralProblem.java) class can be used to create the existing problems. The problem parameters can be passed as constructor arguements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The Eight Puzzle Problem\n",
    "\n",
    "The eight puzzle problem can be constructed from the GeneralProblem class as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial State = [7, 1, 8, 0, 4, 6, 2, 3, 5]\n",
      "Available Actions = [Action[name=Up], Action[name=Down], Action[name=Right]]\n",
      "Resulting State = [0, 1, 8, 7, 4, 6, 2, 3, 5]\n",
      "isGoal\tfalse\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.environment.eightpuzzle.EightPuzzleBoard;\n",
    "import aima.core.environment.eightpuzzle.EightPuzzleFunctions;\n",
    "import aima.core.agent.Action;\n",
    "import aima.core.search.framework.problem.GoalTest;\n",
    "import aima.core.search.framework.problem.GeneralProblem;\n",
    "import aima.core.search.framework.problem.Problem;\n",
    "import java.util.*;\n",
    "\n",
    "\n",
    "EightPuzzleBoard board = new EightPuzzleBoard(new int[] { 7, 1, 8, 0, 4, 6, 2, 3, 5 });\n",
    "Problem<EightPuzzleBoard, Action> problem = new GeneralProblem<>(board, EightPuzzleFunctions::getActions,\n",
    "                                                                 EightPuzzleFunctions::getResult,\n",
    "                                                                 GoalTest.isEqual(EightPuzzleFunctions.GOAL_STATE));\n",
    "System.out.println(\"Initial State = \" + Arrays.toString(problem.getInitialState().getState()));\n",
    "System.out.println(\"Available Actions = \" + problem.getActions(problem.getInitialState()).toString());\n",
    "System.out.println(\"Resulting State = \" + Arrays.toString(problem.getResult(problem.getInitialState(),\n",
    "                                                                            problem.getActions(problem.getInitialState()).get(0))\n",
    "                                                          .getState()));\n",
    "System.out.println(\"isGoal\\t\"+ problem.testGoal(problem.getInitialState()));\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The NQueens Problem\n",
    "\n",
    "The goal of the **n-queens problem** is to place n-queens on an nxn chessboard such that no queens attacks any other. The n-queens problem can be formulated as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial State \n",
      "---\n",
      "---\n",
      "---\n",
      "\n",
      "Available Actions \n",
      "[Action[name=placeQueenAt, location=(0, 0)], Action[name=placeQueenAt, location=(0, 1)], Action[name=placeQueenAt, location=(0, 2)]]\n",
      "\n",
      "\n",
      "Resulting State \n",
      "Q--\n",
      "---\n",
      "---\n",
      "\n",
      "isGoal\tfalse\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.agent.Action;\n",
    "import aima.core.environment.nqueens.*;\n",
    "import aima.core.search.framework.problem.*;\n",
    "import java.util.*;\n",
    "\n",
    "Problem<NQueensBoard, QueenAction> problem = new GeneralProblem<>(new NQueensBoard(3),\n",
    "                                                                  NQueensFunctions::getIFActions,\n",
    "                                                                  NQueensFunctions::getResult, NQueensFunctions::testGoal);\n",
    "\n",
    "System.out.println(\"Initial State \\n\" + problem.getInitialState().toString());\n",
    "System.out.println(\"Available Actions \\n\" + problem.getActions(problem.getInitialState()).toString());\n",
    "System.out.println(\"\\n\\nResulting State \\n\" + problem.getResult(problem.getInitialState(),\n",
    "                                                                   problem.getActions(problem.getInitialState()).get(0)).toString());\n",
    "System.out.println(\"isGoal\\t\"+ problem.testGoal(problem.getInitialState()));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Route finding problem (Romania)\n",
    "Route-finding algorithms are used in a variety\n",
    "of applications. Some, such as Web sites and in-car systems that provide driving directions,\n",
    "are relatively straightforward extensions of the Romania example. Others, such as routing\n",
    "video streams in computer networks, military operations planning, and airline travel-planning\n",
    "systems, involve much more complex specifications. Now let us formulate the map of Romania Problem: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial State  Arad\n",
      "\n",
      "\n",
      "Available Actions \n",
      " [Action[name=moveTo, location=Sibiu], Action[name=moveTo, location=Timisoara], Action[name=moveTo, location=Zerind]]\n",
      "\n",
      "\n",
      "Resulting State  Sibiu\n",
      "\n",
      "\n",
      "isGoal\tfalse\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.environment.map.*;\n",
    "import aima.core.search.framework.problem.*;\n",
    "\n",
    "Map romaniaMap = new SimplifiedRoadMapOfPartOfRomania();\n",
    "Problem<String, MoveToAction> problem = new GeneralProblem<>(\n",
    "\t\t\t\tSimplifiedRoadMapOfPartOfRomania.ARAD,\n",
    "\t\t\t\tMapFunctions.createActionsFunction(romaniaMap),\n",
    "\t\t\t\tMapFunctions.createResultFunction(),\n",
    "\t\t\t\tGoalTest.isEqual(SimplifiedRoadMapOfPartOfRomania.BUCHAREST),\n",
    "\t\t\t\tMapFunctions.createDistanceStepCostFunction(romaniaMap));\n",
    "\n",
    "System.out.println(\"Initial State  \" + problem.getInitialState().toString());\n",
    "System.out.println(\"\\n\\nAvailable Actions \\n \" + problem.getActions(problem.getInitialState()).toString());\n",
    "System.out.println(\"\\n\\nResulting State  \" + problem.getResult(problem.getInitialState(),\n",
    "                                                                   problem.getActions(problem.getInitialState()).get(0)).toString());\n",
    "System.out.println(\"\\n\\nisGoal\\t\"+ problem.testGoal(problem.getInitialState()));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Search Algorithms\n",
    "Search algorithms work by considering various possible **action sequences**. The possible action sequences starting at the initial state form a **search tree** with the initial state at the root then **expanding** current state to form branches. The nodes correspond to states in the state space of the problem. We expand the current state by applying each legal action to the current state, thereby generating a new set of $b$ states. We add $b$ branches from the **parent node** leading to $b$ new **child node**. Each of these $b$ child nodes is a **leaf node**, that is, a node with no children in the tree. The set of all leaf nodes available  for expansion at any given point is called the **frontier**. The process of expanding nodes on the frontier continues until either a goal state is reached or there are no more states to expand. \n",
    "\n",
    "Node expansion in a tree can be visualized [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#node-expansion)\n",
    "\n",
    "Let's have a look at the pseudo code of general Tree Search algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### AIMA4e\n",
       "\n",
       "\n",
       "__function__ GENERIC-SEARCH(_problem_) __returns__ a solution, or failure  \n",
       "&emsp;_frontier_ &larr; a queue initially containing one path, for the _problem_'s initial state  \n",
       "&emsp;_reached_ &larr; a table of {_state_: the best path that reached _state_}; initially empty  \n",
       "&emsp;_solution_ &larr; failure  \n",
       "&emsp;__while__  _frontier_ is not empty __and__ _solution_ can possibly be improved __do__  \n",
       "&emsp;&emsp;&emsp;_parent_ &larr; some node that we choose to remove from _frontier_  \n",
       "&emsp;&emsp;&emsp;__for__ _child_ __in__ successors(_parent_) __do__   \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;_s_ &larr; _child_.state  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _s_ is not in _reached_  __or__ _child_ is a cheaper path than _reached_[_s_] __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_reached_[_s_] &larr; _child_  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;add _child_ to _frontier_  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _child_ is a goal and is cheaper than _solution_ __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_solution_  =  _child_  \n",
       "&emsp;__return__ _solution_\n",
       "\n",
       "---\n",
       "__Figure__ ?? In the GENERIC-SEARCH algorithm, we keep track of the best _solution_ found so far, as well as a set of states that we have already _reached_, and a _frontier_ of paths from which we will choose \n",
       "the next path to expand.\n",
       "In any specific search algorithm, we specify (1) the criteria for ordering the paths in the frontier,\n",
       "and (2) the procedure for determining when it is no longer possible to improve on a solution.\n",
       "\n",
       "# TREE-SEARCH and GRAPH-SEARCH\n",
       "## AIMA3e\n",
       "__function__ TREE-SEARCH(_problem_) __returns__ a solution, or failure  \n",
       "&emsp;initialize the frontier using the initial state of _problem_  \n",
       "&emsp;__loop do__  \n",
       "&emsp;&emsp;&emsp;__if__ the frontier is empty __then return__ failure  \n",
       "&emsp;&emsp;&emsp;choose a leaf node and remove it from the frontier  \n",
       "&emsp;&emsp;&emsp;__if__ the node contains a goal state __then return__ the corresponding solution  \n",
       "&emsp;&emsp;&emsp;expand the chosen node, adding the resulting nodes to the frontier  \n",
       "\n",
       "---\n",
       "__function__ GRAPH-SEARCH(_problem_) __returns__ a solution, or failure  \n",
       "&emsp;initialize the frontier using the initial state of _problem_  \n",
       "&emsp;**_initialize the explored set to be empty_**  \n",
       "&emsp;__loop do__  \n",
       "&emsp;&emsp;&emsp;__if__ the frontier is empty __then return__ failure  \n",
       "&emsp;&emsp;&emsp;choose a leaf node and remove it from the frontier  \n",
       "&emsp;&emsp;&emsp;__if__ the node contains a goal state __then return__ the corresponding solution  \n",
       "&emsp;&emsp;&emsp;**_add the node to the explored set_**  \n",
       "&emsp;&emsp;&emsp;expand the chosen node, adding the resulting nodes to the frontier  \n",
       "&emsp;&emsp;&emsp;&emsp;**_only if not in the frontier or explored set_**\n",
       "\n",
       "---\n",
       "__Figure__ ?? An informal description of the general tree\\-search and graph\\-search algorithms. The parts of GRAPH\\-SEARCH marked in bold italic are the additions needed to handle repeated states."
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%python\n",
    "from notebookUtils import *\n",
    "pseudocode('Tree Search and Graph Search')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Many a time newly generated states match previously generated states (known as a **repeated state**) and it leads to the generation of **redundant paths**. We avoid exploring a redundant path by augmenting the TREE-SEARCH algorithm with a data structure called **explored set** which remembers every expanded node. Clearly, the search tree constructed by the GRAPH-SEARCH algorithm contains at most one copy of each state.\n",
    "\n",
    "\n",
    "The perspective of a Search Agent can be visualized [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#search-agent)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Infrastructure for search algorithms\n",
    "As per textbook for each node $n$ of a tree, we have a structure that contains 4 components:\n",
    "These four component structure is implemented in a class named [node.java](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/framework/Node.java) in the repository. \n",
    "* \n",
    "````java\n",
    "private S state;````\n",
    "   `n.STATE`: The state in the state space to which the node corresponds;\n",
    "* \n",
    "````java\n",
    "private Node<S, A> parent;````\n",
    "   `n.PARENT`: The node in the search tree that generated this node;\n",
    "* \n",
    "````java\n",
    "private A action;````\n",
    "   `n.ACTION`: The action that was applied to the parent to generate the node;\n",
    "* \n",
    "````java\n",
    "private double pathCost;````\n",
    "   `n.PATH-COST`: The cost, traditionally denoted by g(n), of the path from the initial state to the node, as indicated by the parent pointers.\n",
    "\n",
    "These pointers also allow the solution path to be extracted when a goal node is found; we use SOLUTION function to return a sequence of actions obtained by following parent pointers back to the root.\n",
    "\n",
    "\n",
    "The  appropriate data-structure for frontier is **queue**. The operation on queue are as follows:\n",
    "* \n",
    "````java\n",
    "protected abstract void addToFrontier(Node<S, A> node);````\n",
    "   `INSERT(element,queue)`: A primitive operation which inserts the node at the tail of the frontier.\n",
    "* \n",
    "````java\n",
    "protected abstract Node<S, A> removeFromFrontier();````\n",
    "   `POP(queue)`: A primitive operation which removes and returns the node at the head of the frontier.\n",
    "* \n",
    "````java\n",
    "protected abstract boolean isFrontierEmpty()````\n",
    "   `EMPTY?(queue)`: A primitive operation which checks whether the frontier contains not yet expanded nodes.\n",
    "   \n",
    "   \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Uninformed Searches\n",
    "Uninformed Search (also called Blind Search) includes strategies that have no additional information about states beyond that provided in the problem definition. All these strategies can do is generate successor and distinguish goal state from a non-goal state.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Breadth First Search\n",
    "Breadth First Search is a simple search strategy in which all the nodes are expanded at a given depth before any nodes at the next level are expanded. Therefore, it always chooses the **shallowest unexpanded node** for expansion by using a **FIFO** queue for the `frontier`.\n",
    "Here goal test is applied to each node when it is _generated_ rather than when it is selected for expansion.\n",
    "\n",
    "Note that the _shallowest_ goal node is not necessarily the _optimal_ one. Therefore, breadth-first search is optimal if the path cost is a non-decreasing function of depth of the node.\n",
    "\n",
    "Working of Breadth First Search algorithm can be visualized [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#breadth-first-search).\n",
    "\n",
    "Let's have a look at the pseudo code of Breadth-First Search algorithm and then its implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### AIMA4e\n",
       "\n",
       "__function__ BREADTH-FIRST-SEARCH(_problem_) __returns__ a solution, or failure  \n",
       "&emsp;__if__ problem's initial state is a goal __then return__ empty path to initial state  \n",
       "&emsp;_frontier_ &larr; a FIFO queue initially containing one path, for the _problem_'s initial state  \n",
       "&emsp;_reached_ &larr; a set of states; initially empty  \n",
       "&emsp;_solution_ &larr; failure  \n",
       "&emsp;__while__  _frontier_ is not empty __do__  \n",
       "&emsp;&emsp;&emsp;_parent_ &larr; the first node in _frontier_  \n",
       "&emsp;&emsp;&emsp;__for__ _child_ __in__ successors(_parent_) __do__   \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;_s_ &larr; _child_.state  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _s_ is a goal  __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__return__  _child_  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _s_ is not in _reached_ __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;add _s_ to _reached_  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;add _child_ to the end of _frontier_  \n",
       "&emsp;__return__  _solution_\n",
       "\n",
       "---\n",
       "__Figure 3.9__ Breadth-first search algorithm.\n",
       "\n",
       "\n",
       "## AIMA3e\n",
       "__function__ BREADTH-FIRST-SEARCH(_problem_) __returns__ a solution, or failure  \n",
       "&emsp;_node_ &larr; a node with STATE = _problem_.INITIAL\\-STATE, PATH\\-COST = 0    \n",
       "&emsp;__if__ _problem_.GOAL\\-TEST(_node_.STATE) __then return__ SOLUTION(_node_)  \n",
       "&emsp;_frontier_ &larr; a FIFO queue with _node_ as the only element  \n",
       "&emsp;_explored_ &larr; an empty set  \n",
       "&emsp;__loop do__  \n",
       "&emsp;&emsp;&emsp;__if__ EMPTY?(_frontier_) __then return__ failure  \n",
       "&emsp;&emsp;&emsp;_node_ &larr; POP(_frontier_) /\\* chooses the shallowest node in _frontier_ \\*/  \n",
       "&emsp;&emsp;&emsp;add _node_.STATE to _explored_  \n",
       "&emsp;&emsp;&emsp;__for each__ _action_ __in__ _problem_.ACTIONS(_node_.STATE) __do__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_child_ &larr; CHILD\\-NODE(_problem_,_node_,_action_)  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _child_.STATE is not in _explored_ or _frontier_ __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _problem_.GOAL\\-TEST(_child_.STATE) __then return__ SOLUTION(_child_)  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_frontier_ &larr; INSERT(_child_,_frontier_)  \n",
       "\n",
       "---\n",
       "__Figure__ ?? Breadth\\-first search on a graph."
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%python\n",
    "from notebookUtils import *\n",
    "pseudocode('Breadth First Search')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optional[[Action[name=moveTo, location=Sibiu], Action[name=moveTo, location=Fagaras], Action[name=moveTo, location=Bucharest]]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.environment.map.*;\n",
    "import aima.core.search.framework.problem.*;\n",
    "import aima.core.search.uninformed.BreadthFirstSearch;\n",
    "\n",
    "Map romaniaMap = new SimplifiedRoadMapOfPartOfRomania();\n",
    "Problem<String, MoveToAction> problem = new GeneralProblem<>(\n",
    "\t\t\t\tSimplifiedRoadMapOfPartOfRomania.ARAD,\n",
    "\t\t\t\tMapFunctions.createActionsFunction(romaniaMap),\n",
    "\t\t\t\tMapFunctions.createResultFunction(),\n",
    "\t\t\t\tGoalTest.isEqual(SimplifiedRoadMapOfPartOfRomania.BUCHAREST),\n",
    "\t\t\t\tMapFunctions.createDistanceStepCostFunction(romaniaMap));\n",
    "\n",
    "BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch();\n",
    "System.out.println(breadthFirstSearch.findActions(problem));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optional[[parent=[parent=[parent=[parent=null, action=null, state=Arad, pathCost=0.0], action=Action[name=moveTo, location=Sibiu], state=Sibiu, pathCost=140.0], action=Action[name=moveTo, location=Fagaras], state=Fagaras, pathCost=239.0], action=Action[name=moveTo, location=Bucharest], state=Bucharest, pathCost=450.0]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.environment.map.*;\n",
    "import aima.core.search.framework.problem.*;\n",
    "import aima.core.search.framework.*;\n",
    "import aima.core.search.framework.qsearch.*;\n",
    "import java.util.Queue;\n",
    "\n",
    "\n",
    "QueueFactory queueFactory = new QueueFactory();\n",
    "Queue<Node> frontier ;\n",
    "\n",
    "Map romaniaMap = new SimplifiedRoadMapOfPartOfRomania();\n",
    "Problem<String, MoveToAction> problem = new GeneralProblem<>(\n",
    "\t\t\t\tSimplifiedRoadMapOfPartOfRomania.ARAD,\n",
    "\t\t\t\tMapFunctions.createActionsFunction(romaniaMap),\n",
    "\t\t\t\tMapFunctions.createResultFunction(),\n",
    "\t\t\t\tGoalTest.isEqual(SimplifiedRoadMapOfPartOfRomania.BUCHAREST),\n",
    "\t\t\t\tMapFunctions.createDistanceStepCostFunction(romaniaMap));\n",
    "\n",
    "GraphSearchBFS graphSearchBFS = new GraphSearchBFS();\n",
    "frontier = queueFactory.createFifoQueue();\n",
    "\n",
    "System.out.println(graphSearchBFS.findNode(problem, frontier));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Uniform Cost Search\n",
    "Instead of expanding the shallowest node, uniform cost search expand the node $n$ with the **lowest path cost** $g(n)$. This is done by storing the frontier as a **priority queue** ordered by $g$ . There are 2 significant differences from breadth-first search. The first is that goal test is applied to a node when it is _selected for expansion_. The second difference is that a test is added in case a better path is found to a node currently on the frontier.\n",
    "\n",
    "Uniform Cost Search does not care about the _number_ of steps a path has, but only about their _total cost_. Therefore, it expands nodes in order of their optimal path cost. Hence, the first goal node selected for expansion must be the optimal solution.\n",
    "\n",
    "The difference in the working of Breadth First search algorithm and Uniform Cost search algorithm can be visualized  [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#step-costs).\n",
    "\n",
    "Let's have a look at the pseudo code of uniform cost search and then its implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### AIMA4e  \n",
       "\n",
       "__function__ UNIFORM-COST-SEARCH(_problem_) __returns__ a solution, or failure  \n",
       "&emsp;__if__ problem's initial state is a goal __then return__ empty path to initial state  \n",
       "&emsp;_frontier_ &larr; a priority queue ordered by pathCost, with a node for the initial state  \n",
       "&emsp;_reached_ &larr; a table of {_state_: the best path that reached _state_}; initially empty  \n",
       "&emsp;_solution_ &larr; failure  \n",
       "&emsp;__while__  _frontier_ is not empty __and__ top(_frontier_) is cheaper than _solution_ __do__  \n",
       "&emsp;&emsp;&emsp;_parent_ &larr; pop(_frontier_)  \n",
       "&emsp;&emsp;&emsp;__for__ _child_ __in__ successors(_parent_) __do__   \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;_s_ &larr; _child_.state  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _s_ is not in _reached_  __or__ _child_ is a cheaper path than _reached_[_s_] __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_reached_[_s_] &larr; _child_  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;add _child_ to the _frontier_  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _child_ is a goal and is cheaper than _solution_ __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_solution_  =  _child_  \n",
       "&emsp;__return__ _solution_\n",
       "\n",
       "---\n",
       "__Figure 3.11__ Uniform-cost search on a graph. Finds optimal paths for problems with vary-\n",
       "ing step costs.\n",
       "\n",
       "\n",
       "## AIMA3e\n",
       "__function__ UNIFORM-COST-SEARCH(_problem_) __returns__ a solution, or failure  \n",
       "&emsp;_node_ &larr; a node with STATE = _problem_.INITIAL\\-STATE, PATH\\-COST = 0  \n",
       "&emsp;_frontier_ &larr; a priority queue ordered by PATH\\-COST, with _node_ as the only element  \n",
       "&emsp;_explored_ &larr; an empty set  \n",
       "&emsp;__loop do__  \n",
       "&emsp;&emsp;&emsp;__if__ EMPTY?(_frontier_) __then return__ failure  \n",
       "&emsp;&emsp;&emsp;_node_ &larr; POP(_frontier_) /\\* chooses the lowest\\-cost node in _frontier_ \\*/  \n",
       "&emsp;&emsp;&emsp;__if__ _problem_.GOAL\\-TEST(_node_.STATE) __then return__ SOLUTION(_node_)  \n",
       "&emsp;&emsp;&emsp;add _node_.STATE to _explored_  \n",
       "&emsp;&emsp;&emsp;__for each__ _action_ __in__ _problem_.ACTIONS(_node_.STATE) __do__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_child_ &larr; CHILD\\-NODE(_problem_,_node_,_action_)  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _child_.STATE is not in _explored_ or _frontier_ __then__   \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_frontier_ &larr; INSERT(_child_,_frontier_)  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__else if__ _child_.STATE is in _frontier_ with higher PATH\\-COST __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;replace that _frontier_ node with _child_  \n",
       "\n",
       "---\n",
       "__Figure__ ?? Uniform\\-cost search on a graph. The algorithm is identical to the general graph search algorithm in Figure ??, except for the use of a priority queue and the addition of an extra check in case a shorter path to a frontier state is discovered. The data structure for _frontier_ needs to support efficient membership testing, so it should combine the capabilities of a priority queue and a hash table."
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%python\n",
    "from notebookUtils import *\n",
    "pseudocode('Uniform Cost Search')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optional[[Action[name=moveTo, location=Sibiu], Action[name=moveTo, location=RimnicuVilcea], Action[name=moveTo, location=Pitesti], Action[name=moveTo, location=Bucharest]]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.environment.map.*;\n",
    "import aima.core.search.framework.problem.*;\n",
    "import aima.core.search.uninformed.UniformCostSearch;\n",
    "\n",
    "Map romaniaMap = new SimplifiedRoadMapOfPartOfRomania();\n",
    "Problem<String, MoveToAction> problem = new GeneralProblem<>(\n",
    "\t\t\t\tSimplifiedRoadMapOfPartOfRomania.ARAD,\n",
    "\t\t\t\tMapFunctions.createActionsFunction(romaniaMap),\n",
    "\t\t\t\tMapFunctions.createResultFunction(),\n",
    "\t\t\t\tGoalTest.isEqual(SimplifiedRoadMapOfPartOfRomania.BUCHAREST),\n",
    "\t\t\t\tMapFunctions.createDistanceStepCostFunction(romaniaMap));\n",
    "\n",
    "UniformCostSearch uniformCostSearch = new UniformCostSearch();\n",
    "System.out.println(uniformCostSearch.findActions(problem));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Depth First Search\n",
    "Depth First Search algorithm always expands the **deepest** node in the current frontier of the search tree. Depth First search uses a **LIFO queue** for frontier which means that the most recently generated node is chosen for expansion. The properties of depth-first search depend strongly on whether the tree search or graph search version is used. The graph search version, which avoids repeated states and redundant paths, is complete in finite state space because it will eventually expand every node. The tree search version, on the other hand, is _not complete_.\n",
    "\n",
    "Depth First Search algorithm  is implemented [here](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/uninformed/DepthFirstSearch.java) ans it's working can be visualized [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#depth-first-search)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Depth Limited Search\n",
    "\n",
    "The failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first search with a pre-determined depth limit $l$ i.e. nodes at depth $l$ are treated as if they have no successors. But unfortunately, it also introduces an additional source of incompleteness if the shallowest goal node is beyond the chosen depth limit.\n",
    "\n",
    "Let's have a look at its pseudo code. Notice that depth-limited search can terminate with 2 kinds of failure: the standard _failure_ value indicates no solution; the _cutoff_ value indicates no solution within the depth limit.\n",
    "\n",
    "This algorithm is implemented [here](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/uninformed/DepthLimitedSearch.java) and it's working can be visualized [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#depth-limited-search)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### AIMA4e  \n",
       "\n",
       "__function__ DEPTH-LIMITED-SEARCH(_problem_, _l_) __returns__ a solution, or failure, or cutoff  \n",
       "&emsp;_frontier_ &larr; a FIFO queue initially containing one path, for the _problem_'s initial state  \n",
       "&emsp;_solution_ &larr; failure  \n",
       "&emsp;__while__  _frontier_ is not empty __do__  \n",
       "&emsp;&emsp;&emsp;_parent_ &larr; pop(_frontier_)  \n",
       "&emsp;&emsp;&emsp;__if__ depth(_parent_) > l __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;_solution_ &larr; cutoff  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;__else__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__for__ _child_ __in__ successors(_parent_) __do__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _child_ is a goal __then__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__return__ _child_  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;add _child_ to __frontier__  \n",
       "&emsp;__return__  _solution_  \n",
       "\n",
       "---\n",
       "__Figure 3.14__ An implementation of depth-limited tree search. The algorithm has two dif-\n",
       "ferent ways to signal failure to find a solution: it returns failure when it has exhausted all\n",
       "paths and proved there is no solution at any depth, and returns cutoff to mean there might be\n",
       "a solution at a deeper depth than l. Note that this algorithm does not keep track of reached\n",
       "states, and thus might visit the same state multiple times on different paths.\n",
       "\n",
       "## AIMA3e\n",
       "__function__ DEPTH-LIMITED-SEARCH(_problem_,_limit_) __returns__ a solution, or failure/cutoff  \n",
       "&emsp;__return__ RECURSIVE\\-DLS(MAKE\\-NODE(_problem_.INITIAL\\-STATE),_problem_,_limit_)  \n",
       "\n",
       "__function__ RECURSIVE\\-DLS(_node_,_problem_,_limit_) __returns__ a solution, or failure/cutoff  \n",
       "&emsp;__if__ _problem_.GOAL-TEST(_node_.STATE) __then return__ SOLUTION(_node_)  \n",
       "&emsp;__else if__ _limit_ = 0 __then return__ _cutoff_  \n",
       "&emsp;__else__  \n",
       "&emsp;&emsp;&emsp;_cutoff\\_occurred?_ &larr; false  \n",
       "&emsp;&emsp;&emsp;__for each__ _action_ __in__ _problem_.ACTIONS(_node_.STATE) __do__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_child_ &larr; CHILD\\-NODE(_problem_,_node_,_action_)  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;_result_ &larr; RECURSIVE\\-DLS(_child_,_problem_,_limit_\\-1)  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__if__ _result_ = _cutoff_ __then__ _cutoff\\_occurred?_ &larr; true  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;__else if__ _result_ &ne; _failure_ __then return__ _result_  \n",
       "&emsp;&emsp;&emsp;__if__ _cutoff\\_occurred?_ __then return__ _cutoff_ __else return__ _failure_  \n",
       "\n",
       "---\n",
       "__Figure__ ?? A recursive implementation of depth\\-limited tree search."
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%python\n",
    "from notebookUtils import *\n",
    "pseudocode('Depth Limited Search')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterative Deepening Depth-First Search\n",
    "\n",
    "Iterative deepening search is often used in combination with depth-first search, that finds the **best depth limit**. It calls depth-first search with increasing depth limits until a goal is found. It is complete, optimal for unit step costs, has time complexity comparable to breadth-first search, and has linear space complexity.\n",
    "\n",
    "Iterative deepening search is analogous to breadth-first search as it explores a complete layer of new nodes at each iteration before going on to next layer. _In general, iterative deepening is the preferred uniform search method when the search space is large and the depth of solution is unknown._\n",
    "\n",
    "Working of Iterative deepening search can be visualized [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#iterative-deepening).\n",
    "\n",
    "Let's have a look at its pseudo code and implementation on Romania map problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### AIMA3e / AIMA4e\n",
       "__function__ ITERATIVE-DEEPENING-SEARCH(_problem_) __returns__ a solution, or failure  \n",
       "&emsp;__for__ _depth_ = 0 to &infin; __do__  \n",
       "&emsp;&emsp;&emsp;_result_ &larr; DEPTH\\-LIMITED\\-SEARCH(_problem_,_depth_)  \n",
       "&emsp;&emsp;&emsp;__if__ _result_ &ne; cutoff __then return__ _result_\n",
       "\n",
       "---\n",
       "__Figure__ ?? The iterative deepening search algorithm, which repeatedly applies depth\\-limited search with increasing limits. It terminates when a solution is found or if the depth\\-limited search returns _failure_, meaning that no solution exists."
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%python\n",
    "from notebookUtils import *\n",
    "pseudocode('Iterative Deepening Search')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optional[[Action[name=moveTo, location=Sibiu], Action[name=moveTo, location=Fagaras], Action[name=moveTo, location=Bucharest]]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.environment.map.*;\n",
    "import aima.core.search.framework.problem.*;\n",
    "import aima.core.search.uninformed.IterativeDeepeningSearch;\n",
    "\n",
    "Map romaniaMap = new SimplifiedRoadMapOfPartOfRomania();\n",
    "\n",
    "Problem<String, MoveToAction> problem = new GeneralProblem<>(\n",
    "        SimplifiedRoadMapOfPartOfRomania.ARAD,\n",
    "        MapFunctions.createActionsFunction(romaniaMap),\n",
    "        MapFunctions.createResultFunction(),\n",
    "        GoalTest.isEqual(SimplifiedRoadMapOfPartOfRomania.BUCHAREST),\n",
    "        MapFunctions.createDistanceStepCostFunction(romaniaMap));\n",
    "\n",
    "IterativeDeepeningSearch iterativeDeepeningSearch = new IterativeDeepeningSearch();\n",
    "System.out.println(iterativeDeepeningSearch.findActions(problem));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bidirectional Search\n",
    "\n",
    "The idea behind bidirectional search is to run two simultaneous searches: one forward from the initial state and the other backward from the goal, hoping that the two searches meet in the middle. This is implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect; if they do, a solution has been found. This can enormously reduce time complexity, but it is not always applicable and may require too much space.\n",
    "\n",
    "Working of Bidirectional search (using breadth-first search in both the directions) can be visualized [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#bi-directional-bfs) and this algorithm is implemented [here](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/framework/qsearch/BidirectionalSearch.java)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Informed Searches\n",
    "\n",
    "Informed Searches include strategies that use problem-specific knowledge beyond the definition of the problem itself. These strategies can find a solution more efficiently than uninformed strategies.\n",
    "\n",
    "The general approach we consider here is **Best-First search**. It is an instance of a general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an **evaluation function**,$f(n)$. **Heuristic functions** $h(n)$ are the most common form in which additional knowledge of the problem is imparted to the search algorithm. For now, we consider the heuristic function to be an arbitrary, non-negative, problem-specific functions, with one constraint: if $n$ is a goal node, then $h(n) = 0$. Most best-first algorithms include heuristic function $h(n)$ as a component of $f$.\n",
    "\n",
    "$h(n)$ = estimated cost of the cheapest path from the state at node $n$ to a goal state.\n",
    "\n",
    "Best-First Search algorithm is implemented [here](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/informed/BestFirstSearch.java)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Greedy Best-First Search\n",
    "\n",
    "This algorithm tries to expand the node that is closest to the goal. Thus, it evaluates node by using just the heuristic function; that is, $f(n) = h(n)$. This algorithm is not always optimal. However, it is \"greedy\" as at each step it tries to get as close to the goal as it can. Sometimes, this algorithm is incomplete even in a finite state space.\n",
    "\n",
    "Greedy best-first search algorithm is implemented [here](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/informed/GreedyBestFirstSearch.java). Let's use this algorithm to solve **8Puzzle Problem**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want to find the shortest solution, we need a heuristic function that never overestimates the number of steps to the goal (**admissible heuristic**). Therefore, here are 2 commonly used heuristic functions for this problem:\n",
    "\n",
    "* $h1$ = the number of misplaced tiles. $h1$ is admissible heuristic because it is clear that any tile that is out of place must be moved atleast once.\n",
    "\n",
    "* $h2$ = the sum of distances of tiles from their goal positions. As tiles cannot move along diagonals, the distance we will count is the sum of the horizontal and the vertical distances. This is sometimes called the **city block distance** or **Manhattan distance**.\n",
    "$h2$ is also admissible because all any move can do is move one tile one step closer to the goal.\n",
    "\n",
    "As expected, neither of these overestimates the true solution cost.\n",
    "\n",
    "Now, let's use Greedy Best-First Search algorithm to solve Eight Puzzle Problem. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current State = [1, 7, 4, 3, 0, 2, 6, 8, 5]  Misplaced Tiles Heuristic = 6.0  isGoal = false  Path length = 0  Action[name=Up]\n",
      "\n",
      "Current State = [1, 0, 4, 3, 7, 2, 6, 8, 5]  Misplaced Tiles Heuristic = 6.0  isGoal = false  Path length = 1  Action[name=Right]\n",
      "\n",
      "Current State = [1, 4, 0, 3, 7, 2, 6, 8, 5]  Misplaced Tiles Heuristic = 6.0  isGoal = false  Path length = 2  Action[name=Down]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 0, 6, 8, 5]  Misplaced Tiles Heuristic = 5.0  isGoal = false  Path length = 3  Action[name=Down]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 5, 6, 8, 0]  Misplaced Tiles Heuristic = 4.0  isGoal = false  Path length = 4  Action[name=Left]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 5, 6, 0, 8]  Misplaced Tiles Heuristic = 3.0  isGoal = false  Path length = 5  Action[name=Up]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 0, 5, 6, 7, 8]  Misplaced Tiles Heuristic = 2.0  isGoal = false  Path length = 6  Action[name=Up]\n",
      "\n",
      "Current State = [1, 0, 2, 3, 4, 5, 6, 7, 8]  Misplaced Tiles Heuristic = 1.0  isGoal = false  Path length = 7  Action[name=Left]\n",
      "\n",
      "Final State = [0, 1, 2, 3, 4, 5, 6, 7, 8]  Misplaced Tiles Heuristic = 0.0  isGoal = true  Path length = 8"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.agent.Action;\n",
    "import aima.core.environment.eightpuzzle.EightPuzzleBoard;\n",
    "import aima.core.environment.eightpuzzle.EightPuzzleFunctions;\n",
    "import aima.core.search.agent.SearchAgent;\n",
    "import aima.core.search.framework.Node;\n",
    "import aima.core.search.framework.SearchForActions;\n",
    "import aima.core.search.framework.problem.GeneralProblem;\n",
    "import aima.core.search.framework.problem.GoalTest;\n",
    "import aima.core.search.framework.problem.Problem;\n",
    "import aima.core.search.framework.qsearch.GraphSearch;\n",
    "import aima.core.search.informed.GreedyBestFirstSearch;\n",
    "\n",
    "import java.util.Arrays;\n",
    "import java.util.List;\n",
    "\n",
    "EightPuzzleBoard board = new EightPuzzleBoard(new int[] { 1 ,7 ,4 ,3 ,0 ,2 ,6 ,8 ,5 });\n",
    "Problem<EightPuzzleBoard, Action> problem = new GeneralProblem<>(board, \n",
    "                                                                 EightPuzzleFunctions::getActions,\n",
    "                                                                 EightPuzzleFunctions::getResult,\n",
    "                                                                 GoalTest.isEqual(EightPuzzleFunctions.GOAL_STATE));\n",
    "\n",
    "// By Misplaced Tiles Heuristic function (h1)\n",
    "\n",
    "\n",
    "int[] state = problem.getInitialState().getState();\n",
    "EightPuzzleFunctions eightPuzzleFunctions = new EightPuzzleFunctions();\n",
    "\n",
    "try {\n",
    "    SearchForActions<EightPuzzleBoard, Action> search = new GreedyBestFirstSearch<>(new GraphSearch<>(),\n",
    "            EightPuzzleFunctions.createMisplacedTileHeuristicFunction());\n",
    "    SearchAgent<EightPuzzleBoard, Action> agent = new SearchAgent<>(problem, search);\n",
    "    List<Action> actions = agent.getActions().subList(0, agent.getActions().size());\n",
    "    for (int i=0;i<actions.size();i++){\n",
    "        System.out.print(\"Current State = \" + Arrays.toString(state));\n",
    "        EightPuzzleBoard eightPuzzleBoard = new EightPuzzleBoard(state);\n",
    "        System.out.print(\"  Misplaced Tiles Heuristic = \" + eightPuzzleFunctions.createMisplacedTileHeuristicFunction().applyAsDouble(new Node<>(eightPuzzleBoard)));\n",
    "        System.out.print(\"  isGoal = \"+ problem.testGoal(eightPuzzleBoard));\n",
    "        System.out.print(\"  Path length = \" + i);\n",
    "        System.out.println(\"  \" + actions.get(i));\n",
    "        state = problem.getResult(eightPuzzleBoard, actions.get(i)).getState();\n",
    "        System.out.println();\n",
    "    }\n",
    "    EightPuzzleBoard eightPuzzleBoard = new EightPuzzleBoard(state);\n",
    "    System.out.print(\"Final State = \" + Arrays.toString(state));\n",
    "    System.out.print(\"  Misplaced Tiles Heuristic = \" + eightPuzzleFunctions.createMisplacedTileHeuristicFunction().applyAsDouble(new Node<>(eightPuzzleBoard)));\n",
    "    System.out.print(\"  isGoal = \"+ problem.testGoal(eightPuzzleBoard));\n",
    "    System.out.print(\"  Path length = \" + agent.getActions().size());\n",
    "} catch (Exception e) {\n",
    "    e.printStackTrace();\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current State = [1, 7, 4, 3, 0, 2, 6, 8, 5]   Manhattan Heuristic = 8.0   isGoal = false   Path length = 0   Action[name=Up]\n",
      "\n",
      "Current State = [1, 0, 4, 3, 7, 2, 6, 8, 5]   Manhattan Heuristic = 7.0   isGoal = false   Path length = 1   Action[name=Right]\n",
      "\n",
      "Current State = [1, 4, 0, 3, 7, 2, 6, 8, 5]   Manhattan Heuristic = 6.0   isGoal = false   Path length = 2   Action[name=Down]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 0, 6, 8, 5]   Manhattan Heuristic = 5.0   isGoal = false   Path length = 3   Action[name=Down]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 5, 6, 8, 0]   Manhattan Heuristic = 4.0   isGoal = false   Path length = 4   Action[name=Left]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 5, 6, 0, 8]   Manhattan Heuristic = 3.0   isGoal = false   Path length = 5   Action[name=Up]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 0, 5, 6, 7, 8]   Manhattan Heuristic = 2.0   isGoal = false   Path length = 6   Action[name=Up]\n",
      "\n",
      "Current State = [1, 0, 2, 3, 4, 5, 6, 7, 8]   Manhattan Heuristic = 1.0   isGoal = false   Path length = 7   Action[name=Left]\n",
      "\n",
      "Final State = [0, 1, 2, 3, 4, 5, 6, 7, 8]   Manhattan Heuristic = 0.0   isGoal = true   Path length = 8"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.agent.Action;\n",
    "import aima.core.environment.eightpuzzle.EightPuzzleBoard;\n",
    "import aima.core.environment.eightpuzzle.EightPuzzleFunctions;\n",
    "import aima.core.search.agent.SearchAgent;\n",
    "import aima.core.search.framework.Node;\n",
    "import aima.core.search.framework.SearchForActions;\n",
    "import aima.core.search.framework.problem.GeneralProblem;\n",
    "import aima.core.search.framework.problem.GoalTest;\n",
    "import aima.core.search.framework.problem.Problem;\n",
    "import aima.core.search.framework.qsearch.GraphSearch;\n",
    "import aima.core.search.informed.GreedyBestFirstSearch;\n",
    "\n",
    "import java.util.Arrays;\n",
    "import java.util.List;\n",
    "\n",
    "EightPuzzleBoard board = new EightPuzzleBoard(new int[] { 1 ,7 ,4 ,3 ,0 ,2 ,6 ,8 ,5 });\n",
    "Problem<EightPuzzleBoard, Action> problem = new GeneralProblem<>(board, \n",
    "                                                                 EightPuzzleFunctions::getActions,\n",
    "                                                                 EightPuzzleFunctions::getResult,\n",
    "                                                                 GoalTest.isEqual(EightPuzzleFunctions.GOAL_STATE));\n",
    "\n",
    "// By Manhattan Heuristic function (h2)\n",
    "\n",
    "int[] state = problem.getInitialState().getState();\n",
    "EightPuzzleFunctions eightPuzzleFunctions = new EightPuzzleFunctions();\n",
    "\n",
    "try {\n",
    "    SearchForActions<EightPuzzleBoard, Action> search = new GreedyBestFirstSearch<>(new GraphSearch<>(),\n",
    "            EightPuzzleFunctions.createManhattanHeuristicFunction());\n",
    "    SearchAgent<EightPuzzleBoard, Action> agent = new SearchAgent<>(problem, search);\n",
    "    List<Action> actions = agent.getActions().subList(0, agent.getActions().size());\n",
    "    for (int i=0;i<actions.size();i++){\n",
    "        System.out.print(\"Current State = \" + Arrays.toString(state));\n",
    "        EightPuzzleBoard eightPuzzleBoard = new EightPuzzleBoard(state);\n",
    "        System.out.print(\"   Manhattan Heuristic = \" + eightPuzzleFunctions.createManhattanHeuristicFunction().applyAsDouble(new Node<>(eightPuzzleBoard)));\n",
    "        System.out.print(\"   isGoal = \"+ problem.testGoal(eightPuzzleBoard));\n",
    "        System.out.print(\"   Path length = \" + i);\n",
    "        System.out.println(\"   \" + actions.get(i));\n",
    "        state = problem.getResult(eightPuzzleBoard, actions.get(i)).getState();\n",
    "        System.out.println();\n",
    "    }\n",
    "    EightPuzzleBoard eightPuzzleBoard = new EightPuzzleBoard(state);\n",
    "    System.out.print(\"Final State = \" + Arrays.toString(state));\n",
    "    System.out.print(\"   Manhattan Heuristic = \" + eightPuzzleFunctions.createManhattanHeuristicFunction().applyAsDouble(new Node<>(eightPuzzleBoard)));\n",
    "    System.out.print(\"   isGoal = \"+ problem.testGoal(eightPuzzleBoard));\n",
    "    System.out.print(\"   Path length = \" + agent.getActions().size());\n",
    "} catch (Exception e) {\n",
    "    e.printStackTrace();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  A* Search: Minimizing the total estimated solution cost\n",
    "\n",
    "This algorithm evaluates node by combining $g(n)$, the cost to reach the node, and $h(n)$, the cost to get from the node to the goal:\n",
    "\n",
    "$f(n) = g(n) + h(n)$\n",
    "\n",
    "Since $g(n)$ gives the path cost from the start node to the node $n$, and $h(n)$ is the estimated cost of the cheapest path from $n$ to the goal, we have **$f(n)$ = estimated cost of the cheapest solution through n** . A$*$ search is both complete and optimal, provided that $h(n)$ is admissible (for TREE SEARCH) or consistent (for GRAPH SEARCH). The algorithm is identical to UNIFORM-COST SEARCH except that A$*$ uses $g+h$ instead of $g$.\n",
    "\n",
    "**Whenever A* selects a node for expansion, the optimal path to that node has been found.** \n",
    "\n",
    "A$*$ algorithm is implemented [here](https://github.com/aimacode/aima-java/blob/AIMA3e/aima-core/src/main/java/aima/core/search/informed/AStarSearch.java) and it can be vizualised [here](http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#aStarSearchBox).\n",
    "Now, let's solve **8Puzzle Problem** using A$*$ algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current State = [1, 7, 4, 3, 0, 2, 6, 8, 5]  Misplaced Tiles Heuristic = 6.0  isGoal = false  Path length = 0  Action[name=Up]\n",
      "\n",
      "Current State = [1, 0, 4, 3, 7, 2, 6, 8, 5]  Misplaced Tiles Heuristic = 6.0  isGoal = false  Path length = 1  Action[name=Right]\n",
      "\n",
      "Current State = [1, 4, 0, 3, 7, 2, 6, 8, 5]  Misplaced Tiles Heuristic = 6.0  isGoal = false  Path length = 2  Action[name=Down]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 0, 6, 8, 5]  Misplaced Tiles Heuristic = 5.0  isGoal = false  Path length = 3  Action[name=Down]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 5, 6, 8, 0]  Misplaced Tiles Heuristic = 4.0  isGoal = false  Path length = 4  Action[name=Left]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 5, 6, 0, 8]  Misplaced Tiles Heuristic = 3.0  isGoal = false  Path length = 5  Action[name=Up]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 0, 5, 6, 7, 8]  Misplaced Tiles Heuristic = 2.0  isGoal = false  Path length = 6  Action[name=Up]\n",
      "\n",
      "Current State = [1, 0, 2, 3, 4, 5, 6, 7, 8]  Misplaced Tiles Heuristic = 1.0  isGoal = false  Path length = 7  Action[name=Left]\n",
      "\n",
      "Final State = [0, 1, 2, 3, 4, 5, 6, 7, 8]  Misplaced Tiles Heuristic = 0.0  isGoal = true  Path length = 8"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.environment.eightpuzzle.EightPuzzleBoard;\n",
    "import aima.core.environment.eightpuzzle.EightPuzzleFunctions;\n",
    "import aima.core.agent.Action;\n",
    "import aima.core.search.agent.SearchAgent;\n",
    "import aima.core.search.framework.Node;\n",
    "import aima.core.search.framework.SearchForActions;\n",
    "import aima.core.search.framework.problem.GoalTest;\n",
    "import aima.core.search.framework.problem.GeneralProblem;\n",
    "import aima.core.search.framework.problem.Problem;\n",
    "import aima.core.search.framework.qsearch.GraphSearch;\n",
    "import aima.core.search.informed.AStarSearch;\n",
    "\n",
    "import java.util.*;\n",
    "\n",
    "\n",
    "EightPuzzleBoard board = new EightPuzzleBoard(new int[] { 1 ,7 ,4 ,3 ,0 ,2 ,6 ,8 ,5 });\n",
    "Problem<EightPuzzleBoard, Action> problem = new GeneralProblem<>(board, \n",
    "                                                                 EightPuzzleFunctions::getActions,\n",
    "                                                                 EightPuzzleFunctions::getResult,\n",
    "                                                                 GoalTest.isEqual(EightPuzzleFunctions.GOAL_STATE));\n",
    "\n",
    "int[] state = problem.getInitialState().getState();\n",
    "EightPuzzleFunctions eightPuzzleFunctions = new EightPuzzleFunctions();\n",
    "\n",
    "// By Misplaced Tiles Heuristic function\n",
    "\n",
    "try {\n",
    "    SearchForActions<EightPuzzleBoard, Action> search = new AStarSearch<>(new GraphSearch<>(),\n",
    "            EightPuzzleFunctions.createMisplacedTileHeuristicFunction());\n",
    "    SearchAgent<EightPuzzleBoard, Action> agent = new SearchAgent<>(problem, search);\n",
    "    List<Action> actions = agent.getActions().subList(0, agent.getActions().size());\n",
    "    for (int i=0;i<actions.size();i++){\n",
    "        System.out.print(\"Current State = \" + Arrays.toString(state));\n",
    "        EightPuzzleBoard eightPuzzleBoard = new EightPuzzleBoard(state);\n",
    "        System.out.print(\"  Misplaced Tiles Heuristic = \" + eightPuzzleFunctions.createMisplacedTileHeuristicFunction().applyAsDouble(new Node<>(eightPuzzleBoard)));\n",
    "        System.out.print(\"  isGoal = \"+ problem.testGoal(eightPuzzleBoard));\n",
    "        System.out.print(\"  Path length = \" + i);\n",
    "        System.out.println(\"  \" + actions.get(i));\n",
    "        state = problem.getResult(eightPuzzleBoard, actions.get(i)).getState();\n",
    "        System.out.println();\n",
    "    }\n",
    "    EightPuzzleBoard eightPuzzleBoard = new EightPuzzleBoard(state);\n",
    "    System.out.print(\"Final State = \" + Arrays.toString(state));\n",
    "    System.out.print(\"  Misplaced Tiles Heuristic = \" + eightPuzzleFunctions.createMisplacedTileHeuristicFunction().applyAsDouble(new Node<>(eightPuzzleBoard)));\n",
    "    System.out.print(\"  isGoal = \"+ problem.testGoal(eightPuzzleBoard));\n",
    "    System.out.print(\"  Path length = \" + agent.getActions().size());\n",
    "} catch (Exception e) {\n",
    "    e.printStackTrace();\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current State = [1, 7, 4, 3, 0, 2, 6, 8, 5]   Manhattan Heuristic = 8.0   isGoal = false   Path length = 0   Action[name=Up]\n",
      "\n",
      "Current State = [1, 0, 4, 3, 7, 2, 6, 8, 5]   Manhattan Heuristic = 7.0   isGoal = false   Path length = 1   Action[name=Right]\n",
      "\n",
      "Current State = [1, 4, 0, 3, 7, 2, 6, 8, 5]   Manhattan Heuristic = 6.0   isGoal = false   Path length = 2   Action[name=Down]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 0, 6, 8, 5]   Manhattan Heuristic = 5.0   isGoal = false   Path length = 3   Action[name=Down]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 5, 6, 8, 0]   Manhattan Heuristic = 4.0   isGoal = false   Path length = 4   Action[name=Left]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 7, 5, 6, 0, 8]   Manhattan Heuristic = 3.0   isGoal = false   Path length = 5   Action[name=Up]\n",
      "\n",
      "Current State = [1, 4, 2, 3, 0, 5, 6, 7, 8]   Manhattan Heuristic = 2.0   isGoal = false   Path length = 6   Action[name=Up]\n",
      "\n",
      "Current State = [1, 0, 2, 3, 4, 5, 6, 7, 8]   Manhattan Heuristic = 1.0   isGoal = false   Path length = 7   Action[name=Left]\n",
      "\n",
      "Final State = [0, 1, 2, 3, 4, 5, 6, 7, 8]   Manhattan Heuristic = 0.0   isGoal = true   Path length = 8"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import aima.core.environment.eightpuzzle.EightPuzzleBoard;\n",
    "import aima.core.environment.eightpuzzle.EightPuzzleFunctions;\n",
    "import aima.core.agent.Action;\n",
    "import aima.core.search.agent.SearchAgent;\n",
    "import aima.core.search.framework.Node;\n",
    "import aima.core.search.framework.SearchForActions;\n",
    "import aima.core.search.framework.problem.GoalTest;\n",
    "import aima.core.search.framework.problem.GeneralProblem;\n",
    "import aima.core.search.framework.problem.Problem;\n",
    "import aima.core.search.framework.qsearch.GraphSearch;\n",
    "import aima.core.search.informed.AStarSearch;\n",
    "\n",
    "import java.util.*;\n",
    "\n",
    "\n",
    "EightPuzzleBoard board = new EightPuzzleBoard(new int[] { 1 ,7 ,4 ,3 ,0 ,2 ,6 ,8 ,5 });\n",
    "Problem<EightPuzzleBoard, Action> problem = new GeneralProblem<>(board, \n",
    "                                                                 EightPuzzleFunctions::getActions,\n",
    "                                                                 EightPuzzleFunctions::getResult,\n",
    "                                                                 GoalTest.isEqual(EightPuzzleFunctions.GOAL_STATE));\n",
    "\n",
    "int[] state = problem.getInitialState().getState();\n",
    "EightPuzzleFunctions eightPuzzleFunctions = new EightPuzzleFunctions();\n",
    "\n",
    "// By Manhattan Heuristic function\n",
    "\n",
    "try {\n",
    "    SearchForActions<EightPuzzleBoard, Action> search = new AStarSearch<>(new GraphSearch<>(),\n",
    "            EightPuzzleFunctions.createManhattanHeuristicFunction());\n",
    "    SearchAgent<EightPuzzleBoard, Action> agent = new SearchAgent<>(problem, search);\n",
    "    List<Action> actions = agent.getActions().subList(0, agent.getActions().size());\n",
    "    for (int i=0;i<actions.size();i++){\n",
    "        System.out.print(\"Current State = \" + Arrays.toString(state));\n",
    "        EightPuzzleBoard eightPuzzleBoard = new EightPuzzleBoard(state);\n",
    "        System.out.print(\"   Manhattan Heuristic = \" + eightPuzzleFunctions.createManhattanHeuristicFunction().applyAsDouble(new Node<>(eightPuzzleBoard)));\n",
    "        System.out.print(\"   isGoal = \"+ problem.testGoal(eightPuzzleBoard));\n",
    "        System.out.print(\"   Path length = \" + i);\n",
    "        System.out.println(\"   \" + actions.get(i));\n",
    "        state = problem.getResult(eightPuzzleBoard, actions.get(i)).getState();\n",
    "        System.out.println();\n",
    "    }\n",
    "    EightPuzzleBoard eightPuzzleBoard = new EightPuzzleBoard(state);\n",
    "    System.out.print(\"Final State = \" + Arrays.toString(state));\n",
    "    System.out.print(\"   Manhattan Heuristic = \" + eightPuzzleFunctions.createManhattanHeuristicFunction().applyAsDouble(new Node<>(eightPuzzleBoard)));\n",
    "    System.out.print(\"   isGoal = \"+ problem.testGoal(eightPuzzleBoard));\n",
    "    System.out.print(\"   Path length = \" + agent.getActions().size());\n",
    "} catch (Exception e) {\n",
    "    e.printStackTrace();\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "text/x-java",
   "file_extension": ".java",
   "mimetype": "",
   "name": "Java",
   "nbconverter_exporter": "",
   "version": "1.8.0_144"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}