学期序号 , − . / 0 1
表 2 软件 专业课程安排
开设课程 C 1 、C 9 C 2 、C 4 C 10、C 11 C 3 、C 5 C6、C 12 C 7 、C 8
总学分 9 6 7 6 6 8
图2
求解如下: ( a) 将其转化为有向图 (图 2). ( b)按重新设计的顶点结构来解决软件专业 课程的安排问题: 所给条件知, 学期总数为 2N = 6, 每学期的学分限为 L1 = L2 = % = L6 = 7, 修正值为 = 2. ( c) 初始化图, 置图中所有的 点的 S elect = 1, T erm = 0. ( d)求解过程如下: i= 1: W = 0+ L1 = 7 C1. F irst= = 1, d ist( C1 ) = 3, M = int ( 1 / 2* ( 6- 1) ), 3> M, insert(P, C1 ), then C 1. Se lect= 1, C1. T erm = 1, SUM 1 = 0+ 2 = 2, S = 0+ v. Score= 2, T = {C1 } C9. F irst= = 1, dist(C9 ) = 3, M = int ( 1 / 2* ( 6- 1) ), 3> M, insert(P, C9 ), then C 9. Se lect= 1; C9. T erm = 1; SUM 1 = 2+ 7 = 9, S = 2+ 7= 9; T = {C1, C9 } i= 2: W = 7+ L2 = 14 C2. F irst= = 1, d ist( C2 ) = 2, M = int( 1 /2* ( 6- 2) ), 2< = M, S + 3< 14+ 2
我们在有向图中也引进距离的概念, 可得到类
似于上述三角不等式的性质.
设有向网络 G = < N, A, W > 中, 边权非负, 点
集合 N = { 1, 2, %, n}, A 为边弧的集合. 若用 ui 和
uj 分别表示自点 1至 i和自点 1至 j的最短有向路 的长度, 而 w kj表示弧 ( k, j)的长度 (若 ( k, j) & A, 则
对所有顶点定义后, 由其固定的先后修关系建 立有向图. 对应的问题转化为: 在此有向图中, 将所 有的课程分配至 2N 个集合中, 每个集合中的元素 间没有先后修课程关系, 即这 2N 个集合为所在有 向图中的互不相交的点独立集, 则分配后的 2N 个 集合对应着 2N 个学期的课程安排. 2. 3 问题求解 2. 3. 1 模型求解
C4. F irst= = 1, dist (C4 ) = 2, M = int( 1 /2* ( 6- 2) ), 2< = M, S + 3< 14+ 2
then C 4. Se lect= = 1; C 4. T erm = 2; SUM 2 = 3+ 3= 6; S = S + 3= 15; T = {C1, C9, C 2, C 4 }
第 8卷第 12期 2009年 12月
南阳师范学院学报 Journal of N anyang Norm a l Un iversity
V o.l 8 No 12 Dec. 2009
两个组合优化问题的算法设计
杨宏东, 王骁力
( 南阳师范学院 数学与统计学院, 河南 南阳 473061)
摘 要: 以有向赋权图为工具, 通过对满足限制条件的最 短有向 路径问 题的讨 论, 给 出了两 个组合 优化问题
1 数学模型和基本结果
1. 1 数学模型 定义 1 一个有向图 [2] G 是一个有序的二元
组 < V, A > . 其中 V 是非空集合, 其元素称为顶点 或结点; A 称为有向边集或者弧集, 它是笛卡儿积 V V 的多重子集, 其元素称为有向边或弧.
定义 2 给定 (有向或无向 ) 图 G 为赋权 图 [ 2] , 若存 在边集合 E 到实数集 的映射 W, 记作 G = < V, E, W > . 这里, 对于 E 中任意的边 e= < vi, vj > , 称 W ( e) = w ij为边 e上的权; 对于 G 的子图 G !, G !
3
离散数学
C3
4
数据结构
C4
3
汇编语言
C5
2
语言的设计和分析
C6
3
计算机原理
C7
4
编译原理
C8
4
操作系统
C9
7
高等数学
C 10
5
线性代数
C 11
2
普通物理
C 12
3
数值分析
先决条件
无 C1 C1、C 2 C1 C3、C 4 C 11 C3、C 5 C3、C 6 无
C9 C9 C1、C 9、C10
then C 2. Se lect= = 1, C 2. T erm = 2, SUM 2 = 0+ 3= 3, S = S + 3= 12, T = {C 1, C9, C 2 }
+ 18+
南阳师范学院学报
第 8卷
中自点 1至其余各点的最短有向路的 D ijkstra算法
如下:
S tep 1 (开始 ) 置 u1 = 0, uj = w 1j, j = 2, 3, %, n,
S = { 1}, T = { 2, 3, %, n} ;
S tep 2 (确定选择的点 ) 在 T 中寻找一点 k 使得
由前面假设, 每学期的 课程的总学 分上限为 L i + , 设 V 为所有课程的集合, T 是已经选择的点 的集合, P 是要优先选择的点的集合, 初始均为空 集; SUM i 累计第 i 学期被选择课程的学分 ( i = 1, 2, %, 2N ), S 为累计已经选过的课程的总学分, W 为累计学期的总学分, 初值均为 0.
( k, j), 而且该有向路上自点 1至 k 的一段也必为
最短有向路, 从而有方程
u1 = 0,
k, j= 2, 3, %, n. ( 2)
uj
=
m k
in {
uk
+
w
kj
},
因此, 自点 1至各点的最短有向路的长度必满足方
程 ( 2), 从而也说明方程 ( 2)是有解的, 即在图中最
短有向路是存在的. 1. 2 D ijkstra算法 [ 1, 11 ]
C10. F irst= = 1, d ist (C10 ) = 1, M = 1 /2* ( 8- 2), 1< M, S + 5= 20> 14+ 2
then C10. T erm = 2+ 1= 3; %% 按上述的步骤, 可以排 出软件专业 的课程安 排, 见表 2. 由表及求解过程可以看出: 设 置 S 和 W 来累 和是十分必要的, 它避免了因为课程安排靠前而导 致后面的学期没有课程可供安排的问题的出现.
wkj = + ∋ ), 则显然对一切 k ( j均有方程
u1 = 0,
k, j= 2, 3, %, n.
( 1)
uj ∃ uk + wkj,
并且第二式为等式, 当且仅当 ( k, j )在 自点 1至 j
的最短有向路上.
因为诸 uj 是 G 中自点 1至 j的最短有向路径 的长度, 因此这条最短有向路必有最后一个弧
教学计划的编排问题 和交通网络中路径规划问题的有效算法, 并通过实例 进行了算法分析.
关键词: 有向图; 最短有向 路; 教学计划编排; 交通网络; 路径规划
中图分类号: TP 311
文献标识码: A
文章编号: 1671- 6132( 2009) 12- 0017- 06
大学
在实际生活中存在着很多组合优化问题, 这些 问题中大多数是 NP 问题, 用通常的数学方法难以 解决, 或求解的过程过于繁琐, 于是人们尝试解决 这些问题的其他途径, 图论就是解决此类问题的一 种工具. 例如以有向图为工具来求解指定两点间的 最大流问题 [ 1] 、两点间的最小费用流问题 [ 1 ] 、货郎 担问题 [ 2] 等等. 教学计 划的编排问题 和交通网络 中的路径规划问题也属于组合优化问题. 对于前 一个问题, 已有研究都是讨论在同一个学期中如何 合理安排每门课程使得满足需要, 即为一个学期的 课表安排问题. 我们考虑了把某个专业要求的所 有课程安排在不同学期中 的一个教学计 划问题. 对于后一个问题多是讨论在一种条件约束下的路 径设计问题 [ 3- 10 ] , 我们对原有的算法进行了改进, 考虑了多种需求下的路径设计问题. 主要思想是以 有向赋权图作为辅助工具, 将教学计划的编排问题 和交通网络中的路径规划问题转化为赋权有向图 在特殊约束下的指定两点间的最短有向路问题, 设 计了问题的有效解法.
v. Score, S = S + v. Score; 否则, T: ∗ P ) { v}.
若 S + v. Score∃ W + , 置 v. S elect = 1, v. T erm
= i, SUM i = SUM i + v. Score, S = S + v. S core; 否则, 置 T 剩余的点 v. T erm = i + 1. Step 3 循环执行 Step 1, Step 2至集合 V 为空集时 停止. Step 4 循 环结 束后, 将 T erm = i 点插 入到 链表 TAB i 中.
设一个大学某专业共有 N 个学年, 即 2N 个学 期; 开设课程的总数为 m, 所有开设课程为: C1, C2, %, Cm; 每个学期 的学分 上限设 为 L i, 并 给以修 正值