TCSP-时间约束满意度问题
TSCP是一个约束满足问题,其中变量代表时间点,时间信息由一元和二进制约束集表示。
我们将TCSP与图相关联,包括:
一组具有连续域的变量X_1 to X_n
一组约束,每个约束由一组间隔表示
一元约束T_i将变量X_i的域限制为给定的间隔集。
二进制约束T_{ij}将X_j - X_i的距离值约束到一组间隔。
我们用有向约束图表示,其中节点代表变量,边i -> j指定约束T_{ij} 。
为简单起见,我们还引入了X_0 = 0 ,因此一元约束由T_{0i} 。
STP-简单的时间问题
STP是TCSP,其中所有约束都指定一个间隔。
我们将这个问题与distance graph (V, E_d) ,其中V由与约束网络相同的节点组成,并且每个边缘都由权重a_{ij}标记,表示X_j - X_i <= a_{ij} 。
输入
求解器程序的输入由std
1