没有合适的资源?快使用搜索试试~ 我知道了~
Vertex-Cover:在交通路口安装监控摄像头
共13个文件
cpp:4个
png:3个
yml:1个
需积分: 41 0 下载量 63 浏览量
2021-04-08
12:15:17
上传
评论
收藏 352KB ZIP 举报
温馨提示
顶点覆盖 客观的 我们的目的是帮助当地警察局在交通路口安装安全摄像头。 这被设计为称为最小顶点覆盖问题的优化问题,其思想是最小化为有效监控而需要安装的摄像机。 抽象的 在该项目中,我们实现了三种算法来解决最小顶点覆盖问题。 第一种算法CNF-SAT-VC是针对CNF-SAT问题的多项式时间约简,而其他两种算法(即APPROX-VC-1和APPROX-VC-2)是近似方法。 为了分析算法的效率,我们收集了每种算法的结果,并比较了它们的平均运行时间以及近似比率。 综上所述,基于所收集的数据,APPROX-VC-1被证明是解决顶点覆盖问题的最佳算法。 什么是最小顶点覆盖率 最小顶点覆盖是一个优化问题,可以在多项式时间内解决。 因此,这是一个NP完全问题。 无向图的顶点覆盖基本上是覆盖图所有边缘的顶点的子集。 例如,下图中显示的红色顶点是顶点覆盖的一部分。 入门 安装以生成可执行文件。 您还需要
资源详情
资源评论
资源推荐
收起资源包目录
Vertex-Cover-master.zip (13个子文件)
Vertex-Cover-master
_config.yml 28B
CMakeLists.txt 1KB
README.md 3KB
record.csv 25KB
src
CNF_SAT.cpp 4KB
algorithms.cpp 11KB
StreetDB.py 15KB
rgen.cpp 9KB
Shortest_path.cpp 8KB
images
RunningTimeAnalysisSetS2.png 22KB
ApproximateRatioAnalysisSetS2.png 12KB
MinimumVertexCover.png 23KB
report.pdf 306KB
共 13 条
- 1
陈崇礼
- 粉丝: 47
- 资源: 4683
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0