-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathClass_Note.txt
163 lines (97 loc) · 3.06 KB
/
Class_Note.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
wqNote1 2019-1-29
Tree search:
. Breadth-first search
• Uniform-cost search
• Depth-first search
• Depth-limited search
• Iterative deepening depth-first search
• Bidirectional search
Completeness: Is the algorith garanteed to find a solution when there is one?
Optimality: Find optimal solution?
Time Complexity: How long does it take to find?
Space Complexity:How much memory?
Compare performance:
b: maximum branching factor(Max number of children in each node)
d:depth of shallowest goal state
m: maximum length of path in the tree
-BFS: Breadth-First Search:
First in first out, finish each level First
a
b c
d e f g
a->b->c->d->e.....
This is Complete
No, not optimal in terms of real distance but optimal in terms of unit steps
because the result is the shallowest level.
Time: b^d
space: b^d
terrible in terms of algorith
-Depth-First search (DFS)
Last in first out: stack
Expand the deepest node in current search
complete? can run into infinity steps when repeate step are allowed.
DFS not optimal
Time:b^m m is the maximum depth if any node so worse tha BFS
space: b*m only o(m) using backtracking
-Depth-limite search:
depth limit l<d
time: b^l
space: b*l
-Interative dfs:
time:b^d
space: b*d
Optimality:yes
-bidirection search:
one from start, one from goal
complete like BFS
time:2b^(d/2) -> b^(d/2)
space: 2b^(d/2) -> b^(d/2)
-uniform-cost search
2019-1-31
Best-First Search
Function F for search as evaluation function
Heuristic function h(n) approximate cost from n to goal
GBFS(Greedy Best-first search)
if approximate distance is close to real distance, then optimal
A* search
Most popular search algorithm
function g and function f
add approximate and traveled
chose min z=g+f
check the min one
approximate: admissible never overtime cost: h<h*(true cost)
2019-2-1 Resitation
Dikstra(Unifor Cost Search)
2019-2-5
Optimality of A* search
Heuristic function is consistent: approximate h <= real h
It can always find the goal without infinite lopp because f value keep increasing
and it will find the small one(to ensure it not going backward)
manhattan distance
In real life, try different h function to see whitch one goes faster.
Evaluate heuristics functions:
evaluate the number of nodes expanded by a search technique
if h2 has an average a lower effective branching factor than h1
h2(n) >= h1(n)
h2 dominate h1
multi-heuristics
hmax=max(h1, h2, h....)
hmax is admissible and consistent if h1, h2,.... are admissible and consistent
New PPT:
Local Search
Continuous state spaces
Stochastic solutions
Optimization
local Search
local maximum and global maximum
Hill-climbing search (aka greedy local search)
gradient decent is this for continuous
2019-2-12
Hill climbing: The trouble with plateaus
plateaus: a flat area of the state-space landscape
新想法：多线程，在local maximun的地方开启多线程，然后多个小球一起往多个方向走
simulated annealing
temperature is high at begining and decreasing
basic idea: find local maximun, move further, update.
local beam search
genetic algorithms