策略，从广义上讲，是指解决问题所采取的方法。它包括解决方方面面各种问题的方法，例如：工作需要策略、学习需要策略、战争需要策略……本文讨论的策略，是指利用计算机编程解题时所采用的行之有效的方法，即编程解题策略。
　　为了论述的方便，我们约定：策略是一个宏观概念，算法是微观上的操作方法。在利用计算机解决问题时，先设法找到解决问题的策略，再根据这一策略构造出适当的算法，编写程序解决问题。显然，如何获得解决问题的策略（或称之为策略的谋划），是解决问题不可缺少的先驱过程。从某种意义上说，在谋划宏观策略的同时，也应考虑微观算法的实现。
　　编写程序解决问题常见的策略有：数学模型（规律）策略、分治策略、贪心策略、穷举（含搜索）策略等等。本文的任务是探讨策略的谋划（如何获得解决问题的策略）。

　　显然，解决同一个问题可以采用多种不同的策略，对于一个具体问题能够想到采用某种策略来解决它，是个人的分析思维能力的表现。但是，一个问题是否可以采用某种策略来解决，或者怎样采用某种策略，从本质上说，是由问题本身的性质所决定的，也就是说，寻求解决问题的策略必须从问题给出的条件入手。
　　问题一：（最佳航空路线问题）你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市出发，单方向从西到东经若干城市到达最东的城市，然后再单方向从东到西飞回起点。除起点城市外，任何城市只能访问一次。起点城市被访问二次：出发一次，返回一次。除指定的航线外，不允许乘其它航线，也不允许使用其它交通工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行航线在满足上述限制条件下，使访问的城市尽可能多。
对于这个大家熟悉的问题，我们分析下面几种解题策略：
　　[策略1]搜索策略
这个问题有明确的状态表示，而且状态之间的转移规则也是确定的，可以由初状态开始，根据状态转移规则，逐个枚举出所有的可能状态，从而得到答案。这就是状态穷举策略，也就是我们常说的“搜索策略”。
　　确定了采用搜索策略之后，还有一个实施策略的方法问题。如果仅从实际旅行的路线来看，可以先从西向东，再从东向西，搜索出一条旅行路径，这就是“单路”搜索。根据题目给出“旅行先从西到东，再从东到西”的条件，可以换个角度思考，把这一次“往返”的旅行看成是两次“单程”的从西到东的旅行。经过这样的转变之后，可以同时从西向东搜索出两条路径，这就是“双路”搜索。从题目的条件中又可以知道，从东到西的路径也可以看成是从西到东的路径，于是就可以从东、西两个方向同时向中间搜索，采用“双向”搜索，甚至还可以同时结合前面说过的“双路”搜索得到“双向双路”搜索。
　　上面所说的搜索策略，不论是“单向”还是“双向”，也不管是“单路”还是“双路”，都是针对问题给出的旅行信息而得到的。
　　[策略2]数学模型策略1
　　我们根据题目所给出的条件，对问题的形式进行转化。
　　把一次“往返”的旅行看成是两次“单程”的从西到东的旅行，同时考虑两路的旅行路线来描述问题的状态，其状态可以表示为：（X，Y），其中X、Y分别表示当前两条路线所达到的城市。例如：在图1所表示的航线中，初始状态就是（A，A），结束状态是（E，E）。

D

A E

B C
（图1）

　　由于在一个状态中包含有两条路径的信息，因此在状态转移过程中就有一个优先问题。从状态（A，B）到（D，C）,可以先转移到（A，C）再转移到（D，C）,也可以先转移到（D，B）再转移到（D，C）。这显然是一种重复。为了解决这一问题，我们可以规定状态转移时仅取离开始点较近的那一个城市，若两个城市离开始点一样近就可以任取一个城市。这样状态（A，A）只能转移为（A，B）或者（A，D）；状态（A，B）也只能转移为（D，B）……
　　根据这样的转移规则得到图1的状态转移图如下：


（A，B） （D，B） （D，C） （D，E）
（A，A） （E，E）
（A，D） （B，D） （C，D） （E，D）

(图2)

