<jupyter_start><jupyter_text>The search.py module*Date: 14 March 2016*  IntroductionHello!    In this IPython notebook, we study different kinds of search techniques used in [ search.py ]( https://github.com/aimacode/aima-python/blob/master/search.py ) and try to get an intuition of what search algorithms are best suited for various problems. We first explore uninformed search algorithms and later get our hands on heuristic search strategies.    The code in this IPython notebook, and the entire aima-python repository is intended to work with Python 3 (specifically, Python 3.4). So if you happen to be working on Python 2, you should switch to Python 3. For more help on how to install python3, or if you are having other problems, you can always have a look the 'intro' IPython notebook. Now that you have all that sorted out, lets get started!  Uninformed Search Strategies Also called `blind search`, in such search strategies with all the information we have about any state all we can do is generate its successors and check whether it's a `goal state` or not. THAT'S IT. NOTHING MORE(Well ....not really. See the `value` method defined in the following section).First let's formulate the problem we intend to solve. So let's import everything from our module.<jupyter_code>from search import *<jupyter_output><empty_output><jupyter_text>The first thing we observe is '`from utils import *`'. This means that everything in utils.py is imported for use in this module. Don't worry. You don't need to read utils.py in order to understand search algorithms.    The `Problem` class is an abstract class on which we define our problems(*duh*).Again, if you are confused about what `abstract class` means have a look at the 'Intro' notebook.The `Problem` class has six methods.* `__init__(self, initial, goal)` : This is what is called a `constructor` and is the first method called when you create an instance of class. In this and all of the below methods `self` refers to the object itself- the object whose method is called. `initial` specifies the initial state of our search problem. It represents the start state from where our agent begins his task of exploration to find the goal state(s) which is given in the `goal` parameter.* `actions(self, state)` : This method returns all the possible actions our agent can make in state `state`.* `result(self, state, action)` : This returns the resulting state if action `action` is taken in the state `state`. This `Problem` class only deals with deterministic outcomes. So we know for sure what every action in a state would result to.* `goal_test(self, state)` : Given a graph state, it checks if it is a terminal state. If the state is indeed a goal state, value of `True` is returned. Else , ofcourse, `False` is returned.* `path_cost(self, c, state1, action, state2)` : Return the cost of the path that arrives at `state2` as a result of taking `action` from `state1`, assuming total cost of `c` to get up to `state1`.* `value(self, state)` : This acts as a bit of extra information in problems where we try to optimize a value when we cannot do a goal test. Now using the above abstract class as a parent there is another named called `GraphProblem` in our module. It creates a graph problem from an instance of the `Graph` class. To create a graph, simply do `graph = Graph(dict(...))`. The dictionary must contain nodes of the graph as keys, so make sure they are `hashable`. If you don't know what that means just use strings or numbers. Each node in the dictionary should correspond to another dictionary which contain the adjacent nodes as keys and the edge length as its value. The `Graph` class creates a directed(edges allow only one way traffic) by default.If you want to make an undirected graph, use `UndirectedGraph` instead, but make sure to mention any edge in only one of its nodes. If you didn't understand the above paragraph, `Fret not!`. Just think of the below code as a magicical method to create a simple undirected graph. I'll explain what it is about later.<jupyter_code>museum_graph = UndirectedGraph(dict(
    Start = dict(Dog = 3, Cat = 9, Mouse = 4),
    Dog = dict(Bear = 7),
    Cat = dict(Monkey = 9, Fish = 8, Penguin = 3),
    Mouse = dict(Penguin = 2),
    Bear = dict(Monkey = 7),
    Monkey = dict(Giraffe = 11, Fish = 6),
    Fish = dict(Giraffe = 8),
    Penguin = dict(Parrot = 4, Elephant = 6),
    Giraffe = dict(Hen = 5),
    Parrot = dict(Hen = 10),
    Elephant = dict(Hen = 9)))<jupyter_output><empty_output><jupyter_text>Suppose we are in a museum showcasing statues of various animals. To navigate through the museum there are paths between some statues and the entrance. We define the entrance and the statues as nodes in our graph with the path connecting them as edges. The cost/weight of an edge specifies its length. So `Start = dict(Dog = 3, Cat = 9, Mouse = 4)` means that there are paths from `Start` to `Dog`, `Cat` and `Mouse` with path costs 3, 9 and 4 respectively. See the image below to better understand the graph.   Breadth First Search In breadth first search the `shallowest` unexpanded node is chosen for expansion. That means that all nodes of a given depth must be expanded before any node of the next depth level. It accomplishes this by using a `FIFO` meaning 'First In First Out' queue. Any thing thats gets in the queue first also gets out first just like the checkout queue in a supermarket. To use the algorithm, first we need to define our problem. Say we want to find the statue of `Monkey` and we start from the entrance which is the `Start` state. We define our problem using the `GraphProblem` class.<jupyter_code>monkey_problem = GraphProblem('Start', 'Monkey', museum_graph)<jupyter_output><empty_output><jupyter_text>Now let's find the solution for our problem using the `breadth_first_search` method. Note that it returns a `Node` from which we can find the solution by looking at the path that was taken to reach there.<jupyter_code>bfs_node = breadth_first_search(monkey_problem)
bfs_node.solution()<jupyter_output><empty_output><jupyter_text>We get the output as `['Cat', 'Monkey']`. That is because first the nodes `Dog`, `Cat` and `Mouse` are added to the `FIFO` queue in `some` order when we are explanding the `Start` node. Now when we start expanding nodes in the next level, only the `Cat` node gets us to `Monkey`. Note that in breadth first search the goal test is done when it is being added to the queue.  Uniform-cost Search In uniform cost search instead of expanding the shallowest node we expand the node with the lowest path cost(cost to reach upto that node from the start). Instead of a `FIFO` queue we use something called a `priority queue` which selects the element with the highest `priority` of all elements in the queue. For our problem lower path cost means higher priority. Whenever we need to enqueue a node already in the queue we update its path cost if the newer path is better. This is a very important step and it means that the path cost to a node may keep getting better until it is selected for expansion. This is the reason that we do a goal check only when a node is selected for expanion.<jupyter_code>ucs_node = uniform_cost_search(monkey_problem)
ucs_node.solution()<jupyter_output><empty_output><jupyter_text>We got `['Dog', 'Bear', 'Monkey']` instead of `['Cat', 'Monkey']` because the path cost is lower! We can also see the path cost with the path_cost attribute. Lets compare the path cost of the Breadth first search solution and Uniform cost search solution<jupyter_code>bfs_node.path_cost, ucs_node.path_cost<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06588944197013362, 'fraction_numerical': 0.005501702908042965, 'mean_word_length': 4.552727272727273, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 25, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '638258', 'license': 'MIT', 'n_tokens_mistral': 2066, 'n_tokens_neox': 1967, 'n_words': 1172, 'path': 'search.ipynb', 'repo_name': 'lgmoneda/aima-python', 'size': '7634'}