使用ABT(The asynchronous backtracking algorithm)算法求解四皇后(4-queens)问题

本文代码点击这里下载。

将4个皇后放入4×4的棋盘中,修改4个皇后的位置,使他们不能“立即”攻击对方。这里我们假设4个皇后被放置在不同的行中,仅能修改4个皇后的列的位置。

假设我们4个皇后的id依次是A1,A2,A3和A4,它们的优先级依次是1,2,3和4,它们的位置依次是(1,1),(2,1),(3,1)和(4,1)。算法仅能修改它们所在的列。最终使它们无法一步攻击彼此。

四皇后问题:1-2循环

  • 循环1. A1发Ok?信号给A2,A3和A4,A2发Ok?信号给A3和A4,A3发Ok?信号给A4.
  • 循环2. A2收到A1的Ok?信号后,发现自己目前的位置与A1有冲突,于是进行重新选了一个位置——(2,3),并将新位置通过Ok?信号发送给A3和A4. A3收到A1和A2的Ok?信号后,发现自己目前的位置与A1和A2有冲突,于是进行重新选了一个位置——(3,4),并将新位置通过Ok?信号发送给A4. A4收到A1,A2和A3的Ok?信号后,发现自己目前的位置与A1,A2和A3有冲突,但是无法找到可行的位置,于是发送Nogood信号给自己的上级——A3,并将A3的位置从自己的agent_view表中抹去,更新了自己的位置——(4,2).

