文件名称：Vertex-Cover:在交通路口安装监控摄像头
文件大小：352KB
文件格式：ZIP
更新时间：2024-04-28 06:01:57
C++
顶点覆盖 客观的 我们的目的是帮助当地警察局在交通路口安装安全摄像头。 这被设计为称为最小顶点覆盖问题的优化问题，其思想是最小化为有效监控而需要安装的摄像机。 抽象的 在该项目中，我们实现了三种算法来解决最小顶点覆盖问题。 第一种算法CNF-SAT-VC是针对CNF-SAT问题的多项式时间约简，而其他两种算法（即APPROX-VC-1和APPROX-VC-2）是近似方法。 为了分析算法的效率，我们收集了每种算法的结果，并比较了它们的平均运行时间以及近似比率。 综上所述，基于所收集的数据，APPROX-VC-1被证明是解决顶点覆盖问题的最佳算法。 什么是最小顶点覆盖率 最小顶点覆盖是一个优化问题，可以在多项式时间内解决。 因此，这是一个NP完全问题。 无向图的顶点覆盖基本上是覆盖图所有边缘的顶点的子集。 例如，下图中显示的红色顶点是顶点覆盖的一部分。 入门 安装以生成可执行文件。 您还需要
【文件预览】：
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)