一维逻辑阵布图的一个启发式算法

A Heuristic Algorithm for Gate and Net Assignment in One-Dimensional Logic Arrays

一维逻辑阵布图中列排序问题已被证明是一个ＮＰ（Ｎｏｎ—Ｐｏｌｙｎｏｍｉａｌ）－完全问题，本文提出一个新的启发式算法．算法的时间复杂度为Ｏ（ｒ·ｓ·｜Ｇ｜），其中｜Ｇ｜是逻辑阵的总门数，ｓ为单个线网连接的最多门数，ｒ为单门连接的最多线网数；其空间复杂度为Ｏ（｜Ｎ｜·｜Ｇ｜），其中｜Ｎ｜为线网总数．

The problem of the ordering of the columns in one-Dimensional Logic Arrays (OLA) has been proved to be an NP-complete problem.In this paper a new heuristic algorithm is proposed. The time complexity of the proposed algorithm is O(r.s.|G|), where |G| is the total number of gates of OLA, s──the maximal number of gates, connected by a single net, r──the maximal number of nets, connecting to a single gate. The space complexity of the algorithm is O(|N|·|G|), where |N| is the total number of nets.