cs50ai0----search

这篇具有很好参考价值的文章主要介绍了cs50ai0----search。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

cs50ai0-------Search


  • cs50ai0-------Search
    • 基础知识
    • 课后题目
    • 代码实践
    • 学习链接
    • 总结

基础知识

(1) search problem
cs50ai0----search
上图是搜索问题的一般形式
每个名词具体解释如下:
initial state:state是agent与environment的一个配置或者说构造,initial state就是初始的state
actions:在state下可以做出的所有action
transition model:
对在任何state下执行可执行的action所产生的状态的描述
goal test:确认当前state是否是goal state
path cost function:与某一个path相关的cost
(2) dfs与bfs
cs50ai0----search
上图就是dfs与bfs的具体算法流程
首先 从一个包含着initial state的frontier与空的explored set开始,从frontier中安照规则移除一个node(包含parent state,当前state,以及从parent到当前node的action),拓展该node,将拓展得到的不在frontier中和explored set中的node加入frontier,重复上述操作,直到frontier为空或者到达目标state
区别就是frontier采用的数据结构不同,dfs是stack,bfs是queue
(3) greedy best-first search(gbs)与A*搜索
上面提到的dfs与bfs属于无信息搜索即盲目搜索
而贪心搜索属于有信息搜索也叫启发式搜索
具体定义为:
扩展最接近目标的节点的搜索算法,这个最接近的节点由启发式函数 h(n) 估计
cs50ai0----search
如上图所示 在迷宫问题中的h(n)是到目标的manhattan距离

但是贪心搜索可能导致找到的是局部最优解,不是全局最优路径
而A*搜索则是使用g(n)与h(n)来计算path cost

cs50ai0----search
相当于已经走过的cost和估计的cost之和

A*算法是最优的在如下所示的情况下:
cs50ai0----search
要h(n)要满足不过分估计同时保持一致性
这一点我理解的不是很清楚😭

(4)对抗性搜索或者说博弈?😡
重要元素:
s0:初始state
Player(s):定义此时该谁动
Actions(s):此状态下的合法移动集合
Result(s,a):转移模型,定义行动的结果
Terminal(s):终止测试,游戏结束返回真,否则假。
Utility(s):效用函数,定义游戏者p在终止状态s下的数值
cs50ai0----search

minmax算法就是其中的一种
cs50ai0----search
cs50ai0----search
cs50ai0----search

如上面几张图所示
极大极小核心算法建立在尽力削弱对手的value上面
比如说下面这颗树:
cs50ai0----search
箭头向上表示该player要最大化得分
向下则表示要最小化得分
那么player想要自己的得分最大,要考虑对手的想法,需要遍历对手的每一种action,比如说让对手走4这颗子树,会产生4 8 5这三种结果,对手绘最小化自己的得分,所以自己最终会得到四分,同样其它两颗子树自己会得到3和2分,应该选择最大的4这颗子树

而这种算法的问题也很明显,遍历对手的所有想法,树的深度一增加,复杂度就会指数倍上升,因此就有了两种方法来解决此问题
一个是剪枝,即假如我们已经能提前估计下面这颗子树的效果不如当前最好的子树效果好,我们可以直接将整颗子树放弃掉
一个是限制树的深度,比如说就限制树只要十层,这里需要额外的一个evaluate function,来估计某个state下预期的utility,从而提前做出action

课后题目

(1)degrees
文件说明:机翻稍改💪
small与big是两组csv数据文件

现在,打开small/stars.csv。 此文件在 people.csv 中的人物和 movie.csv 中的电影之间建立关系。 每行都是一对 person_id 值和 movie_id 值。 例如,第一行(忽略标题)指出 id 为 102 的人主演了 id 为 104257 的电影。对照 people.csv 和 movie.csv 检查这一点,您会发现这一行表示 Kevin Bacon 主演电影《好人寥寥无几》。

