人工智能原理复习2
ai.berkeley.edu（课件资料来源）
Search Problems
Uninformed Search Methods
Depth-First Search
Breadth-First Search
Uniform-Cost Search
Unified formalism leading to A* search (search guided by heuristic)
Uninformed Search Methods（无信息搜索方法）是一组在没有关于目标位置的额外信息的情况下，用于在图或树结构中搜索目标的方法。这些搜索算法不依赖于任何关于目标位置的启发式信息，它们通常用于解决一些简单的搜索问题，如迷宫探索或路径查找。以下是一些常见的无信息搜索方法：
- 广度优先搜索（Breadth-First Search, BFS）：
- BFS是一种从根节点开始，逐层扩展节点的搜索方法。
- 它使用队列作为其主要的数据结构，以确保按照层次顺序访问节点。
- BFS保证找到的是从起点到目标的最短路径。
- 深度优先搜索（Depth-First Search, DFS）：
- DFS通过递归或显式栈的方式尽可能深地搜索树的分支。
- 它使用栈（可以是递归调用堆栈或显式的栈数据结构）来存储待访问的节点。
- DFS不保证找到最短路径，但通常用于探索所有可能的路径。
- 迭代加深深度优先搜索（Iterative Deepening Depth-First
Search, IDDFS）：
- IDDFS是DFS的改进版本，它通过逐层增加搜索深度来避免DFS的递归深度限制问题。
- 它结合了BFS和DFS的优点，可以在不使用大量内存的情况下找到最短路径。
- Uniform-Cost Search（均匀成本搜索）（代价优先）：
- 这种搜索方法总是扩展具有最低路径成本的节点。
- 它适用于所有边的权重都是非负的情况，并保证找到最短路径。
- 双向搜索（Bidirectional Search）：
- 双向搜索从起点和终点同时进行，向中间点扩展。
- 这种方法可以加快搜索速度，尤其是在起点和终点之间的距离较短时。
无信息搜索方法的优点是它们简单易实现，不需要关于问题领域的额外信息。然而，它们的缺点是在某些情况下效率不高，特别是当搜索空间很大或目标很远时。这些方法通常作为更复杂搜索算法的基础，或者在问题规模较小或结构简单时使用。
1、2、4需要理解掌握
Unified formalism leading to A* search (search guided by heuristic)
Reflex Agents
在人工智能领域，反射式智能体是一种基于简单条件反射规则做出决策的智能体。它们通常对环境的感知非常直接，并且立即做出反应，而不需要复杂的内部状态或长期规划。反射式智能体的决策过程类似于人类的本能反应，例如，当手碰到热的物体时立即缩回。
Reflex agents:
Choose action based on current percept (and maybe memory) May
have memory or a model of the world’s current state Do not consider the
future consequences of their actions Consider how the world IS
反射代理:根据当前感知(也可能是记忆)选择行动
,可能对世界当前状态有记忆或模型不考虑其行动的未来后果考虑世界是怎样的
Can a reflex agent be rational?
Reflex Optimal
Optimality is not defined by algorithm, but by rational behavior.
Planning Agents
Planning agents:
Ask “what if”
Decisions based on (hypothesized) consequences of actions
Must have a model of how the world evolves in response to actions
Must formulate a goal (test)
Consider how the world WOULD BE
Optimal vs. complete planning
最优规划vs.完全规划
Planning vs. replanning
规划vs.重新规划
You could figure out the consequences by doing it. But instead, planning considers what the world would be without actually doing it. Simulate many games, execute one. Doesn’t do it in the world, does it in the model. Consequences of action. > Complete – a solution; optimal – best
Search Problems*****
How do we formalize a search problem?
State Space（状态空间）状态空间是所有可能状态的集合，其中每个状态代表了问题的一个特定配置或位置。
Successor function（后继函数）定义了从给定状态出发，通过执行某个动作所能到达的所有可能的后继状态。换句话说，后继函数是从一个状态到其可能的下一个状态的映射。
start state（初始状态） 初始状态是搜索过程开始时的状态。在很多搜索问题中，它通常是已知的，并且只有一个。初始状态定义了搜索的起点，所有搜索算法都从这个状态开始进行探索。
goal test （目标测试）是搜索算法中用来确定一个状态是否为目标状态的检查过程。在搜索问题中，目标测试是至关重要的，因为它决定了搜索何时结束。
解决方案是将开始状态转换为目标状态的一系列行动(计划)
Goal test – sometimes more than one state that satisfies
having achieved the goal, for example, “eat all the dots”
目标测试——有时不止一种状态满足实现目标，例如，“吃掉所有的圆豆”
Models aren’t perfect.
Too detailed, you can’t solve.
Not detailed enough, doesn’t solve.
State space: > Cities
Successor function:
Roads: Go to adjacent city with cost = distance
Start state: > Arad
Goal test: > Is state == Bucharest?
Solution?
What’s in a State Space?
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 Sizes?
State Space Graphs and Search Trees
State Space Graphs
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!
We can rarely build this full graph in memory (it’s too big), but it’s a useful idea
Search Trees
A search tree:
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
Different plans that achieve the same state, will be different nodes
in the tree.
Every plan in the tree.
Search ignores most of the tree.
Tree Search
Important ideas:
Fringe
Expansion
Exploration strategy
Main question: which fringe nodes to explore?
Depth-First Search
Strategy: expand a deepest node first
Implementation: Fringe is a LIFO stack
DFS扩展了哪些节点?
树的一些左前缀。
可以处理整棵树!
如果m是有限的，耗时O(b^m)
How much space does the fringe take?
Only has siblings on path to root, so O(bm)
Is it complete?
m could be infinite, so only if we prevent cycles (more later)
Is it optimal?
No, it finds the “leftmost” solution, regardless of depth or cost
Process whole tree if goal is lower right.
Space: At each level, children of one node at most on fringe, so b.
Times number of layers m. (Small!)
Breadth-First Search
Strategy: expand a shallowest node first
Implementation: Fringe is a FIFO queue
What nodes does BFS expand?
Processes all nodes above shallowest solution
Let depth of shallowest solution be s
Search takes time O(b^s)
How much space does the fringe take?
Has roughly the last tier, so O(b^s)
Is it complete?
s must be finite if a solution exists
Is it optimal?
Only if costs are all 1 (more on costs later)
Tier of best solution. If on right, b^s. Exponential Big. 最佳解决方案层。如果在右边，b^s。指数大。
DFS vs BFS
When will BFS outperform DFS?
When will DFS outperform BFS?
BFS:解决方案不太靠下。DFS:需要查到底。内存限制。
Iterative Deepening(迭代加深)
Idea: get DFS’s space advantage with BFS’s time / shallow-solution
advantages
Run a DFS with depth limit 1. If no solution…
运行深度限制为1的DFS。如果没有解决方案……
Run a DFS with depth limit 2. If no solution…
Run a DFS with depth limit 3. …..
Isn’t that wastefully redundant?
Generally most work happens in the lowest level searched, so not so
bad!
Another strategy. Combine best of both.
DFS – successor says if deeper than one, stop.
Really common.
BFS finds the shortest path in terms of number of actions.
It does not find the least-cost path. We will now cover a similar
algorithm which does find the least-cost path.
Uniform Cost Search（代价优先）
Strategy: expand a cheapest node first
Fringe is a priority queue (priority: cumulative cost)
首先扩展最便宜的节点
边缘是一个优先级队列(优先级:累积开销)
Like breadth first，but with costs
Contours show equal cost.
What nodes does UCS expand?
Processes all nodes with cost less than cheapest solution!
If that solution costs C* and arcs cost at least e , then the “effective
depth” is roughly C/e
Takes time O(b^(C/e)) (exponential in effective depth)
How much space does the fringe take?
Has roughly the last tier, so O(b^(C*/e))
Is it complete?
Assuming best solution has a finite cost and minimum arc cost is
positive, yes!
Is it optimal? Yes! (Proof next lecture via A*)
Let’s say C* is 10 and minimum step size is 2. How deep in the tree? C*/e = 5. How many nodes is that?
The good:
UCS is complete and optimal!
The bad:
Explores options in every “direction”
No information about goal location
All these search algorithms are the same except for fringe strategies
Search Gone Wrong?
Next time – guided search where you know something about direction of solution.