文章目录
前言一、贪心算法寻找最小支配集程序流程代码链接
二、完全图二染色程序流程代码链接
三、均匀图分割（Uniform graph partition）程序流程代码链接
四、背包问题程序流程代码链接
前言
上《图与网络》这门课时老师布置了几次编程作业，当时做的时候没有在网上找到很好的参考案例， 现在课程结束了稍微总结一下，顺便发布一些本人所写的代码以供参考。代码以matlab为主，少量为python。
一、贪心算法寻找最小支配集
最小支配集：对于一个无向图G=(V, E) , 其中V是点集，E是边集，支配集U是V的子集合，且U-V中的任何一点v 都至少有一个neighbor在U中。其中最小的支配集S（即任意一个比S小的集合都不可能是支配集）叫做最小支配集。 定理：图G=(V, E)有n个顶点，最小度数δ>1，则G存在一个支配集其顶点数目至多为
n
[
1
+
l
n
(
δ
+
1
)
]
/
(
δ
+
1
)
n[1+ln(\delta+1)]/(\delta+1)
n[1+ln(δ+1)]/(δ+1) 要求：编写一个贪心算法求解最小支配集问题，比较所求结果与定理给出的上界。
程序流程
核心思想：选取剩下的点中可以支配未被支配点最多的点加入支配集
代码链接
dominating_set.m
二、完全图二染色
用两种颜色对n个顶点的完全图 Kn 的边进行染色，存在一种方案，使得同色的完全子图 K4至多有
C
n
4
∗
2
−
5
C_n^4*{2^{ - 5}}
Cn4∗2−5 个。用条件概率方法实现边染色，使得最终得到的同色K4的数目小于等于期望值。
程序流程
核心思想：借鉴贪心算法的基本思想，根据当前图的染色情况，分别计算下 一条边染黑色或者染白色后同色K4的权重，权重越大，代表出现同色K4的数目越大，为尽量减少同色K4的数目，选取权重小的颜色进行染色。
代码链接
color_V2.py
三、均匀图分割（Uniform graph partition）
程序流程
核心思想：（启发式算法）首先随机将 V 划分成 2 个元素数目相等的集合 X0、X1 得到初始解，计算目标函数c([X0 , X1]) 。neighborhood 定义为交换 X0、X1中的一对点后得到的所有可能的 V 的划分的集合。采用穷举搜索策略，每次都选择 neighborhood 中目标函数最小的划分，逐步改进解，直到目标函数不能继续减小。
代码链接
uniform_graph_partition.m
四、背包问题
背包问题：给定一组物品，每种物品都有自己的重量和价格，有一个容量一定的背包， 找到最优的物品放置方案，使得背包中物品的总价值最大。 假设物品数量为15，背包可容纳的最大重量为750； 每个物品的重量分别为 70,73,77,80,82,87,90,94,98,106,110,113,115,118,120； 每个物品的价值分别为 135,139,149,150,156,163,173,184,192,201,210,214,221,229,240。 该问题可以采用穷举法、禁忌搜索法以及模拟退火法等来解决，这里主要讨论禁忌搜索法。 禁忌搜索法的基本思想：使用一个禁忌列表来保存最近T步的操作，每进行一次新的操作前首先查找该操作是否在禁忌表中，若在则不执行该操作，以此来避免无效的重复操作。
程序流程
核心思想：每次只改变一个物品的状态。选取性价比（价值/重量）最大的物品放入背包，若无法放入任何物品则选取性价比最小的物品取出。 每次迭代都将当前结果和 best_value（初值为 0）比较，若大于 best_value 则令 best_value 为当前结果。
代码链接
tabu.m
精彩内容
发表评论