Background
现在有许多的智能家居系统，比如”华米”，都可以使用APP来自定义命令实现家居的智能控制。但是不知道大家想过没有这可能会出现一些问题。比如一位用户他设定了两个命令：当湿度大于10，开启空调；当温度小于26度，关掉空调。那么假设如果现在环境湿度从9到10，温度从26度变为25度，那么空调到底应该是关还是开呢？很显然，我们应该在用户设定命令的时候就检查出这类隐藏的逻辑错误。那么在探讨如何有效地解决问题前，势必要对原问题就行一定的抽象建模。
Abstract
首先考虑一下平常我们所使用的家居，基本上bool和continuous的抽象就能涵盖大部分场景。比如空调（开关），灯，插头等就类似于bool变量，只有开关两种可能；而空调温度，灯的亮度等属于continuous类型的变量。而用户键入的命令一般是If Condition Then Update的格式，其中Condition的形式除了通过家居的状态触发家居的变化，还有用户输入特定的语音指令。那么其实我们可以把所有的家居和指令看成一个状态中的各个变量。举个例子，假设现在房间里有灯，空调，再把指令也看作变量。同时进一步我们把布尔值也看成区间（即$True:[1, 1];False:[0, 0]$），那么初始状态$S_{0}=([0, 0], [1, 1], U)$就表达了目前灯是关着的，空调是开着的，指令不受约束（任何状态都有不受约束的状态，我们以全集来表示）。那么用户设定的命令（注意命令和指令不同）就是状态转移函数，可以表示为：$T: S × S$。比如关灯就关空调，可以表示为$([0, 0], U, U) \rightarrow ([0, 0], [0, 0], U)$。
Problem
那么我们会遇到什么问题呢？第一种冲突是每一个状态满足了多个条件，而这多个条件所导致的结果是有冲突的。那么稍微严谨的定义就是$\exists C_{1} \rightarrow U_{1}, C_{2} \rightarrow U_{2}, 且C_{1} \land C_{2} \land R_{1} \cap R_{2} = \emptyset$。这里我有些滥用符号，但大家理解意思就好，C是Condition，而U是Update。那么除了这个问题，第二种是还会出现连锁效应所造成的冲突。就是一个命令的Update会导致其它命令的Condition为真，不断传递得到矛盾的状态。这个大家可以自行想象简单的例子。其实最后还有一个细节，可以称之为第三种冲突，就是新添加的命令的条件和更新本身不能冲突。
Algorithm
那么上述的两个问题看起来要分开解决了。第一个问题的解法很直觉，我们可以假设已经存在的命令不存在第一种冲突，那么当我们把新的命令加进去的时候，可以将新命令和已经存在的命令一一比较，如果Condition不冲突，就看下Update会不会冲突。而在我们将变量都化归为区间的形式后判断冲突就很简单，即依次比较状态中的每个变量的区间是否有交集。如果所有的变量都有交集，就意味着两者不冲突。特别地，无约束和任何状态都有交集。
那么如何解决第二个问题呢？我们可以这样想，把已经存在的命令画成一张图。从Condition结点有一条指向Update结点的边。不失一般性，我们可以假设已经存在的命令不存在第二种冲突，也就是没有矛盾环。那么当我们新命令添加进去后，如果形成环的话，那么从新命令的Condition结点出发一定可以找到矛盾。同时在这个过程中我们也要考虑到连锁反应触发的可能是多个条件，所以要遍历整个命令集来找到状态的转移。最重要的是可以将第一部分的代码合并到这里的循环中，具体的实现方法可以看伪代码。显然，整体的时间复杂度是$O(N^{2}*dimension)$，其中N是命令集大小，dimension是每个状态包含的变量数，即所含的家居的个数。
（当然，我没有证明其正确性。如果发现错误的话，欢迎联系我！）
Implemention
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
orders[]: 命令集，共有N个
current: 当前状态
next: 下个状态
flag: True 标志位
newOrder: 新添加的命令
首先判断 newOrder 本身是否合法
vis[newOrder] = True
current = newOrder.Condition
next = newOrder.Update
while: N--
for order in orders[]:
if(vis[order]) {
if current 和 (order.Condition 交 order.Update) 有冲突
flag = False
End
}else {
if current 和 order.Condition 无冲突
if next 和 order.Update 有冲突
flag = False
End
else
next = next 并 order.Update
vis[current] = True
else
continue
}
current = next
End
