码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift
  • 图论深度优先搜索进阶


    图论深度优先搜索进阶

    • 前言
    • 深度优先搜索进阶
      • 引入概念
        • 解空间
          • 解的组织形式
          • 显约束
          • 解空间
        • 搜索解空间
          • 隐约束
          • 术语
      • 剪枝方法
    • 后继

    前言

    之前写过一篇博客图的搜索:https://blog.csdn.net/weixin_42178241/article/details/125956595
    主要讲述了基础的BFS和DFS

    深度优先搜索进阶

    无非是加了剪枝而已

    引入概念

    解空间

    解的组织形式

    可以看作一个n元组{x1,x2,x3,x5,x5,……,xn-1,xn}

    显约束

    对解分量的取值范围的限定。

    解空间

    就是所有的解组成的空间,而我们要根据题目的约束条件找到符合的最优解,解空间大,搜索效率低,解空间小,搜索效率高。

    搜索解空间

    隐约束

    剪枝函数,包含约束函数和限界函数。剪枝函数可以避免不必要的搜索,提高代码效率

    术语

    1. 扩展结点: 一个正在生成孩子的节点
    2. 活结点:一个自身已生成,但孩子还没有全部生成的节点
    3. 死结点: 一个孩子都已生成的节点
    4. 子孙: 节点e的子树上的所有节点,都是e的祖孙
    5. 祖宗:从节点e到树根路径上的所有节点都是e的祖宗

    剪枝方法

    前面已提过剪枝的作用

    剪枝的方法主要是通过题目给出的条件,去分析如何在一步时花费O(1)或O(log(n))的算法,去预判他的可行性

    后继

    跟多精彩文章尽情期待

  • 相关阅读:
    2022年100道最新软件测试面试题,常见面试题及答案汇总
    Vue(模板语法 2)
    读书 | 设计模式之禅 - 责任链模式
    Windows11突然VM虚拟机无法运行报错与 Device/Credential Guard 不兼容
    动态开点线段树(C++实现)
    Linux服务器格式化磁盘,分区,挂载
    python计算离散积分
    学习笔记第十九天
    openresty出现socket read/write busy的原因及解决方法
    #### 广告投放 ####
  • 原文地址:https://blog.csdn.net/weixin_42178241/article/details/126359724
  • 最新文章
  • 攻防演习之三天拿下官网站群
    数据安全治理学习——前期安全规划和安全管理体系建设
    企业安全 | 企业内一次钓鱼演练准备过程
    内网渗透测试 | Kerberos协议及其部分攻击手法
    0day的产生 | 不懂代码的"代码审计"
    安装scrcpy-client模块av模块异常,环境问题解决方案
    leetcode hot100【LeetCode 279. 完全平方数】java实现
    OpenWrt下安装Mosquitto
    AnatoMask论文汇总
    【AI日记】24.11.01 LangChain、openai api和github copilot
  • 热门文章
  • 十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧!!!
    奉劝各位学弟学妹们,该打造你的技术影响力了!
    五年了,我在 CSDN 的两个一百万。
    Java俄罗斯方块,老程序员花了一个周末,连接中学年代!
    面试官都震惊,你这网络基础可以啊!
    你真的会用百度吗?我不信 — 那些不为人知的搜索引擎语法
    心情不好的时候,用 Python 画棵樱花树送给自己吧
    通宵一晚做出来的一款类似CS的第一人称射击游戏Demo!原来做游戏也不是很难,连憨憨学妹都学会了!
    13 万字 C 语言从入门到精通保姆级教程2021 年版
    10行代码集2000张美女图,Python爬虫120例,再上征途
Copyright © 2022 侵权请联系2656653265@qq.com    京ICP备2022015340号-1
正则表达式工具 cron表达式工具 密码生成工具

京公网安备 11010502049817号