CS50ai week0: search我的笔记

haa_y

811人浏览 · 2025-09-18 16:34:01

haa_y · 2025-09-18 16:34:01 发布

Video 0

Depth-first search（DFS）

search algorithm that always expands the

deepest node in the frontier

在有限的结构下，这是一个绝对能够得到答案的策略
但在多解时它很可能无法找到最佳解决方法

Approach

Start with a frontier that contains the initialstate.
Repeat:
If the frontier is empty, then no solution.
Remove a node from the frontier.
If node contains goal state, return the solution.
Expand node, add resulting nodes to the frontier.

一个框架，node节点，frontier待探索栈

stack:

Last-in first-out data type

一种frontier的数据结构
堆叠栈结构，先拿走刚进来的，形成一个树状结构
沿着一种可能走完再依次将所有可能走完

Breadth-first search（BFS）

search algorithm that always expands the

shallowest node in the frontier

广度优先搜索,优先扩展最浅的
同时探索所有可能的路径
大部分情况下比DFS效果好，并且始终能找到最优情况

queue

first-in first-out data type

先进先出，排队

一种frontier的数据结构

uninformed search

search strategy that uses no problem-specific knowledge

上面的DFS和BFS都是这个类型。
不关心迷宫的结构等等

Informed search

search strategy that uses problem-specific

knowledge to find solutions more efficiently

相反的，启发式搜索h(n)

greedy best-first search

search algorithm that expands the node

that is closest to the goal, as estimated by a

heuristic function h(n)

贪心最佳优先搜索，如图决策点右侧离目标11步更近，走右侧（how close we are ）
有时也会遇到不想要的结果走到死胡同
不一定能够找到最佳

A* search

search algorithm that expands node with lowest value of g(n) + h(n)

g(n) = cost to reach node

h(n) = estimated cost to goal

估值变成了g(n) + h(n)
当到达了14+5，下一步数值20，比左侧另一条路线的6+13大，ai转头走了另一个路线
事实证明在特定情况下总是能找到最优解，当如下情况下时候是最佳的
- h(n) is admissible (never overestimates the true cost), and
- h(n) is consistent (for every node n and successor n' with step cost c, h(n) <h(n') + c)

Adversarial Search

对抗式，有敌人不想让我完成
Minimax 一个algorithm很适合双人对抗类

minimax

MAX (X) aims to maximize score.（想要把值最大化）
MIN (O) aims to minimize score.（想要把值最小化）
回去寻找terminal state往后推演

然后选择最后值最大的状态

Given a state s: MAX picks action a in ACTIONS(s) that produces highest value of MIN-VALUE(RESULT(s, a))

Alpha-Beta Pruning

删除一些node来节约搜索时间

不可思议，井字棋有这么多种可能

更大的棋盘更大，这个就不太行了，需要“Depth-Limited Minimax”：

Depth-Limited Minimax

不考虑不可能或是太久远的结果与状态，提高运行速度
有evaluation function评估函数，估计游戏目前状态的预期效益

Python上的收

获

Python的Class中，当在Class的方法内部调用同一个类的其他方法时，必须通过self.方法名()来调用，会自动把实例作为第一个参数传递
同级class可以继承
raise Exception("xxxxx")
列表变反原来只需要eg. actions.reverse()即可

Quiz 0

Q1

Between depth first search (DFS) and breadth first search (BFS), which will find a shorter path through a maze?

在深度优先搜索（DFS）和广度优先搜索（BFS）中，哪种方法能找到穿过迷宫的更短路径？

DFS will always find a shorter path than BFS
BFS will always find a shorter path than DFS
DFS will sometimes, but not always, find a shorter path than BFS
（我觉得这个😋事实也是这个）BFS will sometimes, but not always, find a shorter path than DFS
Both algorithms will always find paths of the same length

Q2

Consider the below maze. Grey cells indicate walls. A search algorithm was run on this maze, and found the yellow highlighted path from point A to B. In doing so, the red highlighted cells were the states explored but that did not lead to the goal.

考虑下面的迷宫。灰色单元格表示墙壁。在这个迷宫上运行了一种搜索算法，找到了从A点到B点的黄色高亮路径。在此过程中，红色高亮的单元格是已探索但未通向目标的状态。

Could only be A*
Could only be greedy best-first search
（根据特征一看就是这个）Could only be DFS
Could only be BFS（广度则会有伸出头的node）
Could be either A* or greedy best-first search（A*和贪心不可能会往上面走到顶吧）
Could be either DFS or BFS
Could be any of the four algorithms
Could not be any of the four algorithms

Q3

Why is depth-limited minimax sometimes preferable to minimax without a depth limit?

为什么有深度限制的极小极大算法有时比没有深度限制的极小极大算法更可取？

