【实验目的】

掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编程，求解背包问题和tsp问题。 【问题描述】

背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1,

v2, … ,vn}的物品和一个容量为c的背包，求这些物品中的一个最有价值的子集，并且要能够装满背包。背包问题的三种贪心策略，（1）选择价值最大的物品；（2）选择重量最轻的物品；（3）选择单位重量价值最大的物品。应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。

tsp问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出

【篇三：算法设计与分析 第九章np问题】

t>1 关于问题及算法的描述

为了应用算法复杂性理论，首先要对问题、问题的一般描述、计算模型、算法、算法的复杂性给出严格的定义。但在给出精确定义之前，我们先回顾一下有关概念的粗略解释。

所谓一个问题(problem)是指一个有待回答、通常含有几个值还未确定的自由变量的一个一般性提问(question)。它由两部分决定：一是对其所有参数的一般性描述；二是对该问题的答案所应满足的某些特性的说明。而一个问题的某个例子则可通过指定问题中所有参数的具体取值来得到。以下用ii表示某个问题，用i表示其例子。 例1.1 旅行商问题

该问题的参数是由所需访问城市的一个有限集合c?{c1,c1,?,cm}和c中

每对城市ci,cj之间的距离d(ci,cj)所组成。它的一个解是对所给城市的一个排

序(c?(1),c?(2),?,c?(m))，使得该排序极小化下面表达式（目标函数）的值 m?1

?d(c?(i),c?(i?1))?d(c?(m),c?(1)) i?1

旅行商问题的任一个例子的是通过限定城市的数目，并指定每两个城市之间的具体距离而得到的。例如： c??c1,c2,c3,c4?，

d(c1,c2)?10,d(c1,c2)?10,d(c1,c2)?10,d(c1,c2)?10,d(c1,c2)?10,d(c1,c2)?10 就构成了一个具体例子，而这个例子的一个解是排序c1,c2,c3,c4，因为四个

城市的这个排序所对应旅行路线是所有能旅行路线中长度最小的，且为27。

所谓算法(algorithm)是指用来求解某一问题的、带有一般性的一步一步的过程。它是用来描述可在许多计算机上实现任一计算流程的抽象形式，其一般性可以超越任何具体实现时的细节。注意，复杂性理论中对算法的定义与我们通常理解的具体算法－用某种计算机语言编写的、可在某一特定计算机上实现的计算机程序－不同。不过，将算法想象为某个具体的计算机程序在许多情况下可以帮助我们理解有关概念和理论。

称一个算法求解一个问题ii，是指该算法可以应用到ii的任一个例子i，并保证能找到该例子的一个解。广义地讲，一个算法的有效性可以用执行该算法所需要的各种计算资源的量来度量，最典型、也是最主要的两个资源就是所需要

的时间和内存空间。但时间需求常常是决定某一特定算法在实际中是否真正有用和有效的决定性因素。应该注意到，由于计算机速度和指定系统的不同，同一算法所需时间的多少随着计算机的不同可能有很大差别。为使其具有一般性和在实际中有用，所给时间的度量不应该依赖于具体计算机，即是说，如果它们用不同的编程语言来描述，或在不同的计算机上运行，好的算法仍然保持为好的。另一点需要注意的是，即使同一算法和同一计算机，当用它来解某一问题的不同例子时，由于有关参数取值的变化，使得所运行时间也有很大差别。

对于前一个问题的解决，人们提出了一些简单但又能反映绝大多数计算机的基本运作原理的计算模型，如各种形式的图灵(turing)机、随机存储机(ram)等，然后基于这些计算模型来研究算法。对于第二个问题的解决，人们引进了问题例子大小(size)的概念。所谓一个问题例子的大小是指为描述或表示它而需要的信息量。只要表示的合适，可望例子的大小的值应该与求解的难易程度成正比。并称相应

的标识法为编码策略(encoding scheme)。事实上，作为输入提供给计算机的任一问题例子的描述可以看作是从某一有限字母表中选取所需的字符而构成的有限长字符串。通常称该字母表中的字符为码，而由其中之字符如何组成描述问题例子的字符串的方法则称为编码策略。合理的编码策略应该具有可解码性(decodability)和简洁性(conciseness)。一种典型的方法就是利用所谓的结构化字符串、通过递归、复合的方式来给出所考虑问题的合理编码策略。