接下来,看一下 Degrees.py。 在顶部,定义了多个数据结构来存储 CSV 文件中的信息。 名字字典是一种通过名字查找人的方法:它将名字映射到一组相应的 ID(因为多个演员可能具有相同的名字)。people 字典将每个人的 id 映射到另一个字典,其中包含该人的姓名、出生年份以及他们主演的所有电影的集合。电影字典将每个电影的 id 映射到另一个包含该电影标题值的字典, 发行年份,以及所有电影明星的阵容。 load_data 函数将数据从 CSV 文件加载到这些数据结构中。

该程序中的主函数首先将数据加载到内存中(加载数据的目录可以通过命令行参数指定)。 然后,该函数提示用户输入两个名字。 person_id_for_name 函数检索任何人的 ID(如果多个人具有相同的名称,则处理提示用户进行澄清)。 然后该函数调用shortest_path函数来计算两个人之间的最短路径,并打印出该路径。

然而,shortest_path 函数尚未实现。这就是我们要实现的地方

具体说明:
完成shortest_path函数的实现,使其返回从具有source id的人到具有target id的人的最短路径。

假设存在从源到目标的路径,您的函数应返回一个列表,其中每个列表项都是从源到目标的路径中的下一个 (movie_id, person_id) 对。 每对应该是两个字符串的元组。
例如,如果shortest_path的返回值为[(1, 2), (3, 4)],则意味着source与人物2一起主演电影1,人物2与人物4一起主演电影3,人物 4 是target。
如果从source到target有多个最小长度的路径,则您的函数可以返回其中任何一个。
如果两个参与者之间没有可能的路径,则您的函数应返回 None。
您可以调用neighbors_for_person函数,该函数接受一个人的id作为输入,并为与给定人一起主演电影的所有人返回一组(movie_id,person_id)对。
尽管您可以编写其他函数和/或导入其他 Python 标准库模块,但除了 Shortest_path 函数之外,您不应修改文件中的任何其他内容。

提示:
虽然课程中搜索的实现会在节点从边界弹出时检查目标,但您可以通过在将节点添加到边界时检查目标来提高搜索效率:如果检测到目标节点,则无需要将其添加到边界,您只需立即返回解决方案即可。
欢迎您借用和改编课程示例中的任何代码。 我们已经为您提供了一个文件 util.py,其中包含 Node、StackFrontier 和 QueueFrontier 的课程实现,欢迎您使用(如果您愿意,也可以进行修改)。

(2)tic-tac-toe
文件说明
该项目中有两个主要文件:runner.py 和 tictactoe.py。 tictactoe.py 包含玩游戏和做出最佳动作的所有逻辑。 runner.py 已为您实现,并且包含运行游戏图形界面的所有代码。 完成 tictactoe.py 中所有必需的功能后,您应该能够运行 python runner.py 来与您的 AI 对战!

让我们打开 tictactoe.py 以了解所提供的内容。 首先,我们定义三个变量:X、O 和 EMPTY,来表示棋盘可能的移动。

函数initial_state 返回板的起始状态。 对于这个问题,我们选择将棋盘表示为三个列表的列表(表示棋盘的三行),其中每个内部列表包含三个值,即 X、O 或 EMPTY。 剩下的函数是我们留给您实现的功能

具体说明
完成player、actions、result、winner、terminal、utility和minimax的实现。

