基本信息
文件名称：计算机算法设计与分析（第6版）课件 ch0307电路布线.pptx
文件大小：6.6 MB
总页数：20 页
更新时间：2025-09-05
总字数：约2.87千字
文档摘要
电路布线
LETSEMBARKONTODAYSSHARINGJOURNEYTOGETHER
01
问题背景与定义
Letsembarkontodaysjourneyofsharingandcommunicationtogether
电路布线问题的实际背景
在一块电路板上，上下两端各有n个接线柱，需用导线将上端接线柱i与下端接线柱π(i)相连。为避免短路，同层连线不得相交，需将连线分配到不同绝缘层。该问题可抽象为在排列π中找出最大不相交子集，为后续算法设计奠定场景基础。
电路布线问题场景描述
相交条件与问题目标
当且仅当ij且π(i)π(j)时，两条连线相交。基于此