Part -1 Search
Introduction
AIMA (Artificial Intelligence: A Modern Approach) might be the most successful textbook about AI. I take this course with Prof. Yixin Chen this semester. I am going to go through all the source code (Python) provided on the website and use them to finish my homework. Therefore, both for my personal referral purpose and for someone who might be interested in using that code, I write a very simple “practical guide to AIMA python source code” series here. Enjoy the magic of AI and Python!
Step 1, build the environment.
In this section, you will need three python files:
http://aima-python.googlecode.com/svn/trunk/agents.py
http://aima-python.googlecode.com/svn/trunk/search.py
http://aima-python.googlecode.com/svn/trunk/utils.py
Type:
python agents.py
and
python search.py
to make sure that you have all the packages like Image and Tk with your python. If you don’t have them, just download them. The general guideline is to use apt-get if possible. If you are not using Debian family OS, download the Python package and then use
python setup.py
at the python package folder.
Step 2, study the code — tree search
In order to use the code, we have to get familiar with the interface. Let’s get start from search.py and start from depth_first_tree_search (Line 130). The line reads:
def depth_first_tree_search(problem):
return tree_search(problem, Stack())
We all know that depth-first search uses Stack. Now let’s omit the technical detail about the implementation of Stack in util.py and check what the “problem” is.
Let’s move to Line 16 of search.py. Here is the definition of Problem class. Here __init__ just assigns the initial state. All functions like successor and goal_test are abstract. So, let’s take a look a concrete example. Let’s jump to Line 458, NQueenProblem. It’s a subclass of Problem. It defines the initial state, successor function, and goal_test function. Node that the function conflicted and conflict are for internal use only, there are not the essential part of a problem.
Here, by this case study, we at least know that we have to define a problem with
1. self.initial field which is the starting point for a problem.
2. A successor function which generate the successor state for a given state. We will study it carefully later.
3. A goal_test function which returns either False or True.
The initial is really trivial, we can just assign a initial state to it. Note that Python is a dynamic type language, so we don’t actually care about what type of state is. We will exam the type of state later, but now let’s assume that we know the type of state.
The successor function is really tricky. A straight-forward way to design a successor function will return all possible states in a list. But if you do that, you will get an “Too many values to unpack” error. The design here is actually very neat: instead of put a state in to the list, you can put a (action, state) tuple in to a list. [Line 88 of search.py, in
function expand(problem)
...
for (act, next) in problem.successor(self.state)
read this line and you will figure out the date structure to store the successors. The reason is also simple: we can trace the path easily if you record the action down at every expanding step.
Since we moved our eyes to the Node class, let's exam it carefully.
The constructor of Node is fairly simple. The path function will backtrack all the path to the root. We can modify the code of __repr__ here to print the action out if needed. If any search finally return a result in the form of Node, we can actually get everything we need from this Node, e.g., the path to the node, the action series to the node.
Based on the knowledge above, you can write your own problem model based on tree search. Now let's move on to graph search.
Step 3. Graph search.
The only difference between tree search and graph search is that in graph search, we have a fringe that stores the closed notes. As you might know, the fringe is implemented in hash table. In Python, there is a tiny technical point: List is not hash-able as it's mutable, Tuple and String are hash-able. Therefore, if you implement your state as a list, make sure to convert it to a tuple or string or a constant. Otherwise graph search will not be happy with this and complain about it.
If you want to use A* search, another point arises: heuristic function. Note that Line 211 reads:
def f(n):
return max(getattr(n, 'f', -infinity), n.path_cost + h(n))
here n is a Node instead of a State. Hence, if you want to get the state information and implement h, you have to use n.state to get the state information.
Step 4. build your application
Perhaps the best part to study the code is to write your own code to test it. Here are my implementations on eightpuzzle and three-missionaries three cannibals problem. The code is ugly and only for study purpose only. Please don't directly copy it to your homework.
Eightpuzzle.py
#!/usr/bin/python
from utils import *;
from search import *;
class EightPuzzle(Problem):
"""The problem of solving a eight puzzle problem """
def __init__(self, state):
self.initial = tuple(state)
def successor(self, state):
"""In the 8 puzzle problem, move the blank to other position."""
result = []
position = list(state).index(0)
for action, newposition in self.possible_position(position).iteritems():
new = list(state[:])
new[newposition], new[position] = new[position], new[newposition]
result.append((action, tuple(new)))
return result
def possible_position(self, position):
“”"return the possible position”"”
result = {};
col = position % 3;
row = position // 3;
if row != 2:
result['D'] = position +3
if col != 0:
result['L'] = position -1
if row != 0:
result['U'] = position -3
if col != 2:
result['R'] = position +1
return result
def goal_test(self, state):
if state[0] != 0:
return False
elif state[1] !=1:
return False
elif state[2] !=2:
return False
elif state[3] !=3:
return False
elif state[4] !=4:
return False
elif state[5] !=5:
return False
elif state[6] !=6:
return False
elif state[7] !=7:
return False
elif state[8] !=8:
return False
else:
return True
def h(self, node):
“”"Heuristic function”"”
temp=list(node.state)
sum=0
for x in range(8): # mahatten distance
sum = sum + abs(temp.index(x)-x)
return sum
def h2(self, node):
“”"bad h”"”
sum = 0
pos = 0
for x in node.state:
sum = sum + abs(x - pos)
pos = pos + 1
return sum
if (__name__==“__main__”):
# state = [1, 2, 3, 4, 5, 6, 7, 8, 0]
state = [7, 2, 4, 5, 0, 6, 8, 3, 1]
# state = (2, 6, 4, 7, 0, 3, 5, 8, 1)
instance = EightPuzzle(state)
# breadth_first_tree_search(instance)
# depth_first_tree_search(instance)
# breadth_first_graph_search(instance)
# print depth_first_graph_search(instance).path()
print astar_search(instance, instance.h).path()
Boat.py
#!/usr/bin/python
from utils import *;
from search import *;
“”"state is a tuple with (#m1, #m2, #s1, #s2, where_is_the_boat)”"”
class Boat(Problem):
def __init__(self, state):
self.initial = tuple(state)
self.N = state[0]
self.nodenum = 1
def successor(self, state):
result = []
symbol = state[4]*2 -1; # 0 => -1
action = 0
for x in (0, 1, 2):
for y in (0, 1, 2):
if x + y >= 1 and x + y <= 2:
new = (state[0] + symbol*x, state[1]-symbol*x, state[2] + symbol*y, state[3] - symbol*y, 1 - state[4])
if self.check(new):
result.append((action, new))
action = action + 1
self.nodenum = self.nodenum + action
print result
return result
def check(self, state):
for x in state[:-1]:
if x<0:
return False;
if state[0]!=0 and state[0] < state[2]: return False;
if state[1]!=0 and state[1] < state[3]: return False;
return True
def goal_test(self, state):
if state[0] == 0 and state[1] == self.N and state[2] == 0 and state[3] == self.N and state[4] ==1:
print state
return True
return False;
def h(self, node):
return 0
state=node.state
return state[0]
if (__name__==“__main__”):
state=[3, 0, 3, 0, 0]
instance = Boat(state)
# breadth_first_tree_search(instance)
# depth_first_tree_search(instance)
# breadth_first_graph_search(instance)
# depth_first_graph_search(instance)
astar_search(instance, instance.h)
print instance.nodenum
BTW, if you need to highlight your source code and convert it to HTML for example, one of the handy program is GNU source-highlight. I really love this.
bits, 那么, 对于一个输入, 某一位没被设置的概率是 
, 而我们一共有 
个独立不相关的 Hash 函数, 所以这一位保持为 
的概率应该是 
. 因此, 假如我们一直插入了 
个元素进来, 某一位是 
. 用 
减去它, 就是这一位是 
. 这个题目中, 