#机器学习

cs188课堂笔记

劈里啪啦

Search Problems

  • A search problem consists of:
    • A state space
    • A successor function(with actions, costs)
    • A start state and a goal test
  • A solution is a sequence of actions (a plan) which transforms the start state to a goal state
  • The world state includes every last detail of the environment.
  • A search state keeps only the details needed for planning(abstraction)
Problem:Pathing
 States:(x,y)location
 Actions:NSEW
 Successor:update location only
 Goal test:is(x,y) = END

Problem: Eat-All-Dots
 States:{(x,y),dot booleans}
 Actions:NSEW
 Successor:update location and possibly a dot boolean
 Goal test:dots all false

State space graph

A mathematical representation of a search problem

  • Nodes are (abstracted) world configurations
  • Arcs represent successors(action results)
  • The goal test is a set of goal nodes(maybe only one)

In a state space graph, each state occurs only once
20250404213857

Search Trees

  • A “what if” tree of plans and their outcomes
  • The start state is the root node
  • Children correspond to successors
  • Nodes show states, but correspond to PLANS that achieve those states
  • For most problems, we can never actually build the whole tree

20250404214735

Searching with a Search Tree

  • Expand out potential plans(tree nodes)
  • Maintain a fringe of partial plans under consideration
  • Try to expand as few tree nodes as possible

20250404215037

DFS

20250404220129
先进后出，扩展最后加入边缘的那个节点
在实现中一般使用stack即栈存储探索过的节点，再pop选择下一个扩展的节点，同时栈符合先进后出的原则，故使用栈

BFS

先进先出，在边缘等待时间最长的节点会优先被扩展
20250404220543
使用queue即队列存储探索过的节点

Iterative Deepening

20250404220900

Uniform Cost Search(Dijkstra)

不再遵循先进后出或先进先出的原则，而是按照当前最小代价进行扩展
20250404221557
Remember:UCS explores increasing cost contours
The good:UCS is complete and optimal The bad:

  • Explores options in every “direction”
  • No information about goal location

贪婪算法直接向目标所在方向寻找，可能在有障碍物的情况下无法找到代价最小的路，或找不到路

  • Uniform-cost orders by path cost, or backward cost g(n)
  • Greedy orders by goal proximity,or forward cost h(n)
  • A* Search orders by the sum: f(n) = g(n) + h(n)

一个可接受的代价函数的特质：低估从给定状态到达目标的成本
20250615161253

总结一个好的启发式函数的特征：

  • 可采纳 当且仅当对于每个节点n，h(n)都不会高估从n到目标的实际最小代价
  • 一致性 当且仅当对于每个节点n及其任意后续节点m，满足三角不等式
    数学表达： h(n) ≤ c(n,m) + h(m) c(n,m):从n到m的实际代价 h(m):后续节点的启发式值

证明a星可以找到最优路径
20250615164706

20250615211106

20250615203252

每拓展一个新的点就把该点加入探索过的点集合中，之后不再拓展以该点结尾的路径

20250615204317

20250615204346

20250615211122

20250615211435

局部搜索的general idea

  • Start wherever
  • Repeat move to the best neighboring state
  • If no neighbors better than current，quit

容易陷入局部最优，可通过引入在陷入局部最优时随机移动的方法来摆脱局部最优，但允许随机移动的次数难以选择
方案一 退火算法
20250615212745

方案二 束搜索
20250615213420
20250615213458