人工智能原理复习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(无信息搜索方法)是一组在没有关于目标位置的额外信息的情况下,用于在图或树结构中搜索目标的方法。这些搜索算法不依赖于任何关于目标位置的启发式信息,它们通常用于解决一些简单的搜索问题,如迷宫探索或路径查找。以下是一些常见的无信息搜索方法:

  1. 广度优先搜索(Breadth-First Search, BFS)
    • BFS是一种从根节点开始,逐层扩展节点的搜索方法。
    • 它使用队列作为其主要的数据结构,以确保按照层次顺序访问节点。
    • BFS保证找到的是从起点到目标的最短路径。
  2. 深度优先搜索(Depth-First Search, DFS)
    • DFS通过递归或显式栈的方式尽可能深地搜索树的分支。
    • 它使用栈(可以是递归调用堆栈或显式的栈数据结构)来存储待访问的节点。
    • DFS不保证找到最短路径,但通常用于探索所有可能的路径。
  3. 迭代加深深度优先搜索(Iterative Deepening Depth-First Search, IDDFS)
    • IDDFS是DFS的改进版本,它通过逐层增加搜索深度来避免DFS的递归深度限制问题。
    • 它结合了BFS和DFS的优点,可以在不使用大量内存的情况下找到最短路径。
  4. Uniform-Cost Search(均匀成本搜索)(代价优先)
    • 这种搜索方法总是扩展具有最低路径成本的节点。
    • 它适用于所有边的权重都是非负的情况,并保证找到最短路径。
  5. 双向搜索(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?

alt text

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?

alt text
  1. State Space(状态空间)状态空间是所有可能状态的集合,其中每个状态代表了问题的一个特定配置或位置。

  2. Successor function(后继函数)定义了从给定状态出发,通过执行某个动作所能到达的所有可能的后继状态。换句话说,后继函数是从一个状态到其可能的下一个状态的映射。

  3. start state(初始状态) 初始状态是搜索过程开始时的状态。在很多搜索问题中,它通常是已知的,并且只有一个。初始状态定义了搜索的起点,所有搜索算法都从这个状态开始进行探索。

  4. goal test (目标测试)是搜索算法中用来确定一个状态是否为目标状态的检查过程。在搜索问题中,目标测试是至关重要的,因为它决定了搜索何时结束。

解决方案是将开始状态转换为目标状态的一系列行动(计划)

Goal test – sometimes more than one state that satisfies having achieved the goal, for example, “eat all the dots”
目标测试——有时不止一种状态满足实现目标,例如,“吃掉所有的圆豆”

alt text

Models aren’t perfect.
Too detailed, you can’t solve.
Not detailed enough, doesn’t solve.

alt text

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?

alt text

State Space Graphs and Search Trees

alt text

State Space Graphs

alt text

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.

Important ideas:

Fringe
Expansion
Exploration strategy

Main question: which fringe nodes to explore?

Strategy: expand a deepest node first
Implementation: Fringe is a LIFO stack

alt text
alt text

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!)

alt text

Strategy: expand a shallowest node first
Implementation: Fringe is a FIFO queue

alt text

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(迭代加深)

alt text

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.

alt text

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.

alt text
https://pic.imgdb.cn/item/6670de82d9c307b7e972a314.pn

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?

alt text

The good:
UCS is complete and optimal!

The bad:
Explores options in every “direction”
No information about goal location

alt text

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.


人工智能原理复习2
http://jrhu0048.github.io/2024/06/17/ren-gong-zhi-neng-yuan-li/ren-gong-zhi-neng-yuan-li-fu-xi-2/
作者
JR.HU
发布于
2024年6月17日
更新于
2024年10月15日
许可协议