(我觉得对，概念得知)Depth-limited minimax can arrive at a decision more quickly because it explores fewer states
Depth-limited minimax will achieve the same output as minimax without a depth limit, but can sometimes use less memory
Depth-limited minimax can make a more optimal decision by not exploring states known to be suboptimal
Depth-limited minimax is never preferable to minimax without a depth limit

Q4

Consider the Minimax tree below, where the green up arrows indicate the MAX player and red down arrows indicate the MIN player. The leaf nodes are each labelled with their value.考虑下面的极小极大树，其中绿色向上箭头表示MAX玩家，红色向下箭头表示MIN玩家。每个叶节点都标有其值。

What is the value of the root node?

根节点的值是多少？

最左侧的5（Minimax 算法里，先让三个 MIN 节点分别选子节点最小值（5、1、2），再让MAX根节点从这三个值里选最大的，即 5。）

Project 0

Degrees

这个题目主要就是考察先前的node,frontier栈等等内容，逻辑上按顺序：

创建 frontier 队列—>创建初始节点并入队—>设置 visited —>从队列取出 node—>是否是target，是就生成路径不是就获取邻居expand node—>标记经过节点探索未经过节点进行遍历—>直到target

CSV 读取的数值默认是字符串类型，比如 id 是 "101" 而非 101，但不影响作为字典键

当我们用如下代码：

            people[row["id"]] = {
                "name": row["name"],
                "birth": row["birth"],
                "movies": set()
            }

会得到如下结果

people = {
    "101": {  # 键是人员ID
        "name": "张三", 
        "birth": "1990-01-01", 
        "movies": set()  # 空集合，待后续填充电影
    },
    "102": {
        "name": "李四", 
        "birth": "1995-05-05", 
        "movies": set()
    },
    "103": {
        "name": "张三",  # 重名的人，ID不同
        "birth": "1985-10-10", 
        "movies": set()
    }
}

当遇到如下代码的时候：

people[row["person_id"]]["movies"].add(row["movie_id"])

这里使用add()而不是append()，是因为存储电影 ID 和演员 ID 的数据结构是集合（set），而不是列表（list）
直接用person_id，程序能够自动找到两者的对应person_id（名字似乎都一样）进行添加
接下来是我写的最终答案，至于题目点击进官网看吧

def shortest_path(source, target):
    """
    Returns the shortest list of (movie_id, person_id) pairs
    that connect the source to the target.

    If no possible path, returns None.
    """
    # TODO
    
    ## 首先创建队列
    frontier = QueueFrontier()
    ## 创建初始点
    initial = Node(state=source, parent=None, action=None)
    ## 将初始点加入队列并标记为已访问
    frontier.add(initial)
    visited = set()
    visited.add(source)
    ## 当队列不为空时：
    while not frontier.empty():
        ## 从队列中取出第一个节点
        node = frontier.remove()
        ## 如果节点是目标节点，则返回路径
        if node.state == target:
            path = []
            while node.parent is not None:
                path.append((node.action, node.state))
                node = node.parent
            path.reverse()
            return path
        ## 否则，扩展节点
        else:
            ## 获取邻居
            neighbors = neighbors_for_person(node.state)
            ## 遍历邻居
            for movie_id, person_id in neighbors:
                ## 如果邻居未访问，则加入队列并标记为已访问
                if person_id not in visited:
                    child = Node(state=person_id, parent=node, action=movie_id)
                    frontier.add(child)
                    visited.add(person_id)
                ## 如果邻居已访问，则跳过
                else:
                    continue
    ## 如果队列为空，则返回None
    return None

Tic-Tac-Toe

这是一个井字棋游戏，当你走一步，程序会估计其他所有地方下棋的可能值（-1, 0, 1）选最小执行（电脑是地方,min_value），分的几个函数

看下面这行，左边是提取出了记分版的行和列来锁定位置，右边player得到玩家标记“X”还是“O”
```
new_board[action[0]][action[1]] = player(board)
```

minimax搜索寻找路径使用一个for函数迭代

    for action in sorted(actions(board)):
        value, _ = min_value(result(board, action))
        if value > v:
            v = value
            best_action = action

最主要代码实现：

def minimax(board):
    """
    Returns the optimal action for the current player on the board.
    """
    if terminal(board):
        return None
    if player(board) == X:
        return max_value(board)[1]
    else:
        return min_value(board)[1]


def max_value(board):
    if terminal(board):
        return (utility(board), None)
    v = -math.inf
    best_action = None
    for action in sorted(actions(board)):
        value, _ = min_value(result(board, action))
        if value > v:
            v = value
            best_action = action
    return (v, best_action)

def min_value(board):
    if terminal(board):
        return (utility(board), None)
    v = math.inf
    best_action = None
    for action in sorted(actions(board)):
        value, _ = max_value(result(board, action))
        if value < v:
            v = value
            best_action = action
    return (v, best_action)