你好,欢迎来到中学生信息学竞赛网  

网站首页  |  收藏本站  |  报名热线:400-6967-311  |  官方QQ群:167322136

信息学竞赛QQ群
167322136
您当前所在位置:首页 > 辅导资料
辅导资料

解题策略源于问题

发布时间:2016-12-16 18:16:26

解题策略源于问题

皇告锋

    策略,从广义上讲,是指解决问题所采取的方法。它包括解决方方面面各种问题的方法,例如:工作需要策略、学习需要策略、战争需要策略……本文讨论的策略,是指利用计算机编程解题时所采用的行之有效的方法,即编程解题策略。

    为了论述的方便,我们约定:策略是一个宏观概念,算法是微观上的操作方法。在利用计算机解决问题时,先设法找到解决问题的策略,再根据这一策略构造出适当的算法,编写程序解决问题。显然,如何获得解决问题的策略(或称之为策略的谋划),是解决问题不可缺少的先驱过程。从某种意义上说,在谋划宏观策略的同时,也应考虑微观算法的实现。

    编写程序解决问题常见的策略有:数学模型(规律)策略、分治策略、贪心策略、穷举(含搜索)策略等等。本文的任务是探讨策略的谋划(如何获得解决问题的策略)。

 

    显然,解决同一个问题可以采用多种不同的策略,对于一个具体问题能够想到采用某种策略来解决它,是个人的分析思维能力的表现。但是,一个问题是否可以采用某种策略来解决,或者怎样采用某种策略,从本质上说,是由问题本身的性质所决定的,也就是说,寻求解决问题的策略必须从问题给出的条件入手。

    问题一:(最佳航空路线问题)你在加拿大航空公司组织的一次竞赛中获奖,奖品是一张免费机票,可在加拿大旅行,从最西的一个城市出发,单方向从西到东经若干城市到达最东的城市,然后再单方向从东到西飞回起点。除起点城市外,任何城市只能访问一次。起点城市被访问二次:出发一次,返回一次。除指定的航线外,不允许乘其它航线,也不允许使用其它交通工具。求解的问题是:给定城市表列及两城市之间的直通航线表列,请找出一条旅行航线在满足上述限制条件下,使访问的城市尽可能多。

对于这个大家熟悉的问题,我们分析下面几种解题策略:

    [策略1]搜索策略

这个问题有明确的状态表示,而且状态之间的转移规则也是确定的,可以由初状态开始,根据状态转移规则,逐个枚举出所有的可能状态,从而得到答案。这就是状态穷举策略,也就是我们常说的搜索策略

    确定了采用搜索策略之后,还有一个实施策略的方法问题。如果仅从实际旅行的路线来看,可以先从西向东,再从东向西,搜索出一条旅行路径,这就是单路搜索。根据题目给出旅行先从西到东,再从东到西的条件,可以换个角度思考,把这一次往返的旅行看成是两次单程的从西到东的旅行。经过这样的转变之后,可以同时从西向东搜索出两条路径,这就是双路搜索。从题目的条件中又可以知道,从东到西的路径也可以看成是从西到东的路径,于是就可以从东、西两个方向同时向中间搜索,采用双向搜索,甚至还可以同时结合前面说过的双路搜索得到双向双路搜索。

    上面所说的搜索策略,不论是单向还是双向,也不管是单路还是双路,都是针对问题给出的旅行信息而得到的。

    [策略2]数学模型策略1

    我们根据题目所给出的条件,对问题的形式进行转化。

    把一次往返的旅行看成是两次单程的从西到东的旅行,同时考虑两路的旅行路线来描述问题的状态,其状态可以表示为:(XY),其中XY分别表示当前两条路线所达到的城市。例如:在图1所表示的航线中,初始状态就是(AA),结束状态是(EE)。

 

D

 

A E

 

B C

