forked from skalakm/dickinsonaifall2020
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnotes.txt
129 lines (84 loc) · 2.06 KB
/
notes.txt
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
uninformed search
complete- search that finds a solution (if one exists)
optimal- finds the best solution
state- problem state (e.g. "Arad")
node-has a state, a parent, possibly children, possibly cost (e.g. "Arad", "Sibiu", 220)
branching factor- number of child nodes per parent node
depth- distance from root to deepest node
big O and trees
given a branching factor of b and a depth m, how many nodes are in the tree?
depth 0, 1 node
depth 1, b nodes
depth 2, b^2 nodes
depth 3, b^3 nodes
....
depth m, b^m
Total number of nodes
1 + b + b^2 + b^3 + ... + b^m = (1-b^(m+1))/(1-b)
O(b^m)
tree search
frontier = {root}
while no solution and frontier is not empty
curNode = frontier.getNode()
check if it's the solution
add children of curNode to frontier
graph search (don't repeat states)
Collection<Node> frontier = {root}
Collection<State> visited = {root}
while no solution and frontier is not empty
curNode = frontier.getNode()
check if it's the solution
for child in children of curNode
if child is not in visited
frontier.add(child)
visited.add(child)
What data structure is frontier?
stack- depth first search
complete? depends if its graph (yes) or tree (no, could get in an infinite loop)
Arad, Sibiu, Arad, Sibiu, Arad, Sibiu, ...
optimal?
no
space?
O(bm)
speed?
O(b^m)
queue- breadth first search
complete?
yes
optimal?
yes
space?
O(b^(m-1))
speed?
O(b^m)
depth limited search- depth first search, but stop if you hit a particular depth d
complete?
yes if d>=m, no generally
optimal?
no
space?
O(bd)
speed?
O(b^d)
iterative deepening
do a depth limited search. If it fails, increase depth by 1.
DLS(1), then DLS(2), then DLS(3), ... , DLS(m)
complete?
yes
optimal?
yes
space?
O(m)
speed?
O(b^m)
DLS(0) takes 1
DLS(1) takes b
DLS(2) takes b^2
DLS(3) takes b^3
....
DLS(m) takes b^m
1+b+b^2+b^3+...+b^m=O(b^m)
priority queue (ordered by current cost)- uniform cost
(same issues as bfs)
puzzle
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/fifteen.html