首页 > 编程语言 >Python 学习 第三册 第12章 图的最优化问题

Python 学习 第三册 第12章 图的最优化问题

时间:2024-06-21 10:57:21浏览次数:25  
标签:__ src 12 第三册 self dest Python 节点 def

----用教授的方式学习。

目录

12.1图的最优化问题

12.1.1最短路径:深度优先搜索和广度优先搜索


12.1图的最优化问题

我们下面研究另一种最优化问题。假设你有一个航空公司航线的价格列表,其中包括美国任意两个城市之间的航班价格。假设有3个城市A、B和C,从A出发经过B到达C的价格是从A到B的价格加上从B到C的价格。你可能会有以下几个问题:

·某两个城市之间最少的停留次数是多少?

· 某两个城市之间最便宜的飞机票价是多少?

· 某两个城市之间,如果停留次数不超过两次,那么最便宜的飞机票价是多少?

· 如果想访问多个城市,那么最便宜的路线是什么?

所有这些问题(以及许多其他问题)都可以轻松转化为图的问题。

图是由边连接起来的节点对象的集合,边也可称为弧,节点也可称为顶点。如果边是单向的,则图称为有向图。在有向图中,从节点n1到n2有一条边,我们就称n1为源节点或父节点,n2为目标节点或子节点。

以下定义了几个类,分别实现了对应于节点、加权边和普通边的抽象类型。

class Node(object): 
    def __init__(self, name): 
       """假设name是字符串""" 
       self.name = name 
    def getName(self): 
       return self.name 
    def __str__(self): 
       return self.name 
class Edge(object): 
    def __init__(self, src, dest): 
       """假设src和dest是节点""" 
       self.src = src 
       self.dest = dest 
    def getSource(self): 
       return self.src 
    def getDestination(self): 
       return self.dest 
    def __str__(self): 
       return self.src.getName() + '->' + self.dest.getName() 
class WeightedEdge(Edge): 
    def __init__(self, src,

标签:__,src,12,第三册,self,dest,Python,节点,def
From: https://blog.csdn.net/weixin_38135241/article/details/139802480

相关文章

  • 热搜不再错过:用Python打造你的微博热搜追踪器
    简介在当今信息爆炸的时代,获取最新、最热门的信息成为了许多人的日常需求。微博热搜榜作为反映社会热点和公众关注焦点的重要窗口,其信息价值不言而喻。本文将介绍一个实用的Python爬虫程序,它能够自动爬取微博热搜榜的信息,并通过邮件的形式将这些信息发送给用户,帮助用户及时......
  • 文科生脑回路也学得会|Python自学笔记0620
    python安装(windows版)Python官网:WelcometoPython.org(本地机查看)设置-系统-关于-设备规格-系统类型【举例说明】WIN10系统进入各种安装版本 PythonReleasesforWindows|Python.org版本选择界定标准:电脑是64位操作系统,优先选64(win10选这个没影响,windows7以前的用......
  • HCIA17 Python自动化基础 之telnet lib 库
    1.实验介绍及拓扑公司交换机,管理IP地址为192.168.0.101/24。现编写自动化脚本,查看设备当前配置文件。2.掌握内容及配置思路2.1掌握内容Python基本语法telnetlib基本方法2.2配置思路1.   完成设备Telnet预配置(配置Telnet密码,开启Telnet功能和允许Telne......
  • m2_day12 [URL + Socket]
    课程内容:URL和SocketServer端Client端URL和SocketURL=>统一资源定位符:网址URLurl=newURL("网址");URLConnectionuc=url.openConnection();InputStreamis=uc.getInputStream();....​uc.getContentLength();得到目标内容长......
  • 【Python日志模块全面指南】:记录每一行代码的呼吸,掌握应用程序的脉搏
    文章目录......
  • 2024华为OD机试真题- 计算三叉搜索树的高度-(C++/Java/Python)-C卷D卷-100分
     2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++) 题目描述定义构造三叉搜索树规则如下:每个节点都存有一个数,当插入一个新的数时,从根节点向下寻找,直到找到一个合适的空节点插入。查找的规则是:1.如果数小于节点的数减去500,则将数插入节点的左子树2.如果数大于节点的......
  • python GUI:tkinter 信息管理系统——不会长胖的斜杠(浔川python推广部)
    总览前言主要实现登录注册修改运行登录注册登录成功主界面添加查询查询成功保存信息信息管理系统v1.1登录界面获取账号密码主界面查询查询成功显示信息信息管理系统v2.0登录主界面增加查询删除显示代码获取前言本系统主要通过tkinter模块实现,通过读取对应的文件,实现登......
  • python工具系列(亲测有效):在pycharm中复制粘贴时出现ENSP如何处理
    在pycharm中复制粘贴时出现ENSP如何处理在pycharm中复制粘贴时出现ENSP如何处理在pycharm中复制粘贴时出现ENSP如何处理安装nexchatgpt插件之后,生成的代码,如果直接粘贴到pycharm.py文件中,会出现ENSP图样,如下图所示:粘贴到jupyternotebook虽然看不出来,也是不能......
  • 新手小白包会(python) | OpenCV进阶教程,带你踏入计算机视觉领域
    目录一、OpenCV简介1.应用场景2.学习与使用二、OpenCV安装 1.安装2.验证三、OpenCV使用1.边缘检测1)sobel算子(cv2.Sobel()) 2)Scharr算子(cv.Scharr()) 3)laplacian(cv2.Laplacian())4)canny算法(cv.Canny())2.下采样(cv2.pyrDown())3.上采样(cv2.pyrUp())4.拉普拉斯金字塔......
  • 基于python-深度学习的混凝土马路和泥地马路识别-含数据集+pyqt界面
    代码下载:https://download.csdn.net/download/qq_34904125/89434765本代码是基于pythonpytorch环境安装的。下载本代码后,有个requirement.txt文本,里面介绍了如何安装环境,环境需要自行配置。或可直接参考下面博文进行环境安装。深度学习环境安装教程-anaconda-python-pyto......