给定任一问题ii，假设已经找到描述问题例子的一个合理编码策略e，则对ii的任一例子i，称其依编码策略e所得的相应字符串描述中所含有字符的个数为其输入长度，并将该输入长度的具体值作为例子i的大小的正式度量。例如，若用字母表{c,[,],/,0,1,2,3,4,5,6,7,8,9}中的字符表示旅行商问题的具体例子，则前面所给该问题的具体例子可以用字符串c[1]c[2]c[3]c[4]//10//5//9//6//9//3来描述，其相应的输入长度为32，从而，称这个例子的大小为32。

目前广泛采用的描述问题的方法主要有两种：一是将任一问题转化为所谓的可行性检验问题(feasibility problem)，二是把问题转化为判定问题(decision problem)。这里，我们采用后一种形式。实际中几乎所有问题都可直接或间接地转述为判定问题。判定问题是答案只有“是”与“非”两种可能的问题。一个判断问题ii可简单地由其所有例子的集合dii与答案为是的例子所构成

的子集yii?dii刻划。不过，为了反映实际问题所具有的特性，通常所采用的标

准描述方法由两部分组成。第一部分用诸如集合、图、函数等各种描述分量来刻划判定问题的一般性例子，以下用“例子”表示这一部分；第二部分则陈述基于

一般性例子所提出的一个“是非”提问，以下简称“问题”。因此，一个例子属于dii当且仅当它可通过用具有特定性质 的某些对象替代一般性例子所有一般

性描述分量而得到，而一个例子属于yii当且仅当限定于该例子时，它对所述提

问的回答为“是”。

例1.2 待访问城市的有限集合c?{c1,c2,?,cm}、每对城市ci,cj?c之

间的距离d(ci,cj)?z?以及一个界b?z?。

问题 在c存在一个总长不超过b的、通过所有城市的旅行路线吗？也就是说，存在c的一个排序(c?(1),c?(2),?,c?(m))使得 m?1

?d(c?(i),c?(i?1))?d(c?(m),c?(1))?b i?1

这是一个将优化问题转化成判定问题的例子。一般地，一个优化问题可以看作是其所有实例的集合。而每一个实例为一个元素对(f,c)，其中f是可行解集，而c是目标函数。一个最优化问题可以提出下述三种模式：

? 最优化模式：求最优解； ? 求值模式：求出最优值；

? 判定模式：给定一个实例(f,c)和一个整数l，问是否存在一个可行解

f?f，使得c(f)?l？

显然，在求解最优值不太困难的假设下，上述三种模式的每一种都不比前一种困难。一般而且比较现实的假设是：最优值是一个整数，且这个整数或其绝对值的对数被输入长度的一个多项式所界定。在这种情况下，用二分搜索(或叫折半搜索)技术证明，只要判定模式存在多项式时间算法，求值模式也存在多项式时间算法。

为了给出算法的严格定义，我们借助于“语言”这一术语。设?是一个字符集，用?*表示由?中的字符组成的所有有限长度字符串的集合。?*的任何非空子集l都称为?上的一个语言(language)。例如{01,001,111,1010110}就是字符集{0,1}上的一个语言。判定问题于语言之间的对应关系是通过编码策略来实现的。一旦选定了某个字符集?，则对于任一个判定问题ii及其编码策略e，ii和e将会把?*中的所有字符串划分为三部分：那些不是ii的例子的编码、那些对ii的回答为“非”的例子的编码和那些对ii的答案为“是”的例子的编码。 这后一类编码正是要与ii通过e来联系的语言。定义：

l[ii,e]?{x??|?为e所使用的字符集，*x为某个例子i?yii在e下的编码}

如果一个结论对语言l[ii,e]成立，则说它在编码策略e下对问题ii成立。计算复杂性理论所直接考虑的是对语言或字符串集的分析。对于任何两个合理的编码策略e和e’，问题ii的某个性质要么对l[ii,e]和l[ii,e] 均成立，要么对二者均不成立。因此，可以直接说某个性质对ii成立或不成立，常常将l[ii,e]简记为l[ii]。但是，这样的省略却