Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import pytest
from search import *
class Graph(Problem):
"""
Graph class to test uninformed search algorithms which work on graphs with path costs.
"""
def __init__(self, initial, goal=None, paths={}, bidirectional = False):
"""
The constructor takes as input the initial state, list of goal states and a dictionary representing a list of tuples which contiains the action and path cost
"""
#Make a dictionary of actions
action_dict = {}
for state in paths.keys():
action_dict[state] = {}
for next_state, path_cost in paths[state]:
action_dict[state][next_state] = path_cost
if bidirectional:
if next_state not in action_dict.keys():
action_dict[next_state]={}
action_dict[next_state][state] = path_cost
update(self, initial=initial, goal=goal, action_dict=action_dict)
def actions(self, state):
"""
returns the possible actions to take as a list of strings representing the state that action leads to
"""
return [ action for action in self.action_dict[state] ]
def result(self, state, action):
"""
Return the state that results from executing the given action
"""
#Make sure the action is in actions(state)
assert is_in(action, self.actions(state))
return action
def goal_test(self, state):
"""
Return True if the state is a goal.
"""
return is_in(state, self.goal)
def path_cost(self, c, state1, action, state2):
"""Return the cost of a solution path that arrives at state2 from
state1 via action, assuming cost c to get up to state1. If the problem
is such that the path doesn't matter, this function will only look at
state2. If the path does matter, it will consider c and maybe state1
and action. The default method costs 1 for every step in the path."""
return c + self.action_dict[state1][state2]
Fig[3, 12] = Graph('A', ['G'], {'A':[('B', 1), ('C', 1)],
'B':[('D', 1), ('E', 1)],
'C':[('F', 1), ('G', 1)],
'D':[],
'E':[],
'F':[],
'G':[]})
def test_breadth_first_tree_search():
solution_node = breadth_first_tree_search(Fig[3, 12])
assert solution_node.solution() == ['C', 'G']
assert [node.action for node in solution_node.path()] == [None, 'C', 'G']
#Test BFS if no goal is present
Fig[3, 12].goal = []
assert breadth_first_tree_search(Fig[3, 12]) is None
Fig[3, 12].goal = ['G']
if __name__ == '__main__':
pytest.main()