Problem

The adder.problem module is likely to be the first module to import in your Adder-based application. Here's why.

Our job as programmers is basically to:

1. Model a real-world problem.
2. Describe that model in code.
3. Design and implement an algorithm for solving that model.

Let's go abstract. What does a problem consist of? Usually, a problem asks for a set of variables for which a certain condition holds. Here are some examples:

• Problem: How do I make an omelette du fromage?
  Solution condition: A sequence of actions that result in a ready to be consumed omelette.
  Solution: Open the fridge, Take eggs and cheese, Crack the eggs into a bowl, Beat the eggs, Turn the cooker on, Put everything in a frying pan, cook for 10minutes, Serve

• Problem: What is the shortest path from NYC to LA?
  Solution condition: A sequence of cities c1, c2, ..., cN such that:
      1. c1 == NYC
      2. cN == LA
      3. The sum of the distance between each c_i and c_(i + 1) is less than the sum of distances of any other sequence.
  Solution: NYC, Colorado, Denver, central Utah, LA (according to this post)

Search space

One way we can define any model is to by using states and actions. A state represents the values of all variables in the problem - "Eggs are cracked, fridge is closed, cooker is off" may be a state of our first problem. An action is a way to change the current state and transit into another state. The action "Crack the eggs" executed in the state "Eggs are uncracked" causes a transition to the state "Eggs are cracked".

If the problem at hand is described with this approach, here's a simple algorithm that can solve it:

1. Start from the initial state.
2. Try to apply any of the possible actions we can do.
3. See if we've reached our goal. If that's the case, we are done.
4. Else, go to step 1.

Here's an example solution for the first problem:

State	Goal	Available actions	Last Taken Action
You standing in the room with eggs and cheese in the fridge.	Make an omelette	Open the fridge, Turn the cooker on	-
You standing in the room with eggs and cheese in the open fridge	Make an omelette	Take eggs, Turn the cooker on	Open Fridge
You standing in the room with eggs and cheese in hand	Make an omelette	Crack eggs, Turn the cooker on	Take eggs and cheese
Eggs cracked in a bowl	Make an omelette	Beat eggs, Turn the cooker on	Crack eggs
Eggs beaten in the bowl	Make an omelette	Turn the cooker on	Beat eggs
Eggs beaten in the bowl, cooker turned on	Make an omelette	Put everything in a frying pan	Turn the cooker on
Frying pan on the cooker, full of eggs and cheese	Make an omelette	Wait then serve	Put everything in a frying pan
Omelette done	Make an omelette	-	Wait then serve

Note how the different actions we took changed the current state of the problem. Also note that we could've selected the action Turn the cooker on even on step 1 but that would not have been beneficial. There are also some actions that aren't considered - for instance we could've thrown the eggs out of the window.

The pattern we need to follow to model our problems go like this:

• Describe the initial state.
• Describe the possible actions in each state.
• For each state and each action in that state, describe how to compute the resultant state.
• Try the available actions starting from the initial state until we've reached the goal.

Here's the same thing done in code:

import adder.problem as problem

class OmeletteProblem(problem.Problem): # Inherit from problem.Problem
    def __init__(self):
        self.initialState = "You standing in the room"
        
    # A method that returns an iterator with all the actions available from the given state
    def actions_iter(self, state): 
        if state == self.initialState:
            return iter(["Open fridge", "Turn cooker on"])
        ....
     
    # Returns the state our problem will be in after executing the given action in the given state   
    def result(self, state, action):
        if state == self.initialState:
            if action == "Open fridge":
                return "You standing in the room with eggs and cheese in the *open* fridge"
            elif action == "Turn cooker on"
                return "You standing in the room with eggs and cheese in the fridge and the cooker turned on"
        ...

    # Returns true if the given state is a goal state
    def goal_test(self, state):
        return state == "Omelette done"
    
    # Returns the cost for executing the given action in the given state
    def step_cost(self, state, action):
        return 1

Of course the above implementation is incredibly naive. You are much better using an enumeration for the states or any other data structure than a plain string.

There's an additional method that we did not discuss - the step_cost. Usually, an action takes some time (or money / other resources) to be completed - beating the eggs might be twice as slow as cracking them. For simplicity all actions in the example cost 1 unit of time.

The adder.search module provides facilities for solving problems described in this fashion. It also tries to minimize the total cost (the sum of all step_costs).

There are a few ready to use problems that can be used from the adder.problem module. The one you'll find using most certainly is the graph problem - given a weighted (di)graph find the shortest path between two nodes. To create a graph problem use the ProblemFactor singleton:

from adder.problem import ProblemFactory

problem = ProblemFactory.from_graph(graph, start, goal)

You can also take a look at the adder.graph module which has utilities for loading / saving graphs from / to files. The /data folder contains several examples including incomplete maps of Bulgaria, Romania and Germany.

Now go read the wiki page on Search module to see how to solve these tasks.