相邻项序列

相邻项序列

 问题描述：

对于一个N*N（N≤100）的正整数矩阵M，存在从M[A1，B1]开始到M[A2，B2]结束的相邻项序列。两个项M[I，J]和M[K，L]相邻的条件是指满足如下情况之一：（1）I=K±1和J=L；（2）I=K和J=L±1。先要求你从文件中读入矩阵M及K（K≤4）组M[A1，B1]和M[A2，B2]，求一相邻项序列，使得相邻项之差的绝对值之和为最小。

输入格式及样例：
4                  //表示矩阵M的大小      

1   9   6   12     //每行有M个数据，共M行

8   7   3   5

5   9   11  11

7   3   2   6

2                  //表示有K组数据

4   1   1   4      //表示A1，B1及A2，B2的值，共K行

2   2   3   4

  

输出格式及样例：

1  17               //表示第1组数据相邻项之差的绝对值之和的最小值为17

7  5  8  7  9  6  12    //表示第1组数据的相邻序列

2  4                 //表示第2组数据相邻项之差的绝对值之和最小值为4

7  9  11  11          //表示第2组数据的相邻序列

　
 
算法分析：

本题若将相邻的两个数看成是两个顶点，两个数差的绝对值作为权，则问题转化为图论中的求两顶点间的最短路问题。

对于有向图D=（V，A），弧a=（Vi,Vj）,相应地有权W（a）=Wij，对有向图D中两个顶点Vs,Vt，设P是D中从Vs到Vt的一条路，定义路P的权是P中所有弧的权之和，记作W（p），所谓最短路问题就是在所有从Vs到Vt的路中，找出一条权最短的路，即求一条从Vs到Vt的路P0，令：

           W（P0）=min(p)

对于所有Wij>=0，即所有的权为非负值时，求最短路通常使用标号法。

所谓标号法的基本思想是从Vc出发，逐步地向外探寻最短路。在执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从Vs到该点的最短路的权（称为P标号），或者表示这个权的上界（称为T标号），具体做法是每扩展一步，就将一个具T标号的点改具P标号的点，从而使有向图D中具P标号的顶点数增多一个。如此一步步执行下去，就可求出从Vs到各点的最短路。

为简便起见，我们可以称从M[I，J]到M[K，L]的相邻项之差的绝对值之和最小的相邻项序列为从M[I，J]到M[K，L]的“最优序列”。这样便可用标号法来求得从起点M[A1，B1]到矩阵M的其它各项的“最优序列”。

设SUM[I，J]为从M[A1，B1]到M[I，J]的“最优序列”的相邻项的绝对值之和。有：

SUM[I，J]=MIN SUM[K，L]+ABS（M[I，J]-M[K，L]）{I=K±1且J=L，或I=K且J=L±1}

通过这一式子，可以利用标号法来求得从M[A1，B1]到M[A2，B2]的最优序列。

在标号法中，每一次扩展都要寻找一个项M[I，J]，其中：

① M[I，J]是未改为P的标号的点；

② SUM[I，J]=MIN SUM[K，L]{K，L∈[1，N]，且M[K，L]是未改为P标号的点。

这一步若采用二重循环来求则非常耗时。所以考虑采用一个队列来存储矩阵中待扩展的项，使得该队列的各项的SUM值地由小到大排列的。扩展时，只要移动队列的首指针即可：生成的新的待扩展的项，可以将其插入到队列中的适当位置，使插入后队列的各项的SUM值仍是从小到大排列。为了较方便地插入新的待扩展的项，采用指针结构来存储这个队列。

具体算法描述：

  定义一个POINT类型来记录待扩展的项：

   point=^xy;

xy=record

   x,y:byte;

   next:point;

end;

其中X，Y为该项在矩阵中的坐标，NEXT为指针类型，以记录其在队列中的后继结点。

1、  置SUM[I，J]为∞（I<>A1或J<>B1），置SUM[A1，B1]为0；

2、  首指针F后移一位；

3、  若F^.X=B2且F^.Y=A2，则已找到从M[A1，B1]到M[A2，B2]的“最优序列”，反向链接、打印所经过的路径并转6，否则继续4；

4、  从M[F^.Y,F^.X]向上下左右四个方向扩展，现设向M[NODE1^.Y,NODE1^.X](NODE1^.Y=F^.Y±1且NODE1^.X=F^.X，或NODE1^Y=F^.Y且NODE1^.X=F^.X±1)扩展：

a)     SUM1：=SUM[F^.Y,F^.X]+ABS(M[F^.Y,F^.X]-M[NODE1^.Y,NODE1^.X]);

b)      若SUM1<SUM[NODE1^.Y,NODE1^.X]，则继续c)，否则转为4；

c)      SUM[NODE1^.Y,NODE^.X]:=SUM1;

d)      M[F^.Y,F^.X]是M[NODE1^.Y,NODE1^.X]的前趋项，记下从M[NODE1^.Y,NODE1^.X]到M[F^.Y,F^.X]的方向，以便打印时反向链接所经路径；

e)       生成一新待扩展结点NODE2，使得NODE2^=NODE1^，并把NODE2插入到队列中，使得插入后队列的各项的SUM值仍是从小到大排列；

5、  转2；

6、  结束


 
 

<img src="images/post/smile/dvbbs/em04.gif" /><img src="images/post/smile/dvbbs/em04.gif" /><img src="images/post/smile/dvbbs/em04.gif" /><img src="images/post/smile/dvbbs/em04.gif" /><img src="images/post/smile/dvbbs/em04.gif" /><img src="images/post/smile/dvbbs/em04.gif" />

<P>斑竹的数据结构学得真好</P>
<P>佩服佩服！</P>

<img src="images/post/smile/dvbbs/em05.gif" />