利用回顧調整方法來降低交叉點數量

淡江大學機構典藏 > 工學院 > 資訊工程學系暨研究所 > 學位論文 > Item 987654321/34964

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/34964

题名:	利用回顧調整方法來降低交叉點數量
其它题名:	Retracing and adjusting edge algorithm for crossing reduction
作者:	蕭宏仁;Hsiao, Hung-jen
贡献者:	淡江大學資訊工程學系碩士在職專班蔡憶佳
关键词:	交叉點;Crossing Number;Two Pages Routing
日期:	2009
上传时间:	2010-01-11 05:49:51 (UTC+8)
摘要:	「最小化交叉點問題」是指將網路節點配置在平面上，試著去找出一個較佳的配置方式，使得網路連線與連線之間產生的交叉點最少。在許多的應用中，例如Circuit Board Layout、VLSI Circuit Layout、Automated Graph Drawing等，「最小化交叉點問題」一直是相當重要的一環，愈低的交叉點數量，往往代表著愈低的成本。在這篇論文中，我們研究的題目比「最小化交叉點問題」更特定，我們僅討論FLCNP（Fixed Linear Crossing Number Problem）。FLCNP類似k-pages book crossing number中的兩頁交叉點問題，指將所有的節點排成一條直線，我們稱之為「節點線」，由節點線所區隔開的上下兩個區域我們稱之為「頁面」。節點與節點在連接時，該連線必須以弧線的方式在上下兩個頁面做連接，連線不可從任一邊的頁面跨越節點線到另一邊的頁面。另外還需符合兩個條件，一是節點為有順序性而且是預先就知道的；二是節點的位置是固定不可變動的。我們藉由實作幾個現有的演算法，分析其優缺點，進而提出利用回顧調整的方式來有效降低交叉點的數量 This thesis studies the problem of crossing number reduction in drawing a graph on a two dimensional plane. Crossing number reduction problem is an important part among many applications, such as circuit board layout, VLSI circuit layout and automated graph drawing and so on. For those applications, lower crossing number means lower cost. This thesis focus on the reduction of crossing number in FLCNP (Fixed Linear Crossing Number Problem). The problem of fixed linear crossing number is to arrange all network nodes along a “node line” according to a pre-arranged order. Each edge is drawn as a semicircle above or below the node line. Existing heuristic algorithm of crossing reduction are analyzed and a “retracing and adjusting edge algorithm” for effective crossing reduction are proposed in this thesis.
显示于类别:	[資訊工程學系暨研究所] 學位論文

文件中的档案:

档案	大小	格式	浏览次数
	0Kb	Unknown	327	检视/开启

在機構典藏中所有的数据项都受到原著作权保护.

TAIR相关文章

数据加载中.....