动态规划-骑士游历问题
- 格式：doc
- 大小：39.00 KB
- 文档页数：4
骑士游历问题
设有一个n*m的棋盘(2≤n≤50，2≤m≤50)，如下图。
在棋盘上任一点有一个中国象棋马，
马走的规则为：
1.马走日字
2.马只能向右走。
即下图所示：
当n，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。
例如：(n=10，m=10)，(1，5)(起点)，(3，5)(终点)。
应输出2(即由(1，5)到(3，5)共有2条路径，如下图)：
输入：
n，m，x1，y1，x2，y2(分别表示为：n，m，起点坐标，终点坐标)
输出：
路径数目(若不存在从起点到终点的路径，输出0)
分析：
使用回溯法是可以计算路径数目，但问题是搜索效率太低，根本不可能在较
短的时间内出解。
因为题目并不要求每一条路径的具体走法。
在这种情况下，是否非得通过枚举所有路径方案后才能得出路径数目，有没有一条简便和快效的“捷径”呢。
从(x 1，y 1)出发，按照由左而右的顺序定义阶段的方向。
位于（x ，y ）左方且可达（x ，y ）的跳马位置集合都是（x ，y ）的子问题，起点至（x ，y ）的路径数实际上等于起点至这些位置集的路径数之和（如下图）。
如此一来，状态转移关系便凸显出来。
设状态转移方程map ，其中map[i ，j]为起点（x1，y1）至（i ，j ）的路径数目。
由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此不妨设map 数组的元素类型为extended 。
初始时，除map[x1，y1]=1外其余为０。
显然
}),(],[],[{],[),),(在界内的坐标集可达（y x y x map j i map y x map y x j i ∑∈+=。
采用动态程序设计的方法计算起点（x1，y1）至终点（x2，y2）的路径数目map[x2，y2]：
阶段j ：中国象棋马当前的列位置(y 1≤j ≤y2)；
状态i ：中国象棋马在j 列的行位置（1≤i ≤n ）；
决策k ：中国象棋马在（i ，j ）的起跳方向(1≤k ≤4)；
计算过程如下：
fillchar(map ，sizeof(map)，0)；
map[x1，y1] ←1； {从（x1，y1）出发}
for j ←y1 to y2 do {递推中国象棋马的列位置}
for i ←1 to n do {递推中国象棋马在j 列的行位置}
for k←1 to 4 do {递推中国象棋马在（i，j）的4个跳动方向} begin
中国象棋马由（i，j）出发，沿着k方向跳至（x，y）；
if (x∈｛１..n｝)∧(y∈{1..y2}) {计算状态转移方程}
then map[x，y] ←map[i，j]+map[x，y]
end；{for}
writeln(map[x2，y2]：0：0) {输出从（x1，y1）到（x2，y2）的路径数目} 上述算法的时间复杂度为O（n2），明显优于回溯法的效率。
程序代码如下：
program qishiyouli;
const
maxm=50;
maxn=50;
var
m,n,x1,y1,x2,y2:integer;
i,j,k,x,y:integer;
map:array[-2..maxm+2,-2..maxn+2] of extended;
begin
fillchar(map,sizeof(map),0);
readln(m,n,x1,y1,x2,y2);
map[x1,y1]:=1;
for i:=x1+1 to x2 do
for j:=1 to m do
map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1]; writeln(map[x2,y2]:0:0);
end.
出师表
两汉：诸葛亮
先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。
然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。
诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。
宫中府中，俱为一体；陟罚臧否，不宜异同。
若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。
侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。
将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。
亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。
先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。
侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也。
臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。
先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。
后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。
先帝知臣谨慎，故临崩寄臣以大事也。
受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；故五月渡泸，深入不毛。
今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。
此臣所以报先帝而忠陛下之职分也。
至于斟酌损益，进尽忠言，则攸之、祎、允之任也。
愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。
若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。
臣不胜受恩感激。
今当远离，临表涕零，不知所言。
