文档介绍：对拟阵的初步研究
概览
第一部分：拟阵的基本概念
第二部分：拟阵的最优化问题
第三部分：一个任务调度问题
第四部分：拟阵实例
拓展部分： Shannon开关游戏
第一部分：拟阵的概念
拟阵是一个二元组对拟阵的初步研究
概览
第一部分：拟阵的基本概念
第二部分：拟阵的最优化问题
第三部分：一个任务调度问题
第四部分：拟阵实例
拓展部分： Shannon开关游戏
第一部分：拟阵的概念
拟阵是一个二元组
S
1、S是一个有限集。
2、L是个以集合作为元素的集合,且它的元素必须是S的子集
L
3、遗传性：对任意
任意
有
L
B
A
A
4、交换性：对任意
存在一个
,使
L
B
A∪{x}
x
A
定义
拟阵是一个二元组
，满足:
1、S是一个有限集。
2、L是由S的一些子集组成的有限非空集
3、遗传性：对任意
，任意
有
4、交换性：对任意
存在一个
,使
S
L
S
L
U
A
X
定义
对于
如果
那么称U为独立集
对于独立集A,若存在
满足
则称A为可扩展的
不可扩展的独立集称为极大独立集
满足此条件的x称为A的一个可扩展元素
实例:图拟阵
考虑对于无向图
定义
1、S是边集E
2、
无环的边集的子集必然无环,故满足遗传性
此连通分量中必然存在一条边，放入A中不形成环
所以B中存在一个连通分量,该分量在A中不连通
如果边集A的边数比边集B少
则A形成的连通分量数目比B多
该边显然属于B-A。交换性成立
M是拟阵，称为图拟阵
A
B
第二部分：拟阵上的最优化问题
问题提出
对于拟阵
S的元素x有一个正整数权值w(x)
S的任意子集U的权值
目标:求权值最大独立集。
贪心算法
Greedy(M,w)
A := 空集
根据w按递减顺序对S排序
for 每个
根据权
的递减顺序 do
if (
)
then
return A
时间复杂度
排序
若判断需
总复杂度
贪心
次判断
正确性证明
只需证明在算法的每一步A都是某个最优解的子集，那么当算法结束时A就是一个最优解
运用归纳思想
归纳基础:初始时A为空,满足要求
归纳:只需证明一个最优解的子集A经过一次循环后仍满足要求.
T
A
T
A =A∪{x}
X
能使A扩展
的最大元素
y
A
X
T =T-{y}+{x}
w(y) ≤w(x)
w(T ) ≥w(T)
T
′
′
′
′
′
第三部分任务调度问题
问题提出
S:
调度:
0
1
2
3
4
5
给定一个单位时间任务的集合S
S有n个任务1,2,…,n
对S的一个调度规定了各任务执行的顺序。
该调度第i个任务开始于时刻i-1,结束于时刻i
表示第i个任务的截止时刻
问题提出
n个整数
(
)
,
表示第i个任务的罚款
n个正整数
调度:
0
1
2
3
4
5
2
3
1
3
9
7
6
8
罚款:6+8=14
如果任务i的结束时刻超过截止时刻
则要交付
的罚款。
求一个调度，使得罚款最少。
分析
考虑这么一个问题：对于S的子集A，是否存在调度方案使A中的任务都被完成。
将A按任务的截止时刻从小到大排序作为调度方案,如果按此调度无法全部完成A的任务，则其他任意调度方案都无法完成。
调度:
0
1
2
3
4
5
1
2
4
3
拟阵结构
对于给定的任务集合A，能够有效地判断这些任务能否全部完成
能全部完成的任务集合A称为可行的
定义
S就是所有任务的集合
第四部分：拟阵实例
线性拟阵
T:
S
U
线性无关
1
3
2
7
图拟阵和线性拟阵
G=(V,E)
4
5
1
2
3
4
5
1
1
1
0
0
0
2
0
-1
0
-1
0
3
-1
0
0
1
0
4