player:应将board作为输入,并返回轮到哪个玩家了(X 或 O)。在初始游戏状态下,X 先走一步。随后,玩家交替进行每个额外的动作。
actions:应该返回一组可以在board上执行的所有可能操作。
每个动作应表示为一个元组 (i, j),其中 i 对应于该移动的行(0、1 或 2),j 对应于该行中与该移动相对应的单元格(也是 0、1 或 2)。可能的移动是棋盘上尚未包含 X 或 O 的任何单元格。
result:将board和action作为输入,并应返回新的board状态,而不修改原始棋盘。
如果action对于board是非法的,应该raise an exception
返回的board应该是通过获取原始输入棋盘并让轮到的玩家在输入动作指示的单元格处移动而产生的棋盘。
重要的是,原始棋盘应保持不变:因为 Minimax 最终需要在计算过程中考虑许多不同的棋盘状态。 这意味着简单地更新板本身的单元并不是结果函数的正确实现。在进行任何更改之前,您可能需要先对板进行deep copy。
winner:应接受一个棋盘作为输入,并返回该棋盘的获胜者(如果有)。如果 X 玩家赢得了游戏,您的函数应返回 X。如果 O 玩家赢得了游戏,您的函数应返回 O。
水平、垂直或对角线连续走三步即可赢得比赛。
您可能会假设最多只有一个获胜者。
如果游戏没有获胜者(因为游戏正在进行中,或者因为平局结束),则该函数应返回 None。
terminal:应该接受board作为输入,并返回一个布尔值来指示游戏是否结束。
如果游戏结束,无论是因为有人赢得了游戏,还是因为所有单元格都已填满而没有人获胜,则该函数应返回 True。
否则,如果游戏仍在进行中,该函数应返回 False。
utility:应接受board作为输入并输出该板的utility。
如果 X 赢得了游戏,则效用为 1。如果 O 赢得了游戏,则效用为 -1。 如果比赛以平局结束,则效用为 0。
您可能会假设只有当terminal为 True 时才会在板上调用utility。
minimax: 应将board作为输入,并返回玩家在该board上移动的最佳移动。
返回的移动应该是最优动作 (i, j),这是棋盘上允许的动作之一。 如果多个移动同样是最佳的,那么任何一个移动都是可以接受的。
如果该板是terminal,则 minimax 函数应返回 None。
对于接受板作为输入的所有函数,您可以假设它是一个有效的板(即它是一个包含三行的列表,每行具有 X、O 或 EMPTY 三个值)。 您不应修改所提供的函数声明(每个函数的参数的顺序或数量)。
一旦所有功能都正确实现,您应该能够run python runner.py 并与您的 AI 比赛。 而且,由于井字游戏是双方都发挥最佳表现的平局,所以你永远无法击败人工智能(尽管如果你表现不佳,它可能会打败你!)

e我还真输了一局😭

提示
如果您想在不同的 Python 文件中测试函数,可以使用 from tictactoe import initial_state 等行导入它们。
欢迎您向 tictactoe.py 添加其他辅助函数,前提是它们的名称不会与模块中已有的函数或变量名称冲突。
Alpha-beta 剪枝是可选的,可能会让你的 AI 运行更高效!

代码实践

(1)degrees
采用的是bfs,具体思路见上面的算法流程,基本上是一步步对应的,不过多讲解了
具体代码如下:

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
    start = Node(state=source, parent=None, action=None)
    frontier = QueueFrontier()
    frontier.add(start)
    explore = set()
    while True:
        if frontier.empty():
            return None
        node = frontier.remove()
        if node.state == target:
            ac = []
            while node.parent is not None:
                  ac.append((node.action,node.state))
                  node = node.parent
            ac.reverse()
            return ac
        explore.add(node.state)
        neighbours = neighbors_for_person(node.state)
        for action,state in neighbours:
            if not frontier.contains_state(state) and state not in explore:
                child = Node(state=state, parent=node, action=action)
                frontier.add(child)

(2)tictactoe
前面几个函数都比较简单
minmax函数也是和前面算法流程实现一致
值得注意的是这里并没有使用剪枝函数
还有player的先手判断,涉及到第一步下哪
这里我试了一下发现,如果是ai先手的话运行时间比较慢
感觉是runner.py的逻辑写的有一点问题?

def player(board):
    """
    Returns player who has the next turn on a board.
    """
    ## xo数量判断谁先手,数量一致默认x先手
    xcount = 0
    ocount = 0
    for row in board:
        xcount += row.count(X)
        ocount += row.count(O)
    return X if xcount == ocount else O