　　显然，这是一张有向无环图。其中，点表示状态，边表示状态之间的转移关系。对应于本题，状态每发生一次转移，就经过一个新的城市，题目中要求的经过城市数目最多，也就是说状态转移的次数最多，对应于图2也就是从点（A，A）到点（E，E）经过的边数最多。如果，我们规定图2中的所有的边的权重都为-1，那么问题的最优解就对应于图2中从点（A，A）到点（E，E）的一条最短路径。
　　通过上述的对问题的抽象、变形，问题就转化为我们熟悉的“最短路问题”。由于图2是一张有向无环图，因此图中就不存在负回路，“最短路问题”就可以用动态规划这一数学模型策略来解决，其动态转移方程如下：



Min（u(i,k)-1） （i>＝j；j<k<=n；(k<>i) or (i=n)）
（城市j到城市k有直达航线）
ｕ（ｉ，ｊ）=
Min（u(k,j)-1） （i<＝j；i<k<=n；(k<>j) or (j=n)）
（城市i到城市k有直达航线）

｛按从西到东顺序给城市编号，u(i,j)表示(i,j)到(n,n)的最短路径的权值，u(n,n)=0｝
所能经过的最多城市数即为－ｕ（１，１）。
　　[策略3]数学模型策略2
　　题目给出的条件要求“往返”过程经过的城市数最多，也就相当于用两条路径来“覆盖”最多的城市，这两条路径的起点和终点是最西的城市和最东的城市，也就是说路径的起止是确定的。这就使我们由“从起点到终点的两条路径”联想到“从源点到汇点的两条流”。
为此，从“网络流”数学模型的角度考虑，建立一个流网络，它可以在城市网络的基础上经过　　下面的变化得到：
　　（１）把城市网络中的边的方向规定出来，即每一条边都是由西向东的。这样，城市网络就成为一张有向图。
　　（２）由于题目中规定除起点外每个城市只能经过一次，这必须在流网络上表达出来，常用的方法是把一个城市X分裂成两个点X`和X``，两点之间连一条容量为１的有向边，原来所有指向城市X的边都指向点X`；原来所有由城市X指出的边都改由点X``指出。如图3所示：

… … … X` X`` …
… X …
（图3） X

　　（３）“网络流求极值”最常用的就是求最大流或者最小费用。由于我们已经把“两条路径”看成是“两条流”，也就是说流量已经定为２，因此就无所谓什么最大流问题，只能朝着最小费用的方向考虑。而题目中又要求经过最多的城市，这就存在一个最多与最少的转化问题。我们可以做一个等效代换：“被经过的城市数目最多”就相当于“不被经过的城市的数目最少”，接着要做的就是将“不经过的城市数目”和流网络中边的费用联系起来。看下面的图示：



１ ２ ３ ４
（图4）

　　在这个城市网络中，如果选择走航线１à４，那么我们就称作城市２和３分别被“跳”过一次，同样，如果选择走航线２à４，城市３就被“跳”过一次。由于题目中规定每个城市最多被访问１次，因此，在从西向东的两次旅行中，每个城市（除了最东和最西的城市外）至少会被“跳”过一次。于是我们就得到了“被‘跳’过的总次数”和“不被经过的城市的数目”之间的关系：除最东的和最西的城市外，中间的城市若不被经过，则被“跳”过的次数为２；若被经过，则被“跳”过的次数为１。于是得到：
　　不被经过的城市数＝被“跳”过的总次数－（城市总数－２）
　　这样，“不被经过的城市数最少”就对应于“被‘跳’过的总次数最少”。我们就可以用选择某条航线“‘跳’过的城市数”作为该航线对应的边的费用，从而使问题转化为“最小费用流”问题。
　　通过上面的分析，对于图1给出的例子，可以得到下面的流网络：

D` D``
2 0 0 
A` A`` 1 0 E` E``
(S) 0 0 2 0 (T)
B` 0 B`` C` 0 C`` 1
0
(图5)
　　图中，各边的费用已在图上标出，
　　除了与源点(S)汇点(T)相关联的边容量为２外，其它各边的容量都为１

　　对这一流网络，求流值为２的最小费用流就对应于题目的一个解。
　　当然采用网络流求极值这种数学模型策略，不仅可以求“往返”（２路）的最佳航空路线，而且还可以求得３路、４路，甚至更多路的最佳航空路线，这恐怕是动态规划和搜索策略难以办到的。
　　上面用了各种不同的策略来解决同一道题，归根到底都是由问题本身的条件所决定的，不是所有的问题都可以如此求解。我们的任务就是分析题目给出的条件的内涵，获得解题的策略。这也就是说“策略源于问题”。