(图1

 

    由于在一个状态中包含有两条路径的信息,因此在状态转移过程中就有一个优先问题。从状态(AB)到(DC,可以先转移到(AC)再转移到(DC,也可以先转移到(DB)再转移到(DC)。这显然是一种重复。为了解决这一问题,我们可以规定状态转移时仅取离开始点较近的那一个城市,若两个城市离开始点一样近就可以任取一个城市。这样状态(AA)只能转移为(AB)或者(AD);状态(AB)也只能转移为(DB……

    根据这样的转移规则得到图1的状态转移图如下:

 

 

AB) (DB) (DC) (DE

AA) (EE

AD) (BD) (CD) (ED

 

(2)

 

    显然,这是一张有向无环图。其中,点表示状态,边表示状态之间的转移关系。对应于本题,状态每发生一次转移,就经过一个新的城市,题目中要求的经过城市数目最多,也就是说状态转移的次数最多,对应于图2也就是从点(AA)到点(EE)经过的边数最多。如果,我们规定图2中的所有的边的权重都为-1,那么问题的最优解就对应于图2中从点(AA)到点(EE)的一条最短路径。

    通过上述的对问题的抽象、变形,问题就转化为我们熟悉的最短路问题。由于图2是一张有向无环图,因此图中就不存在负回路,最短路问题就可以用动态规划这一数学模型策略来解决,其动态转移方程如下:

 

 

 

Minu(i,k)-1) (i>jj<k<=n(k<>i) or (i=n)

(城市j到城市k有直达航线)

u(i,j)=

Minu(k,j)-1) (i<ji<k<=n(k<>j) or (j=n)

(城市i到城市k有直达航线)

 

{按从西到东顺序给城市编号,u(i,j)表示(i,j)(n,n)的最短路径的权值,u(n,n)=0

所能经过的最多城市数即为-u(1,1)。

    [策略3]数学模型策略2

    题目给出的条件要求往返过程经过的城市数最多,也就相当于用两条路径来覆盖最多的城市,这两条路径的起点和终点是最西的城市和最东的城市,也就是说路径的起止是确定的。这就使我们由从起点到终点的两条路径联想到从源点到汇点的两条流

为此,从网络流数学模型的角度考虑,建立一个流网络,它可以在城市网络的基础上经过    下面的变化得到:

    (1)把城市网络中的边的方向规定出来,即每一条边都是由西向东的。这样,城市网络就成为一张有向图。

    (2)由于题目中规定除起点外每个城市只能经过一次,这必须在流网络上表达出来,常用的方法是把一个城市X分裂成两个点X`X``,两点之间连一条容量为1的有向边,原来所有指向城市X的边都指向点X`;原来所有由城市X指出的边都改由点X``指出。如图3所示:

 

… … … X` X`` …

… X …

(图3X

 

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

 

 

 

(图4

 

    在这个城市网络中,如果选择走航线1à4,那么我们就称作城市2和3分别被过一次,同样,如果选择走航线2à4,城市3就被过一次。由于题目中规定每个城市最多被访问1次,因此,在从西向东的两次旅行中,每个城市(除了最东和最西的城市外)至少会被过一次。于是我们就得到了过的总次数不被经过的城市的数目之间的关系:除最东的和最西的城市外,中间的城市若不被经过,则被过的次数为2;若被经过,则被过的次数为1。于是得到:

    不被经过的城市数=被过的总次数-(城市总数-2)

    这样,不被经过的城市数最少就对应于过的总次数最少。我们就可以用选择某条航线“‘过的城市数作为该航线对应的边的费用,从而使问题转化为最小费用流问题。

    通过上面的分析,对于图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)相关联的边容量为2外,其它各边的容量都为1

 

    对这一流网络,求流值为2的最小费用流就对应于题目的一个解。

    当然采用网络流求极值这种数学模型策略,不仅可以求往返(2路)的最佳航空路线,而且还可以求得3路、4路,甚至更多路的最佳航空路线,这恐怕是动态规划和搜索策略难以办到的。

    上面用了各种不同的策略来解决同一道题,归根到底都是由问题本身的条件所决定的,不是所有的问题都可以如此求解。我们的任务就是分析题目给出的条件的内涵,获得解题的策略。这也就是说策略源于问题

文章来源于网络
了解更多资讯可关注天科学堂自主招生网(www.goodedus.com)、微信公众号【jingsai985】和奥林匹克学科竞赛网(www.jingsai985.com

本页标题:解题策略源于问题
本页网址:http://www.noip.org.cn//news/view.php?id=772
信息原创:中学生信息学竞赛网,版权所有,转载请注明出处,并以链接形式链接网址:http://www.noip.org.cn/
上一个  :  信息学奥赛分区联赛复赛经验漫谈
下一个  :  高中三年对应年级升学后应该注意什么?建议、方法、准备