T-S-T三级交换网络路径搜索算法的研究

4.2 算法思想的设计

算法设计要求：

(1)对于任意给定的输入矩阵和输出矩阵，都能够得到2个中间矩阵；

(2)由输入矩阵到第一个中间矩阵只能经过一系列行内置换；

(3)由第一个中间矩阵到第二个中间矩阵只能经过一系列列内置换；

(4)由第二个中间矩阵到输出矩阵只能经过一系列行内置换。

由行内变换和列内变换的性质可以推断出after_t1(AT)和after_s(AS)矩阵的特点如下：

AT的特点：ATij=INij'(只能在同一行上进行置换)；AS的特点：AS是inport的一个置换矩阵；AS的同一列上不可能出现inport同一行上的元素。

这是由于AT同一列上不可能出现inport同一行上的元素，而AT到AS经过的是列内变换。

现在有了inport和outport，目标是通过这2个矩阵找到after_t1和after_s。从上面的设计要求和模型2个中间矩阵的特点可以看出，由inport到outport所经过的置换与由outport到inport所经过的置换是对称的，所以由outport到inpott置换所得的2个中间矩阵也是问题的解。而且inport相对于output较为确定，因此为了方便描述和算法实现，本文采用逆推法，由outport经过一系列的行内变换逆推出after_s，由after_s经过一系列的列内变换逆推出after_t1。很容易发现从after_s到after_t1只需要一个简单的排序就可以完成，因此算法的关键是由outport推导after_s。

这样本文研究的交换网络调度算法要解决的关键问题等效后分解为：将一个任意置换矩阵经过一系列的行内变换变成为同一列上不存在输入矩阵的同一行数据的置换矩阵(这是由AS的特点所决定的)。将解决这个关键问题的算法称为交换网络调度算法的核心算法。

5 关键矩阵算法的思想和步骤

5.1 高冲突值行优先排列算法

一些约定和定义：

规则：矩阵after_s同一列上不存在矩阵inport同一行上的数据。

那么对于任一给定输出矩阵outport(OP)，本算法的任务是；根据“规则”将outport的每一行元素放到after_s(AS)同行的适当位置上。例如假设现在开始第i行的排列，也就是说，第0行到第i～l行的数据已经初步放置完毕(考虑到回溯，所以说“初步”)，则前i行的每一列元素的初始矩阵行可以组成1个一维矩阵，一共n个一维矩阵，定义为垂直行阵v[0]，v。…，v[n一1]；而OP的第i行的所有元素的初始矩阵行又可以组成1 个一维矩阵(元素的初始矩阵行等于该元素整除矩阵维数的商)，定义为水平行阵h，数据结构如图3所示：



定义：垂直冲突值：vRepeat[n]，其中vRepeat[ i](i=0，1，2，…，n-1)等于u[ i]中的元素在h中的重复次数的和。

水平冲突值：hRepeat[n]，其中hRepcat[ i](i=0，1，…，n-1)等于k[ i]在v中的重复次数的和。

生存数(lifenum)：假设vRepeat[j]等于k，也就是说，O[ i]中有k个元素不能放在AS的第j列，能放在这一列的元素个数只有n-k个，定义为生存数(lifenum)，将这n-k个元素下标取出形成向量，定义为生存空间(lifespace)

5.2 高冲突值行优先排列算法的实现

算法安放数据元素时，首先从vRepeat最大的那一列开始安放hRepeat最大的符合“规则”的元素，再逐次安放vRepeat中较小的且符合“规则”的列。这样，大冲突值的元素得到优先安放，重排或回溯的可能性就大大减小。

5.2.1 主流程

(1)排列第1行数据，row=0；

(2)row=row+1，如果row≥n，则停止，否则转下一步；

(3)统计冲突值，调用判回溯算法判断是否回溯，如果回溯，调用回溯算法，否则转下一步；

(4)选择vRepeat冲突值最大的列，根据“规则”安放hRepeat中最大的元素；

(5)更新vRepeat和hRepeat；

(6)判断这一行的数据是否都安放完毕，如果是，转(2)，否则转(3)。

5.2.2 判断回溯算法

回溯条件：生存数为k，生存空间相同的列的个数和大于生存数k，则回溯，原因是某生存空间“不够分配”。例如，第i列和第j列(i不等于j)的生存数都为1和生存空间都为{2}，这样第2个元素只能放在一个位置上，也就是说，无论如何排列都无法满足“规则”，需要回溯。

定义节点数据结构如图4所示：



判回溯的算法流程：

(1)将生存数相同的所有节点串成链表，链表的序号等于生存数；

(2)从链表序号为0向链表序号为n顺序扫描链表，统计生存空间相同的节点个数，当出现节点个数大于生存数的情况，需要回溯，否则转下一步；

(3)将本链并入下一个链表；

(4)如果所有链表都不出现生存空间相同的节点个数和大于生存数的情况，则不需要回溯。

5.2.3 回溯算法

定义经历表：在回溯过程中，各元素所“呆过”的位置序列。

回溯算法流程：

(1)确定回溯元素(冲突值最大原则)；

(2)为回溯元素找一个“合法位置”；

合法条件：

规则：冲突值小于当前情况；位置不在经历表中。

(3)为其他元素找“合法位置”；