下载文档原格式
（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。
）比如有这样一组不等式：X1 - X2 <= 0X1 - X5 <= -1X2 - X5 <= 1X3 - X1 <= 5X4 - X1 <= 4X4 - X3 <= -1X5 - X3 <= -3X5 - X4 <= -3不等式组(1)全都是两个未知数的差小于等于某个常数（大于等于也可以，因为左右乘以-1就可以化成小于等于）。
这样的不等式组就称作差分约束系统。
这个不等式组要么无解，要么就有无数组解。
因为如果有一组解{X1, X2, ..., Xn}的话，那么对于任何一个常数k，{X1 + k, X2 + k, ..., Xn + k}肯定也是一组解，因为任何两个数同时加一个数之后，它们的差是不变的，那么这个差分约束系统中的所有不等式都不会被破坏。
差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。
即对于任何一条边u -> v，都有：d(v) <= d(u) + w(u, v)其中d(u)和d(v)是从源点分别到点u和点v的最短路径的权值，w(u, v)是边u -> v的权值。
显然以上不等式就是d(v) - d(u) <= w(u, v)。
这个形式正好和差分约束系统中的不等式形式相同。
于是我们就可以把一个差分约束系统转化成一张图，每个未知数Xi对应图中的一个顶点Vi，把所有不等式都化成图中的一条边。
对于不等式Xi - Xj <= c，把它化成三角形不等式：Xi <= Xj + c，就可以化成边Vj -> Vi，权值为c。
最后，我们在这张图上求一次单源最短路径，这些三角形不等式就会全部都满足了，因为它是最短路径问题的基本性质嘛。
话说回来，所谓单源最短路径，当然要有一个源点，然后再求这个源点到其他所有点的最短路径。
那么源点在哪呢？我们不妨自已造一个。
算法导论（第三版）－复习－第六部分图论22-26［转］22习题22.1-5 有向图G(V, E)的平⽅图。
链表表⽰时，对每结点u的Adj[u]中所有v加⼊队列，后边出队边将Adj[v]加⼊Adj[u]中。
矩阵表⽰时，若w[i, j]、w[j, k]同时为1则将w[i, k]置1.习题22.1-6 O(V)的时间寻找通⽤汇点。
汇点的特征是邻接矩阵的第j列除[j, j]外所有元素为1. 可将每⾏调整[j ,j]后作为⼀个整数，所有整数与运算，为1的位是汇点。
习题22.1-7 有向⽆环图的关联矩阵B，BB’每个元素C[i, j]=∑B[i, k]*B’[k, j]=∑B[i, k]*B[j, k]，即同时进i, j两结点与同时出i, j的结点总数-⼀进⼀出i, j两结点的结点总数。
习题22.2-7 类似BFS，d mod2为0则标为B（娃娃脸），d mod2为1则标为H（⾼跟鞋）。
但若有边连接相同类的结点，则⽆法划分。
wrestler(G){for each u in G{(u,v)=Adj[u];if(v.mark==u.mark){throw error;}if(v.d==NIL) {v.d=u.d+1; v.mark=v.d mod 2;}}}习题22.2-8 任意点之间的最短路径。
重复的Dijktra算法或Floyd-Warshall算法习题22.2-9 ⽆向图扩展为有向图。
问题变成要遍历所有边⼀次。
访问结点u时，将u的⼦结点v的其他边都可视为⼦集v，问题等价于u到v，访问v的集合，v到u。
u标为visiting⼊列，然后访问v，v标为visiting⼊列，然后访问v的后继结点，访问过的边标为visited，返回到visiting的点时，如果该点所有连接的边都标为visited只剩⼀条返回上级的边，则返回上级结点并将点标为visited，v出列，访问u的其他⼦结点，最终u出列。
全部结点出列后达到遍历所有边⼀次。
Contents一、定义二、详解三、例题一、定义（百度百科）：如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。
亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
求解差分约束系统，可以转化成图论的单源最短路径（或最长路径）问题。
观察xj-xi<=bk，会发现它类似最短路中的三角不等式d[v]<=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。
因此，以每个变量xi为结点，对于约束条件xj-xi<=bk，连接一条边(i,j)，边权为bk。
我们再增加一个源点s,s与所有定点相连，边权均为0。
对这个图，以s为源点运行Bellman-ford算法（或SPFA算法），最终{d[ i]}即为一组可行解。
例如，考虑这样一个问题，寻找一个5维向量x=(xi)以满足：这一问题等价于找出未知量xi，i=1,2,…,5，满足下列8个差分约束条件：x1-x2≤0x1-x5≤-1x2-x5≤1x3-x1≤5x4-x1≤4x4-x3≤-1x5-x3≤-3x5-x4≤-3该问题的一个解为x=(-5,-3,0,-1,-4)，另一个解y=(0,2,5,4,1)，这2个解是有联系的：y中的每个元素比x 中相应的元素大5。
引理：设x=(x1,x2,…,xn)是差分约束系统Ax≤b的一个解，d为任意常数。
则x+d=(x1+d,x2+d,…,xn+d)也是该系统Ax≤b的一个解。
bellman-ford算法伪代码：for each v V do d[v] <-- 无限大; d[s] <-- 0Relaxationfor i =1,...,|V|-1 dofor each edge (u,v) 属于E dod[v] <-- min{d[v], d[u]+w(u,v)}Negative cycle checkingfor each v 属于V do if d[v]> d[u] + w(u,v) then no solution在实际的应用中，一般使用SPFA(Shortest Path Fast Algorithm)算法来实现。
差分约束系统在一个差分约束系统(system of difference constraints)中，线性规划矩阵A的每一行包含一个1和一个-1，A的其他所有元素都为0。
因此，由Ax≤b给出的约束条件是m个差分约束集合，其中包含n个未知量，对应的线性规划矩阵A为m行n列。
每个约束条件为如下形式的简单线性不等式：xj-xi≤bk。
其中1≤i,j≤n，1≤k≤m。
例如，考虑这样一个问题，寻找一个5维向量x=(xi)以满足：这一问题等价于找出未知量xi，i=1,2,…,5，满足下列8个差分约束条件：x1-x2≤0x1-x5≤-1x2-x5≤1x3-x1≤5x4-x1≤4x4-x3≤-1x5-x3≤-3x5-x4≤-3该问题的一个解为x=(-5,-3,0,-1,-4)，另一个解y=(0,2,5,4,1)，这2个解是有联系的：y中的每个元素比x中相应的元素大5。
引理：设x=(x1,x2,…,xn)是差分约束系统Ax≤b的一个解，d为任意常数。
则x+d=(x1+d,x2+d,…,xn+d)也是该系统Ax≤b的一个解。
约束图在一个差分约束系统Ax≤b中，m X n的线性规划矩阵A可被看做是n顶点，m条边的图的关联矩阵。
对于i=1,2,…,n，图中的每一个顶点vi对应着n个未知量的一个xi。
图中的每个有向边对应着关于两个未知量的m个不等式中的一个。
给定一个差分约束系统Ax≤b，相应的约束图是一个带权有向图G=(V,E)，其中V={v0,v1,…,vn}，而且E={ (vi,vj) : xj-xi≤bk是一个约束}∪{ (v0,v1) , (v0,v2) , … , (v0,vn) }。
引入附加顶点v0是为了保证其他每个顶点均从v0可达。
因此，顶点集合V由对应于每个未知量xi的顶点vi和附加的顶点v0组成。
边的集合E由对应于每个差分约束条件的边与对应于每个未知量xi的边(v0,vi)构成。
如果xj-xi≤bk是一个差分约束，则边(vi,vj)的权w(vi,vj)=bk（注意i和j不能颠倒），从v0出发的每条边的权值均为0。
差分约束算法差分约束算法（Difference Constraint Algorithm）是一种用于求解差分约束系统的方法，差分约束系统是一种特殊的线性约束系统，其中约束关系为“某个变量的值与另一个变量的差的绝对值不超过某个常数”。
差分约束算法的基本思想是通过对约束条件进行适当的转换，构造一个有向图，并利用拓扑排序的方法求解变量的取值范围。
具体步骤如下：1. 将差分约束系统中的每个差分约束关系转化为两个线性约束关系。
例如，对于约束 a - b ≤ c，可以将其转化为a ≤ b + c 和b ≤ a - c；对于约束 a - b ≥ c，可以转化为a ≥ b +c 和b ≥ a - c。
2. 根据转化后的约束关系构造一个有向图，图中的每个变量表示一个节点，约束关系表示节点间的有向边。
对于每个约束关系a ≤ b + c，构造一条从节点 a 到节点 b 的有向边，边的权重为 c；对于每个约束关系a ≥ b + c，构造一条从节点 b 到节点a 的有向边，边的权重为 c。
3. 对构造的有向图进行拓扑排序，得到拓扑排序的顺序。
4. 根据拓扑排序的顺序，依次计算每个节点的取值范围。
对于每个节点 a，初始化其取值范围为负无穷大到正无穷大。
对于节点 a 的每个后继节点 b，更新节点 b 的取值范围为节点 a 的取值范围加上边的权重。
重复此步骤，直到没有节点的取值范围发生变化，即达到稳定状态。
5. 根据计算得到的每个节点的取值范围，判断差分约束系统是否可解。
如果存在某个节点的取值范围为负无穷大到正无穷大，则差分约束系统无解；否则，取值范围即为差分约束系统的解。
差分约束算法的时间复杂度为 O(nm)，其中 n 是变量的个数，m 是约束关系的个数。
这种算法通常用于求解动态最短路径等问题，具有较高的效率。
Allegro16.3约束设置Allegro16.3约束设置差分对的约束设置第一步，差分对的设置差分对的设置有很多方法，下面介绍两种最常用的方法。
1．点击菜单Logic→Assign Differential Pair... 弹出以下对话框。
点击你想要创建差分对的Net1和Net2,填入差分的名字，点击Add后就成功创建了差分对。
点击Auto Generate按钮后，弹出以下对话框：在第一个输入框填入Net的主要名字后，在下面的框中填入差分线的标志如N，P。
点击Generate即可自动产生差分对。
2.在约束管理器中设置差分对。
在DSN上点击右键，在菜单中选择Create→Differential Pair。
即可弹出下面的对话框。
和上一种方法的设置差不多，这里就不再叙述了。
第二步差分对约束规则的设置差分对各项约束可以在约束管理器中的Electric→Net→routing→Differential Pair中直接在各差分对上填入各项约束数值就可生效，但更好的方法是创建约束规则后赋给各个差分对。
在DSN上点击右键，在菜单中选择Create→Electrical CSet后，弹出下面的对话框;输入规则名后点Ok，在Electric→constraimt set→outing→Differential Pair中可以看到新规则。
在表格中输入各项数值即可完成新规则的设置。
如图所示差分对约束参数主要有以下几个：1coupling paramaters 主要包括了Primary Gap 差分对最优先线间距（边到边间距）。
Primary Width 差分对最优先线宽。
Neck Gap 差分对Neck模式下的线间距（边到边间距），用于差分对走线在布线密集区域时切换到Neck值。
Neck Width差分对Neck模式下的线宽，用于差分对走线在布线密集区域时切换到Neck值。
如图所示设置数值时在表格中右键菜单中选择change，会出现以下各层数值表格，可以在每一层上设置不同的数值。
差分对的约束设置第一步，差分对的设置差分对的设置有很多方法，下面介绍两种最常用的方法。
1．点击菜单Logic→Assign Differential Pair... 弹出以下对话框。
点击你想要创建差分对的Net1和Net2,填入差分的名字，点击Add后就成功创建了差分对。
点击Auto Generate按钮后，弹出以下对话框：在第一个输入框填入Net的主要名字后，在下面的框中填入差分线的标志如N，P。
点击Generate即可自动产生差分对。
2.在约束管理器中设置差分对。
在DSN上点击右键，在菜单中选择Create→Differential Pair。
即可弹出下面的对话框。
和上一种方法的设置差不多，这里就不再叙述了。
第二步差分对约束规则的设置差分对各项约束可以在约束管理器中的Electric→Net→routing→Different ial Pair中直接在各差分对上填入各项约束数值就可生效，但更好的方法是创建约束规则后赋给各个差分对。
在DSN上点击右键，在菜单中选择Create→Electrical CSet后，弹出下面的对话框;输入规则名后点Ok，在Electric→constraimt set→outing→Differential Pair中可以看到新规则。
在表格中输入各项数值即可完成新规则的设置。
如图所示差分对约束参数主要有以下几个：1coupling paramaters 主要包括了Primary Gap 差分对最优先线间距（边到边间距）。
Primary Width 差分对最优先线宽。
Neck Gap 差分对Neck模式下的线间距（边到边间距），用于差分对走线在布线密集区域时切换到Neck值。
Neck Width差分对Neck模式下的线宽，用于差分对走线在布线密集区域时切换到Neck值。
如图所示设置数值时在表格中右键菜单中选择change，会出现以下各层数值表格，可以在每一层上设置不同的数值。
Vivado差分时钟管脚约束1. 引言在FPGA设计中，时钟是一个关键因素。
时钟的稳定性和准确性对于设计的正确性和性能至关重要。
在Vivado工具中，差分时钟是一种常见的时钟类型，它可以提供更好的抗干扰能力和噪声容限。
本文将介绍如何在Vivado中进行差分时钟管脚约束的配置，以确保设计的正确性和稳定性。
2. 差分时钟概述差分信号由一对相互补偿的信号组成，其中一个信号是另一个信号的反相。
这种信号传输方式可以提供更好的抗干扰能力和噪声容限，因此在高速数据传输和时序要求严格的应用中广泛使用。
在FPGA设计中，差分时钟常用于数据接口、存储器接口、高速通信等场景。
为了正确地使用差分时钟，在设计过程中需要对其进行适当的约束设置。
3. Vivado工具约束设置流程步骤1：创建约束文件首先，在Vivado工程目录下创建一个新的约束文件（以.xdc为后缀），例如constraints.xdc。
步骤2：定义差分时钟在约束文件中，使用create_clock命令定义差分时钟。
语法如下：create_clock -period <period> -waveform {<rise_time><fall_time>} [get_pins <c lock_pins>]其中： - <period>表示时钟周期，单位为纳秒（ns）； - <rise_time>和<fall_time>表示上升沿和下降沿的时间，单位为纳秒（ns）； - <clock_pins>表示与差分时钟相关的管脚。
例如，定义一个50MHz的差分时钟：create_clock -period 20 [get_pins {clk_p clk_n}]步骤3：设置约束属性除了定义差分时钟周期外，还可以设置其他约束属性来进一步优化设计。
以下是一些常见的约束属性及其用法：•set_input_delay：设置输入延迟；•set_output_delay：设置输出延迟；•set_false_path：设置虚假路径（不进行时序优化）；•set_max_delay：设置最大延迟。