def actions(board):
    """
    Returns set of all possible actions (i, j) available on the board.
    """
    ## 返回棋盘上所有可以下的位置
    actionmove = set()
    for row_index, row in enumerate(board):
        for column_index, item in enumerate(row):
            if item is None:
                actionmove.add((row_index, column_index))
    return actionmove


def result(board, action):
    """
    Returns the board that results from making move (i, j) on the board.
    """
    ## 返回做出相应行动的棋盘状态
    player_move = player(board)
    i, j = action
    ## 根据提示这里采用深拷贝
    new_board = deepcopy(board)
    if board[i][j] is not None:
        raise Exception
    else:
        new_board[i][j] = player_move

    return new_board


def winner(board):
    """
    Returns the winner of the game, if there is one.
    """
    # Check rows
    for row in board:
        if all(item == X for item in row):
            return X
        elif all(item == O for item in row):
            return O

    # Check columns
    for col in range(3):
        if all(board[row][col] == X for row in range(3)):
            return X
        elif all(board[row][col] == O for row in range(3)):
            return O

    # Check diagonals
    if board[0][0] == board[1][1] == board[2][2] and board[0][0] in [X, O]:
        return board[0][0]
    if board[0][2] == board[1][1] == board[2][0] and board[0][2] in [X, O]:
        return board[0][2]

    return None  # No winner found


def terminal(board):
    """
    Returns True if game is over, False otherwise.
    """
    if winner(board) is None:
        if not actions(board):
            return True
        else:
            return False
    else:
        return True


def utility(board):
    """
    Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
    """
    if winner(board) == X:
        return 1
    elif winner(board) == O:
        return -1
    elif winner(board) is None:
        return 0


def minimax(board):
    """
    Returns the optimal action for the current player on the board.
    """

    def max_value(board):
        optimal_move = ()
        if terminal(board):
            return utility(board), optimal_move
        else:
            v = -10000
            for action in actions(board):
                minval = min_value(result(board, action))[0]
                if minval > v:
                    v = minval
                    optimal_move = action
            return v, optimal_move

    def min_value(board):
        optimal_move = ()
        if terminal(board):
            return utility(board), optimal_move
        else:
            v = 10000
            for action in actions(board):
                maxval = max_value(result(board, action))[0]
                if maxval < v:
                    v = maxval
                    optimal_move = action
            return v, optimal_move

    curr_player = player(board)

    if terminal(board):
        return None

    if curr_player == X:
        return max_value(board)[1]

    else:
        return min_value(board)[1]


学习链接

参考代码链接:https://github.com/wbsth/cs50ai
https://github.com/PKUFlyingPig/cs50_ai
视频链接(b站中文机翻字幕): https://www.bilibili.com/video/BV1AQ4y1y7wy/?p=5&vd_source=23b9ed7e58fa7e510011caaf2e7e3320
课程官网(全套资源):https://cs50.harvard.edu/ai/2023/

总结

ai入门课,第一节课感觉很不错,课上讲的知识很好的在代码中实现,但也比较基础
总体花费: 3小时文章来源地址https://www.toymoban.com/news/detail-656198.html

