1.1 问题与问题实例

问题是需要人们回答的一般性提问，通常包含若干参数，由问题描述、输入条件、输出要求等要素组成。

问题实例定义为确定问题描述参数后的一个对象。

一个问题的问题描述和输入条件通常包含若干参数，当给定这些参数一组赋值后，则可以得到一个问题实例。一个问题可以包含若干问题实例，问题和问题实例的关系类似面向对象程序设计语言中类和对象的关系。

【例1-1】 正整数求和问题

问题描述：计算正整数a与b的和c。

输入：正整数a、b（1≤a,b≤10000）。

输出：和c。

在正整数求和问题中，指定a=1，b=1，则构成了一个问题实例“1+1”；如果令a=1000，b=1000，则构成了另一个问题实例“1000+1000”。

虽然对于正整数求和问题，两个问题实例之间的差别不大。但是，对于有些问题，不同问题实例无论是其描述还是求解的难度差别都非常大。

【例1-2】 迷宫问题

问题描述：在一个N×N的棋盘迷宫中，有些格子能通行（用1表示），有些格子不能通行（用0表示），假定棋盘位置(1, 1)为入口，(N,N)为出口，且在棋盘中只能横向或者竖向移动。任意给定一棋盘，试问是否存在从入口到出口的路径。

输入：正整数N表示棋盘的大小，N×N的0-1矩阵表示每个棋盘格子的状态。

输出：1，表示存在路径；0，表示不存在。

在迷宫问题中，当N=2时，棋盘布局如图1-1(a)所示（黑色格子表示0，白色格子表示1），得到一个问题实例a。当N=10000，棋盘布局如图1-1(b)所示，得到另一个问题实例b。显然，求解问题实例b比求解问题实例a更困难。在棋盘大小（N=10000）相同布局不相同的情况下，求解消耗时间也可能不一样。比如在实例b、c、d中，采用从入口到出口的广度优先搜索算法（搜索技术参阅第7章），实例b所需要的时间比实例c的多，实例d所需要的时间也比实例c的多。如果采用从出口到入口的广度优先搜索算法，实例d所需要的时间比实例b和实例c的要少得多。

图1-1 迷宫问题的不同问题实例

值得注意的是，在问题求解时，一个算法能正确而有效地求解某一个问题，严格意义上是指该算法对于该问题的所有问题实例都能正确而有效地得到答案，而不是指该算法能正确而有效地求解某一个或者某几个问题实例。