Pages

2012年6月10日 星期日

[演算法] Constraint graphs

以下整理Constraint Graph的觀念:
1.   Ax <= b,Constraint graph的vertices數目為x向量內元素個數+1。
2.   額外多出來的vertex為v0,目的為確保vertex之間都能互通。
3.   Constraint graph中的edge對應一組Constraint。
4.   weight的表示法:w(vi,vj) = bk,代表xj - xi = bk。(i、j、k為下標的index)。
5.   只要用找出v0到各vertex的shortest path的方法,且不能有負的edge weight,就可以找出每個vertex對應的xi的解。

沒有留言:

張貼留言