到了这里,关于cs50ai0----search的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【AI人工智能】50个AI技术在商城的应用和服务

    智能客服机器人:通过 AI 技术可以实现商城的智能客服功能,为用户提供24小时在线的咨询、答疑和解决问题的服务。可以利用自然语言处理和深度学习等技术,让机器人像人类一样理解用户提问,并给出相关的答复。 推荐引擎:利用AI技术,可以根据用户的历史购买记录、

    2024年02月08日
    浏览(45)
  • AI:50-基于深度学习的柑橘类水果分类

    🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌本专栏包含以下学习方向: 机器学习、

    2024年02月05日
    浏览(37)
  • 【AI人工智能】Phind:免费面向开发者的生成式 AI 搜索引擎 | FREE Generative AI search engine for developers

    Phind 通过简单的解释和来自网络的相关代码片段来回答技术问题。  与ChatGPT和new Bing一样,Phind由大语言模型(Large Language Model (LLM))驱动。体验后,个人感觉在技术方面的检索能力和质量上Phind 比 new Bing 和 ChatGPT 的体验要好得多。 Phind也支持非开发人员相关问题回答,响应

    2023年04月19日
    浏览(53)
  • AI绘图哪家强?50款AI绘图软件大盘点【内附Midjourney保姆级上手教程】

    今天就为大家盘点一下,目前世面上比较火的24款AI绘图软件,并附上Midjourney最新注册教程以及使用方法! Midjourney可谓是2023年最火的AI绘画工具,一经发布就让无数设计师直呼“要失业了”。 只要输入,Midjourney就能生成任何你想要的图片。 目前搭载在discord平台上的

    2024年03月24日
    浏览(42)
  • 分享50个AI绘画prompt的关键词,让你的AI绘画更贴近想法

    我们在使用AI绘画工具时,最关键的就是prompt,但是我们不能总是拾人牙慧,总是用别人写出的现成的prompt,那样的话,最终画出来的画,也是别人画出来的,并不能完全生成自己想要的效果。所以,我们需要学习编写prompt的技巧,了解prompt中的,并将这些加入到我

    2024年02月09日
    浏览(51)
  • 50倍效率!600+AI工具、3000+AI提示艺术,《AIGC万能工具包》助你职场效率起飞

    众所周知,2023年是AI元年。 以ChatGPT为例,AI能帮你 定目标、写文案,列提纲、找数据 ,甚至还能帮你做到想不到的事情…… 对不同行业的职场人士来说,它绝对是一个 省力气,省时间,能大幅度提升工作产出 的助手。 但也有人发现了,给ChatGPT不明确的指令,它并不能给

    2024年02月10日
    浏览(50)
  • pytorch实现AI小设计-1:Resnet50人脸68关键点检测

            本项目是AI入门的应用项目,后续可以补充内容完善作为满足个人需要。通过构建自己的人脸数据集,此项目训练集为4580张图片,测试集为2308张图片,使用resnet50网络进行训练,最后进行效果展示。本项目也提供了量化内容,便于在硬件上部署。         研究A

    2024年01月18日
    浏览(42)
  • openGauss学习笔记-50 openGauss 高级特性-DB4AI

    openGauss当前版本支持了原生DB4AI能力,通过引入原生AI算子,简化操作流程,充分利用数据库优化器、执行器的优化与执行能力,获得高性能的数据库内模型训练能力。更简化的模型训练与预测流程、更高的性能表现,让开发者在更短时间内能更专注于模型的调优与数据分析上

    2024年02月11日
    浏览(91)
  • FPGA上利用Vitis AI部署resnet50 TensorFlow神经网络模型

    参考Xilinx官方教程快速入门 • Vitis AI 用户指南 (UG1414) 克隆 Vitis AI 存储库以获取示例、参考代码和脚本(连接github失败可能需要科学上网)。 安装Docker如何在 Ubuntu 20.04 上安装和使用 Docker 安装完docker后,下载最新Vitis AI Docker, 将官方的指令 docker pull xilinx/vitis-ai-pytorch/tensorfl

    2024年02月04日
    浏览(44)
  • 【ChatGPT】| 最全七大场景50+小场景应用指南合集——内部指导版本(AI训练师必备,带案例)

    系列说明:由ChatGPT小白进阶成最强AI训练师必看(含资讯/框架教程/应用案例等) 第一篇【ChatGPT】| 最全七大场景50+小场景应用指南合集——内部指导版本(AI训练师必备,带案例) 本文尽量完整罗列了目前ChatGPT的七大应用场景(50+细分场景),为接下来打算深度应用ChatG

    2024年02月04日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包