没有合适的资源？快使用搜索试试~ 我知道了~

文库首页操作系统其它斯坦福 CS261 算法进阶课程讲义

斯坦福 CS261 算法进阶课程讲义

课程资源

需积分: 5 0 下载量 184 浏览量 2024-02-01 14:38:02 上传评论收藏 6.15MB PDF 举报

温馨提示

试读

270页

斯坦福 CS261 算法进阶课程讲义斯坦福 CS261 算法进阶课程讲义斯坦福 CS261 算法进阶课程讲义 =========================

资源推荐

资源详情

资源评论

CS261：算法进阶课程第一讲：课程

目标和最大流介绍

∗

Tim Roughgarden

†

2016年1月5日

1 课程目标

CS261有两个主要的课程目标，并且课程大致上分为两部分。

1.1 解决良好的问题

这个第一个目标非常符合算法入门课程的精神。事实上，CS261的前几周几乎是CS161的

直接延续——在一个学期的学校里，我们会在CS161的最后几周讲到这些主题。

课程目标1 学习高效的算法解决基本和解决良好的问题。

有一系列问题非常灵活，可以模拟许多应用，并且在理论和实践中都可以快速准确地

解决。例如，在CS161中，你学习了最短路径算法。你应该已经学会了以下所有内容：

1. 最短路径问题的一个或多个变体的正式定义。

2. 一些著名的最短路径算法，如Dijkstra算法和Bellman-Ford算法，属于算法的经典之

作。

3. 最短路径算法的应用，包括那些并不明确涉及网络路径的问题。例如，用于规划一

系列随时间变化的决策问题。

†斯坦福大学计算机科学系，474 Gates Building，353 Serra Mall，斯坦福，

CA 94305。电子邮件：tim@cs.stanford.edu。

像CS161或CS261这样的课程中，研究这类问题是首要任务。这些课程的最大好处之一

是它们防止你重新发明轮子（或者试图发明不存在的东西），而是让你站在前辈们的肩膀

上。当你遇到这类问题时，你已经有了好的算法工具，不需要从头开始设计一个。这门

课程还将让你练习发现那些只是稍加伪装的这些问题的应用。

具体而言，在课程的前半部分，我们将学习：

1. 最大流问题；

2. 最小割问题；

3. 图匹配问题；

4. 线性规划，这是已知的最一般的多项式时间可解问题之一。

我们解决这些问题的算法的运行时间会比你在CS161中学到的算法稍微长一些（在那里几

乎所有的东西都在近线性时间内运行）。然而，这些算法足够快，如果你关心的问题归

约为这些问题之一，你应该会很高兴。

1.2 不太好解决的问题

课程目标2学习解决不太好解决的问题的工具。

不幸的是，许多现实世界的问题属于这个范畴，原因各不相同。

我们将重点研究两类这样的问题。

1.N P困难问题，我们不指望存在任何精确的多项式时间算法。我们将学习几种广泛有

用的技术，用于设计和分析这类问题的启发式算法。

2. 在线问题。这个过时的名称并不是指互联网或社交

网络，而是指现实情况下算法必须在不知道未来的情况下做出不可撤销的

决策（即，在不知道整个输入的情况下）。

我们将重点讨论N P-难和在线问题的算法，这些算法能够保证输出

一个与最优解相当接近的解。

1.3 预期受众

CS261有两个重要的受众群体。第一群是正在修读他们的最后一个算法课程的学生。对

于这个群体，目标是将课程内容压缩为必要且可能-有用的材料。第二群是考虑深入研究

算法的学生。考虑到这个群体，当机会出现时，我们将讨论

最近的研究进展并让你一窥未来算法课程的内容。对于这第二个受众，CS261还有第三个

目标。

课程目标3提供学习高级算法的入口。

完成CS261课程后，你将能够顺利选修部门提供的许多200级和300级算法课程。 CS261的

学习进度和难度介于CS161和更高级理论课程之间。

当你向听众演讲时，最好心中有一个或几个“典型听众”角色。供你参考和娱乐，这是

你的导师对不同级别课程中典型学生的心理模型：

1. CS161：有一部分学生不想参加课程，或者讨厌数学。

2. CS261：一群自愿选择学习算法并希望深入了解的学生。学生们可能喜欢数学，也可

能不喜欢，但不应该讨厌它。

3. CS3xx：面向希望从事或已经从事算法研究的学生。

2 最大流问题介绍

图1：（a，左）我们的第一个流网络。每条边都与一个容量相关联。（b，右）一个值为

5的示例流，其中红色、绿色和蓝色路径的流值分别为2、1、2。

2.1 问题定义

最大流问题在算法的设计和分析中是一个经典问题。

直观上很容易理解，所以在给出正式定义之前，让我们先进行一个非正式的例子。

定义。

图1(a)中的图片类似于你在学习最短路径时看到的图片，但语义不同。每条边都标有

一个容量，即它能够承载的最大数量的东西。目标是弄清楚从顶点 s到顶点 t可以推动多

少东西。

例如，图1(b)展示了一种从 s到 t推送五个单位流量的方法，同时尊重所有边的容量。

