5.2　问题(2)模型的建立与求解

5.2　问题(2)模型的建立与求解

5.2.1　模型Ⅰ

1)模型Ⅰ的分析

由于问题(2)中加了4个条件,用“Z”字搜索模型进行匹配更加复杂了。首先每台控制器都有被限制与传感器通信的时间,即它工作是不连续的,因此基于问题(1)中给出的“Z”字搜索模型,我们需要对控制器序列也进行搜索。

2)模型Ⅰ的建立与求解

它虽然看似放宽了一对一匹配的条件,给出一个传感器至多可与两台控制器通信的条件,即可以一对二或一对一匹配,但实际上给处理问题带来了很大的麻烦,为此,在可匹配的控制器多于可匹配的传感器时,我们要在一对一的基础上对已匹配过的传感器做第二次的匹配,即扫描搜索2次。

同时控制器01和02不能同时控制同一个传感器,这个条件只有在控制器01和02同时可工作的状态下才需要考虑,因此它们同时可以工作时,将控制器01匹配的传感器进行标记,控制器02匹配传感器时要判断是否被控制器01控制过。同理,控制器03和04也可用这种方法解决。也就是程序中多了几个分支,解决起来并不困难。而且扫描搜索2次同样具有随机性,每个传感器都有可能被匹配2次,而时间的相对均衡并不影响。但对传感器类的控制数量的相对均衡同样放宽要求了。程序流程图跟问题(1)类似。

在得到的解中我们同样发现大部分传感器都能够接收完整指令信息,说明“Z”字搜索匹配模型在问题(2)中也可以给出较优化的解。

5.2.2　模型Ⅱ

我们仍用随机匹配模型来解问题的可行解。

对于问题(2)中的二对一匹配。

Step1 我们首先在控制器的类集合中随机选取一个类;

Step2 在该类中随机选取一个可匹配的传感器;

Step3 接下去我们要随机决定该传感器匹配1个控制器还是两个控制器,然后在控制器集合中寻找可匹配的控制器,直到控制器集合和传感器集合中不再有可匹配的对象。

Step4 由于要求01与02号控制器分别控制不同的传感器,03与04号控制器分别控制不同的传感器,所以当一个传感器决定要和两个控制器匹配时,我们考虑了随机产生的两个控制器不能同时出现1号和2号或者同时出现3号或4号。在算出初解后将不能完整接收指令信息的传感器的所有匹配删除,实现控制器的高效,最终得到较优的解。