基于剪枝法的Costas阵列通用搜索算法

The Generl Algorithm Searching for Costas Arrays Based on the Method of Branch-Cutting

给出了一种基于剪枝法的Costas阵列通用搜索算法 .由于采用了剪枝法 ,在遍历过程中剪去了不满足Costas阵列条件的分枝 ,这样既避免了大量不必要的回溯 ,又在遍历的同时生成了Costas阵列 ,而不需另外判断是不是Costas阵列 ,因而比遍历加判断的回溯算法效率更高 .用汇编语言程序实现了该算法 ,并穷尽地求出了一定阶数 (1≤n≤ 2 0阶 )的所有Costas阵列 ,实验结果表明杨义先等关于Costas阵列的第 4猜想不成立 .

This paper presents a general algorithm for searching Costas arrays based on the method of branching-cutting, which cuts off all the branches not satisfying the conditions for Costas arrays so that not only a large number of unnecessary backtrackings are avoided but also Costas arrays are generated at the same time without any additional judgment. Thus it is more effective than the algorithm which needs judgment in the process of traversing. Moreover, we implemented the algorithm in assembly language for the sake of higher effectiveness, and have found all the N(N ostas arrays with a given N(1≤N≤20). The experimental results indicate that the Yang Yixian s fourth guess at Costas arrays is incorrect.