四皇后问题:3-5循环

  • 循环3. A3收到了A2的Ok?信号,无法找到可行的位置,于是发送Nogood信号给自己的上级——A2,并将A2的位置从自己的agent_view表中抹去,为自己重新分配了位置(虽然与原先一样,因为A2被抹去后该位置不再非法)——(3,4). A3收到了A4的Nogood信号,但是由于A4发来的Nogood信号与自己的agent_view表中的数据不一致(A4在发送此Nogood信号时认为A1,A2和A3还都在第1列,因此对此Nogood信号不作理会。A4收到了Ok?信号,但其位置并不非法,因此不作理会。
  • 循环4. A2收到了A3的Nogood信号,为自己重新分配了位置——(2,4),并通过Ok?信号告知A3和A4.
  • 循环5. A3收到了A2的Ok?信号,为自己重新分配了位置——(3,2),并通过Ok?信号告知A4. A4收到了A2的Ok?信号,无法找到可行的位置,于是发送Nogood信号给A3,并将A3的位置从自己的agent_view表中抹去,为自己重新分配了位置——(3,4).

如此这般循环,找到一个可行方案。

主函数部分代码如下。

while len(ok_set) != 0 or len(nogood_set) != 0:
    for agent in agents:
        agent.handle_ok()
        agent.handle_nogood()

每次循环中,每个智能体都要处理自身收到的Ok?和Nogood信号,当没有信号在网络中传递时,程序结束。

处理Ok?信号函数的部分代码如下。

def handle_ok(self, it, ok_set, nogood_set):
    del_list = []
    i = 0
    for ok in ok_set:
        if ok.it == it - 1 and ok.receiver_id == self.id:
            print(self.id, '处理', ok)
            self.agent_view[ok.sender_id] = ok.pose
            del_list.append(i)
        i += 1
    for i in range(len(del_list)):
        # 由于i是被从小到大添加到del_list中的,因此可以这样做
        del ok_set[del_list[i]]
        for j in range(i + 1, len(del_list)):
            del_list[j] -= 1
    self.check_agent_view(it, ok_set, nogood_set, False)

可以看到,程序的实现方法是:收集上一循环中自己作为接收方的Ok?信号,并且将其添加到自己的agent_view中,最后检查自己的值(check_agent_view)。

处理Nogood信号函数的部分代码如下。

def handle_nogood(self, it, ok_set, nogood_set):
    del_list = []
    i = 0
    ignore = False
    for nogood in nogood_set:
        if nogood.it == it - 1 and nogood.receiver_id == self.id:
            del_list.append(i)
            ignore = self.ignore_nogood(nogood)
            if not ignore:
                print(self.id, '处理', nogood)
                self.add_nogood(nogood.agent_view)
            else:
                print(self.id, '忽略', nogood)
        i += 1
    for i in range(len(del_list)):
        # 由于i是被从小到大添加到del_list中的,因此可以这样做
        del nogood_set[del_list[i]]
        for j in range(i + 1, len(del_list)):
            del_list[j] -= 1
    # 没有检查是否是neighbor的步骤
    self.check_agent_view(it, ok_set, nogood_set, ignore)

与处理Ok?信号的过程比较类似,不同在于,如果Nogood信号中的内容与自己agent_view表中内容不相符,该Nogood信号会被丢弃。

check_agent_view函数的部分代码如下。

def check_agent_view(self, it, ok_set, nogood_set, send_ok):
    old_pose = [self.pose.x, self.pose.y]
    cps = np.random.permutation(range(1, self.pars['map_width'] + 1)).tolist()
    k = 0
    is_consistent, inconsistent_id = self.check_consistent()
    while not is_consistent and k < len(cps):
        self.pose.y = cps[k]
        is_consistent, inconsistent_id = self.check_consistent()
        k += 1
    if not is_consistent:
        if self.priority == 1:
            print('无解')
            sys.exit()
        self.backtrack(it, ok_set, nogood_set)
    else:
        if old_pose != [self.pose.x, self.pose.y] or send_ok:
            receivers_id = self.get_ok_receivers(self.priority)
            for receiver in receivers_id:
                ok_set.append(signals.Ok(it, self.id, receiver, copy.deepcopy(self.pose)))

可以看出,如果自己的位置是非法的,那么智能体应寻找新的位置,并且将新的位置发送给下一级智能体。

回溯(backtrack)函数部分代码如下。

def backtrack(self, it, ok_set, nogood_set):
    # 怎样判断nogood已经全部出现是一个问题
    # !!! 此处的方法存疑
    if len(self.nogood_list) >= self.pars['map_width'] ** self.pose.x:
        print('无解')
        sys.exit()
    receiver_id = self.get_nogood_receiver(self.priority)
    nogood_set.append(signals.Nogood(it, self.id, receiver_id, copy.deepcopy(self.agent_view)))
    if receiver_id in self.agent_view.keys():
        del self.agent_view[receiver_id]
    self.check_agent_view(it, ok_set, nogood_set, True)

回溯过程会判断整个算法是否已经无解。如果还无法判断是否无解,那么就将Nogood表中优先级最低的智能体的Nogood去掉,并发送Nogood信号给那个智能体,并重新检查自己的值(check_agent_view)。

请注意下面的代码:

def check_agent_view(self, it, ok_set, nogood_set, send_ok):

check_agent_view函数中有一个send_ok参数,如果该参数为True,则该智能体的位置会被Ok?信号发送到下一级智能体中。如果智能体在check_agent_view过程中发现自己的值与进入该过程前的值不一致,那么它会发送Ok?信号。那么这个参数起什么作用呢?可以看到,在下面两句中,这个参数可能被赋值为True

def handle_nogood(self, it, ok_set, nogood_set):
    self.check_agent_view(it, ok_set, nogood_set, ignore)
def backtrack(self, it, ok_set, nogood_set):
    self.check_agent_view(it, ok_set, nogood_set, True)

先来看看handle_nogood的情况,我们假设3个智能体A->B->C。在一次循环中,A发送Ok?信号给B和C,C发送Nogood信号给B。再次循环中,B发现自己目前的位置是合法的,而C的Nogood信号被忽略,也就是B没有改变的自己的位置,也没有任何信号发出;C收到Ok?信号后,发现自己目前的位置不合法,于是换了新的位置,但是与当前B位置冲突,但是由于上一次循环中,C在发送Nogood信号前把B的位置抹去了,因此C并不知情。因此,此时出现了一种奇怪的现象:B与C的位置是矛盾的,网络中却没有信号了。为了避免这种情况的发生,如果Nogood信号被忽略了(ignore==True),那么send_ok位被赋值位True,即B一定会发送Ok?信号给C。

再来看看backtrack过程得情况,我们假设有一个智能体收到了Nogood信号,在check_agent_view过程中,它改变了自己的位置,但是仍然无法找到合法的位置,此时进入backtrack过程,此时它的位置与处理Nogood信号前位置不一样(即它已经更改了自己的位置)。接下来,它在backtrack过程中发送了Nogood信号,并且将某一上级智能体的位置抹去,便又进入check_agent_view过程。当它目前的位置是合法的时候(因为某一上级智能体的位置被抹去了),它不会发送Ok?信号给下一级智能体(因为在此次check_agent_view过程中位置没变)。但是,它目前的位置与最开始相比,已经改变了,因此此时需要把send_ok设置为True

发表评论

电子邮件地址不会被公开。 必填项已用*标注