【算法设计与分析】02 货郎问题与计算复杂性理论
发布日期:2021-07-01 00:07:15
浏览次数:3
分类:技术文章
本文共 1159 字,大约阅读时间需要 3 分钟。
什么是NP系列问题?今天来看看这些问题。
文章目录
1 货郎问题
-
问题:有n个城市,已知任何两个城市之间的距离,求一条每个城市恰好经过1次的回路,使得总长度最小。
-
建模与算法:
- 输入:有穷个城市的集合C={c1,c2,…,cn},距离d(ci,cj)=d(cj,ci) ∈ \in ∈ Z+ ,1 ≤ \leq ≤i ≤ \leq ≤j ≤ \leq ≤n
- 输出:1,2,…,n的排列k1,k2,…,kn,使得:
min{
∑ i = 1 n − 1 d ( c k i , c k i + 1 ) + d ( c k n , c k 1 ) {\sum_{i=1}^{n-1} d(c_{k_i},c_{k_{i+1}}) +d(c_{k_{n}},c_{k_1})} ∑i=1n−1d(cki,cki+1)+d(ckn,ck1)}- 现状:至今没有找到有效的算法。
2 0-1背包问题
- 0-1背包问题:有n个物品要装入背包,第i件物品的重量wi,价值vi,i=1,2,…,n。背包最多允许装入的重量是B。问如何选择装入背包的物品,使得总价值达到最大?
举个例子:
n=4, B=6,物品的重量和价值如下:
标号 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
重量 wi | 3 | 4 | 5 | 2 |
价值 vi | 7 | 9 | 9 | 2 |
- 0-1背包问题数学建模:
问题的解:0-1向量<x1,x2,…,xn>,当xi=1时,代表物品i装入背包。
目标函数:max ∑ i = 1 n v i x i {\sum_{i=1}^{n} v_ix_i} ∑i=1nvixi
约束条件: ∑ i = 1 n w i x i {\sum_{i=1}^{n} w_ix_i} ∑i=1nwixi ≤ \leq ≤B
x i = 0 , 1 。 i = 1 , 2 , . . . . . . , n 。 x_i=0,1 。 i=1,2,......,n。 xi=0,1。i=1,2,......,n。
0-1背包问题与货郎问题一样,至今没有找到有效的算法来解决。
3 什么是NP-hard问题(NP难问题)
像上面的货郎问题以及0-1背包问题,这样的问题有数千个,大量存在于各个领域。
- 至今没有找到有效的算法来解决该问题。(没有找到有效的算法意思是现有的算法的运行时间是输入规模的指数或者更高阶函数)
- 至今没有人能够证明对于这类问题不存在多项式时间的算法。
- 从是否存在多项式时间算法的角度看,这些问题彼此是等价的。这些问题的难度处于可有效计算的边界。
算法的研究目标主要是下面四点:
而本专栏的主要目标是下图中的下面的算法设计的部分:
我们主要学习的内容是算法分析与问题的计算复杂性,以及分治策略、动态规划、贪心算法、回溯与分支限界等的学习。
学习是漫长的,期待后面将算法知识学好。
转载地址:https://lyy-0217.blog.csdn.net/article/details/93868643 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月19日 18时52分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
查看端口占用情况
2019-05-01
nginx(编译安装)-自定义nginx安装路径
2019-05-01
linux系统,启动、停止、重启crontab服务
2019-05-01
Linux下Nginx安装/启动/重启/停止
2019-05-01
Nginx URL重写(rewrite)配置及信息详解
2019-05-01
Nginx rewrite模块深入浅出详解
2019-05-01
mysql 数据库优化配置实例
2019-05-01
crontab定时任务写法
2019-05-01
nginx: [emerg] unknown directive "if($remote_addr" in /usr/local/tools/nginx/conf/nginx.conf:57
2019-05-01
module pip has no attribute main问题解决
2019-05-01
LeetCode 134.Gas Station (加油站)
2019-05-01
Python之命名元组 (namedtuple)
2019-05-01
使用libpcap过滤arp
2019-05-01
在VC环境中调试跟踪变量
2019-05-01
开源网络通信库参考
2019-05-01