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

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

判回溯的算法流程：

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

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

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

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

5.2.3 回溯算法

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

回溯算法流程：

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

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

合法条件：

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

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

6 算法的正确性证明和复杂度分析

从前面的分析可以知道，要解决整个交换算法的关键是确定和寻找中间矩阵after_s，也就是说，在解决问题之前，必须确定问题有解。如何确定after_s一定存在，这里可以通过组合数学中的抽屉原理证明必然存在这样的矩阵，证明过程比较简单，本文在这里不做推导证明。

从前面的理论分析中知道，衡量交换算法有2个重要的指标：交换次数和比较次数。为了统计本文所研究的交换算法的性能，本文针对不同阶数矩阵的交换次数和比较次数做了系统的统计：

(1)对于每一行数据，由于统计冲突值、判回溯算法和元素的安放算法都是多项式复杂度，所以，在不存在回溯的条件下，本算法是多项式复杂度。

(2)在本算法中，“冲突”起着非常重要的作用，本身回避了许多回溯可能。即使回溯，本行可供回溯元素和非回溯元素“待”的位置个数非常有限，所以元素回溯的空间很小。

下面本文给出在不回溯的情况下，对高冲突行优先排列算法在阶数递增变化时，50次平均交换次数和比较次数统计结果如表1所示。

从前面对该算法的描述可知，该算法通过使每个元素“找到”尽可能适合自己的位置，从而回避了重新排列的许多可能，对于一行来说，完全避免了全排列，而且大大减小回溯概率。由于对大多数(约80％)矩阵来说，是不会出现回溯的，只有类似这样的矩阵才有可能出现回溯(也可能不回溯)，即，AS的某些行，可供选择的初始行太少。所以，该算法是一个近似多项式的算法，在不回溯的情况下，是多项式算法。该算法基本上能够完成交换网络的路径接续，他有一个很大的优势就是在交换过程中交换的次数达到最小，这样也就大大提高了寻找交换路径的效率。本算法具有良好的特性，而且通过芯片级联可实现。