Solved–Lab #3– Solution

Description

In this lab, we will build the foundation for our later implementation of “Heuristic Search” (lecture to come). Below, you will see a listing of code for search functions of increasing levels of sophistication. Relatively to where we will be going over the next weo weeks, these functions are all basic building blocks.

Begin with a “starter” copy of file graphsearch_lab3.py and copy into it the function definitions shown below. While you do this, we will interrupt periodically in order to experiment and discuss the specifics of each function individually.

Exercise 1: Copy functions dfs_ and bfs_traverse, dfs_ and bfs_ search, dfs_ and bfs_search_path, and best_search_path.

Exercise 2: Only if you are done with Exercise 1, and you have a good understanding of

best_search_ path, attempt the definition of a related function best_ search_ALLpaths. This new function is to list not only the first solution path found, but list paths that are possible between a given start and goal node.

Credit for this lab: Work conscientiously on the exercises and sign up on this week’s signup sheet.

—

Code listing:

#graphsearch_lab3.py

• by Kerstin Voigt, Jan 2018, for lectures and lab on GRAPHSEARCH import random

#directed, acyclic graph of “nodes”

• example from Poole et.al. “Computational Intelligence” Oxford Univ Press,,

• 1998,pp. 117, 121

GRAPH = {‘o103’:[‘o109′,’ts’,’l2d3′],

‘o109’:[‘o111′,’o119’],

‘ts’:[‘mail’],

‘o111’:[],

‘mail’:[],

‘o119’:[‘store’,’o123′],

‘store’:[],

‘o123’:[‘o125′,’r123’],

‘o125’:[],

‘r123’:[],

‘l2d3’:[‘l2d1′,’l2d4’],

‘l2d1’:[‘l3d2′,’l2d2’],

‘l2d4’:[‘o109’],

‘l2d2’:[‘l2d4’],

‘l3d2’:[‘l3d3′,’l3d1’],

‘l3d3’:[],

‘l3d1’:[‘l3d3’]}

COST = {(‘o103′,’ts’):8, (‘o103′,’o109’):12, (‘o103′,’l2d3’):4,\ (‘ts’,’mail’):6,\

(‘o109′,’o111’):4, (‘o109′,’o119’):16,\

(‘o119′,’store’):7, (‘o119′,’o123’):9,\

(‘o123′,’r123’):4, (‘o123′,’o125’):4,\

(‘l2d1′,’l3d2’):3, (‘l2d1′,’l2d2’):6,\

(‘l2d2′,’l2d4’):3, (‘l2d3′,’l2d1’):4,\

(‘l2d3′,’l2d4’):7, (‘l2d4′,’o109’):7,\

(‘l3d2′,’l3d3’):6, (‘l3d2′,’l3d1’):4,\

(‘l3d1′,’l3d3’):8}

def dfs_traverse(start):

open = [start]

closed = []

while open != []:

nxt = open[0]

open = open[1:]

closed.append(nxt)

print nxt

succ = GRAPH[nxt]

random.shuffle(succ) # WHY DO THIS?

for x in succ:

if not x in closed:

open = [x] + open

return closed

def bfs_traverse(start):

open = [start]

closed = []

while open != []:

nxt = open[0]

open = open[1:]

closed.append(nxt)

print nxt

succ = GRAPH[nxt]

random.shuffle(succ)

for x in succ:

if not x in closed:

open.append(x)

return closed

def dfs_search(start,goal):

open = [start]

closed = []

while open != []:

nxt = open[0]

if nxt == goal:

return goal

open = open[1:]

closed.append(nxt)

print nxt

succ = GRAPH[nxt]

#random.shuffle(succ)

for x in succ:

if not x in closed:

open = [x] + open

return None

def bfs_search(start,goal):

open = [start]

closed = []

while open != []:

nxt = open[0]

if nxt == goal:

return goal

open = open[1:]

closed.append(nxt)

print nxt

succ = GRAPH[nxt]

random.shuffle(succ)

for x in succ:

if not x in closed:

open.append(x)

return None

def dfs_search_path(start,goal):

open = [[start,[start]]]

closed = []

k = 1

while open != []:

nxt= open[0]

nxtnode = nxt[0]

nxtpath = nxt[1]

if nxtnode == goal:

return nxt

open = open[1:]

closed.append(nxtnode)

print “%d. %s” % (k,nxt)

succ = GRAPH[nxtnode]

random.shuffle(succ)

for x in succ:

if not x in closed:

open = [[x,addpath(nxtpath,x)]] + open k += 1

return None

def bfs_search_path(start,goal):

open = [[start,[start]]]

closed = []

k = 1

while open != []:

nxt = open[0]

nxtnode = nxt[0]

nxtpath = nxt[1]

if nxtnode == goal:

return nxt

open = open[1:]

closed.append(nxtnode)

print “%d. %s” % (k,nxt)

succ = GRAPH[nxtnode]

random.shuffle(succ)

for x in succ:

if not x in closed:

open.append([x,addpath(nxtpath,x)])

k += 1

return None

def addpath(path,x):

newpath = path[:]

newpath.append(x)

return newpath

def best_search_path(start,goal):

open = [[start,[start],0]]

closed = []

k = 1

while open != []:

nxt = open[0]

nxtnode = nxt[0]

nxtpath = nxt[1]

nxtcost = nxt[2]

if nxtnode == goal:

return nxt

open = open[1:]

closed.append(nxtnode)

print “%d. %s” % (k,nxt)

succ = GRAPH[nxtnode]

random.shuffle(succ)

for x in succ:

if not x in closed:

xcost = COST[(nxtnode,x)] open.append([x,addpath(nxtpath,x),nxtcost+xcost])

open.sort(lambda x,y: CostCmp(x,y))

k += 1

return None

• x,y are lists that are compared by

• magnitude of their third elements; def CostCmp (x,y):

if x[2] < y[2]: return -1

elif x[2] == y[2]: return 0

else: return 1