我们能做得更好吗？当然不能，因为最多只能有5个单位的流量通过它的两条出边逃逸。

形式上，最大流问题的一个实例由以下要素组成：

•一个有向图 G，具有顶点 V和有向边 E；

•一个源顶点 s ∈ V；

•一个汇顶点 t ∈ V；

•对于每条边 e ∈ E，一个非负整数容量 u

。

3 (3)

2 (2)

5 (1)

3 (3)

图2：通过跟踪每条边上的流量量来表示流量。流量量用括号表示。

由于目标是从 s到 t推送流量，我们可以假设不失一般性地， s没有入边， t没有出边

。

给定这样的输入，可行的解是网络中的流量。虽然图1(b)描述了多条路径的流量，但

对于算法来说，只需跟踪每条边上的流量量（如图

所示）更有效。

形式上，流量是一个

非负向量{f,

}

e∈E

，索引为G的边，满足两个约束条件：

1我们所有的最大流算法都可以扩展到无向图；参见练习集＃1。

2在这个意义上，每个流都是流路径和流循环的叠加；参见问题＃1。

容量约束：对于每条边

∈E，f≤u。

守恒约束：对于除s和t以外的每个顶点v，

进入 v的流量量等于离开 v的流量量。

左边是进入 v的边的 f

的总和；同样，右边是离开v的边的总和。

目标是计算出最大流量——即离开 t的总流量最大的流量。（正如我们将看到的，这

与进入t的总流量相同。）

2.2 应用

为什么我们要关心最大流问题？与所有核心算法问题一样，最大流问题本身就很有用，

而且许多不同的问题实际上只是最大流的变形。对于一些相对明显和字面的应用，最大

流问题可以模拟交通网络中的路由、数据网络中的数据包传输，或者分配网络中的石油流

动。在接下来的讲座中，我们将证明从二分图匹配到图像分割等问题都可以归约为最大流

问题。

2.3 一个朴素贪心算法

现在我们将注意力转向最大流问题的高效算法设计。事先并不清楚是否存在这样的算法（

就我们现在所知，该问题可能是N P难的）。

我们首先考虑贪心算法。回想一下，贪心算法是一种通过一系列短视和不可撤销的决

策来解决问题的方法，希望最终一切都能顺利解决。对于大多数问题，贪心算法通常不能

产生最佳解。但是尝试贪心算法仍然是值得的，因为贪心算法失败的方式通常会带来启

发，从而导致更好的算法。

解决最大流问题的最简单的贪心方法是从全零流开始，并贪心地产生具有越来越高值

的流。从一个流到下一个流的自然方式是在某条从 s到 t的路径上发送更多的流（参见图

1(b)）。

3流量对应于稳态解，具有恒定的到达速率和离开速率。该模型无法捕捉流量到达不同顶点的时间。然而

，将模型扩展到同时捕捉时间方面也不难。

剩余269页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

绝不原创的飞龙

粉丝: 1w+
资源: 1091

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

斯坦福 CS261 算法进阶课程讲义

斯坦福大学cs229机器学习课程原始讲义合集

斯坦福大学MATLAB进阶讲义与源码

Python-斯坦福机器学习CS229课程讲义的中文翻译

斯坦福算法分析与设计【part 1】课程讲义

斯坦福CS231课程讲义

斯坦福 cs229 机器学习课程笔记

斯坦福CS231n李飞飞计算机视觉课程 全部讲义

斯坦福机器学习课程讲义+作业讲解

斯坦福大学CS106A课程讲义及教材

斯坦福大学机器学习课程原始讲义.zip

[CS131]2017斯坦福cs131计算机视觉课程笔记和课后作业

斯坦福大学机器学习课程cs229原始讲义

斯坦福大学机器学习学习课程讲义.rar_斯坦福大学机器学习_机器学习

[CS131]2017斯坦福cs131计算机视觉课程ppt

斯坦福大学机器学习课程原始讲义

斯坦福_图机器学习_CS224W_课程讲义.zip

斯坦福CS231课程全套资料.zip

斯坦福 CS229 机器学习讲义中文版 1~5

计算机组成原理 白中英 第六版 课后习题答案

小米妙享3.3.0.652免认证安装

2023-飞机免费社工机器人最新合集

DirectX修复工具V4.3增强版

王道408 计算机组成原理课件 2024新版ppt课件

DirectX修复工具V4.0增强版

STEP7-MicroWIN-SMART-V2.8安装包

玩客云刷机功能包（全套资料） 真·包教包会！！！ 玩客云刷机软件+玩客云刷机固件+固件刷写软件+openwrt固件+手把手教学

诺威达K2201刷机包，10.0版本，解决蓝牙不连接，放音乐一会就断

Fiddler下载，版本：5.0.20211.51073，2023年1月亲测win11可用

内含方正小标宋简体、仿宋-Gb2312、黑体、楷体、宋体，五个公文常用字体

最新资源

斯坦福CS231n李飞飞计算机视觉课程全部讲义

计算机组成原理白中英第六版课后习题答案

玩客云刷机功能包（全套资料）真·包教包会！！！玩客云刷机软件+玩客云刷机固件+固件刷写软件+openwrt固件+手把手教学