【动态规划】电路布局问题

简介：
简介：本项目探讨了利用动态规划算法解决电路布局优化的问题，旨在寻找最短连线路径或最小成本配置，提高电路板设计效率和性能。 问题描述：在一块电路板的上、下两端分别有n个接线柱。根据电路设计要求，用导线(i, π(i)) 将上端接线柱i与下端接线柱π(i)相连，其中π(i), 1 ≤ i ≤ n 是{1,2,…,n}的一个排列。每条导线(I, π(i)) 称为该电路板上的第i条连线。对于任何1 ≤ i ≤ j ≤ n，第i条连线和第j条连线相交的充要条件是π(i) > π(j)。给定一个具体的例子：π(i)={8，7，4，2，5，1，9，3，10，6}。 在制作电路板时需要将这n条连线分布到若干绝缘层上，在同一层上的连线不相交。电路布线问题要求确定哪些连线安排在第一层上以使得该层上有尽可能多的连线。换句话说，这个问题是寻找导线集Nets = {i, π(i), 1 ≤ i ≤ n} 的最大不相交子集。 最优子结构性质：记 N(i,j) = {t|(t,π(t)) ∈ Nets,t ≤ i, π(t) ≤ j}. N(i,j)的最大不相交子集为MNS(i,j)，Size(i,j)=|MNS(i,j)|。即： 1. 当i=1时， 2. 当i>1时，分两种情况： ① 若j <π(i)，此时 (i, π(i)) 不属于N(i, j)。 该问题的核心在于确定导线集的最大不相交子集以减少连线之间的交叉。