电梯直达

1楼 [收藏(0)] [报告]

发表于 2006-09-22 00:04 |只看该作者 |倒序浏览

给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚称为网组。现要求设计一个算法来确定：对于给定的网组，能否合理地布设电线以使其不发生交叉。

2楼 [报告]

发表于 2006-09-22 10:25 |只看该作者

考查每对网组，若存在两个网组的点连接的直线在矩形区域内有交叉，则无解。
这个单层的PCB板是很难布线的。

3楼 [报告]

发表于 2006-09-22 15:09 |只看该作者

原帖由 美丽人生 于 2006-9-22 10:25 发表
考查每对网组，若存在两个网组的点连接的直线在矩形区域内有交叉，则无解。
这个单层的PCB板是很难布线的。

有具体的算法思路吗?用咩数据结构实现呢?

4楼 [报告]

发表于 2006-09-22 16:25 |只看该作者

图论嗷嗷，平面图的知识

5楼 [报告]

发表于 2006-09-22 17:35 |只看该作者

晕

6楼 [报告]

发表于 2006-09-23 00:58 |只看该作者

图论——平面图
图是非片面图的等价条件是：
该图不存在任何子图与基本非平面图同胚。
基本非平面图只存在两种同构：
1：5个顶点的完全图
2:6个顶点的图：
010101
101010
010101
101010
010101
101010

[算法] 开关盒布线算法 [复制链接]