20151910042-刘鹏-AG实验04-路的插点数问题1
需积分: 0 189 浏览量
2022-08-03
15:46:13
上传
评论
收藏 335KB PDF 举报
·
1
·
云南大学数学与统计学院
《算法图论实验》上机实践报告
课程名称：
算法图论实验
年级：2015
级
上机实践成绩：
指导教师：
李建平
姓名：
刘鹏
专业：
20151910042
上机实践名称：
路的插点数问题
学号：20151910042
上机实践日期：2018-12-31
上机实践编号：
4
组号：
一、 实验目的
1. 了解最短路的最小插点问题的实际背景；
2. 能快速写出求最短路的最小插点问题的动态规划算法。
二、 实验内容
1. 写出求最短路的最小插点问题的动态规划算法；
2. 用 C 语言实现上述算法。
三、 实验平台
Windows 10 Pro 1803；
MacOS Mojave。
四、 算法设计
4.1 问题描述
给定一个无向图 = (,;)，边权重函数: →
+
，该函数可以视为两个节点之间进行通信的时
间延迟（time delay），然后给定一个正整数 ∈
+
，集合 = {(
,
;
)| = 1,2,,}，其中
∈ 是起
始点（source node），
∈ 是收点（sink node）可以把集合看作一个通信请求限制集合，即沿着某条从
到
路径中，延迟之和不准超过
；该问题是寻找一个的子图
= (
,
)，满足：
（1） 对于集合中任何一个元素(
,
;
)，在
中都有一条从从
到
的路径
，且该路径的总延迟
(
) = ∑ ()
∈
≤
;
（2） 在
中的所有边上，都插入一些新的节点（可以看作是添加一些中继器或信号放大器），保证得到的
边的延迟都不超过，显然，∀ ∈
，插入的节点数量应该是() = ()/−1。
（3） 目标是找一个
，在其中总插入的节点数量最少且满足要求（1）和（2）。
4.2 路的插点问题
给定一个连通赋权图 = (,;,;,)以及两个正整数和，这里: →
+
是边的权重函数，
: →
+
是边的插点函数（指往这条边插入一个点需要花费的成本），,是两个固定的顶点，在图中寻
找一条从到的路
，使得路
的权重
不超过常数，并且向路
的一些特殊边上插入若干顶点，
使得新的路
∗
中任意边的权重都不超过常数；目标：在满足上述条件下，求出插入顶点后所产生的最小
费用，如果用INSERT()表示在边中插入的点的个数，那么总插点费用为∑ ()
∈
，即求
min∑ ()
∈
any
评论0
最新资源