程序员的算法趣题Q57: 最快的联络网

1. 问题描述

2. 解题分析

2.1 学生的状态

学生的状态可以分为以下几种：

S0: 尚未收到联络的学生，最终必须变为0

S1: 直接收到老师联络的学生。这一类学生可以继续联络其他学生，也可以就此打住，他们即便处在某一联络分支的最末端，也不需要给老师回电。他们不会变为其他类别

S2: 收到来自其他学生的联络，且尚未发出联络的学生。这一类的学生不能在他自己收到联络后就此打住，必须联络其他学生或者给老师回电。分为以下几种情况：

1. 如果他联络其他学生的话，就变为S3类型（之后他还可以继续联络其他学生）
2. 如果他联络过其他学生的话（变为S3类型），就不能（不应该）再给老师回电
3. 如果他在收到联络后给老师回电（变为S4类型）的话，后面就不应该再联络其他学生

S3: 收到来自其他学生的联络，且联络过其他学生（由S2类型变化而来）。这一类学生后续可以继续联络别的学生，也可以就此打住

S4: 给老师回过电话的学生。这类学生可能是来自于S2.他们不能再联络别人，即可以看作已经完成联络而退出联络网

进一步，由于学生之间仅按以上状态区分，而不区分个人身份。所以重要的只是处于各个状态的学生的人数，以及某个状态有几个学生给状态S0的学生或者老师打电话，而不关心具体是谁打电话谁接电话。

以小写的s0~s4分别对应于处于状态S0~S4的学生的个数，初始状态为s0=N, s1=s2=s3=s4=0.

最终的状态应该为s0=0, s2=0, 其它s1,s3,s4只要满足s1+s3+s4=N即可。

2.2 学生状态转移

状态转移取决在某个状态可以发生什么样的动作。注意，以下假定不会出现打电话冲突的情况，比如说同时两个人给老师打电话，或者同时两个人给某个S0状态的学生打电话。

老师(以下简记为T)可能有三种动作：

Case-T1：Do nothing, just wait

Case-T2：给处于S0状态的学生打电话

Case-T3：接听某个处于S2状态的学生的电话

以下分这三种情况讨论。

Case-T1：Do nothing, just wait

在这种情况下，处于S2,S3,S4的学生都可能给处于S0状态下的学生打电话，只要满足总的电话数不超过S0人数个数。所以可以通过以下所示的三重嵌套循环来遍历所有各种情况：

在以上各种组合中，各状态的人数变化情况分析如下(以[S1 to S0]表示一个S1状态的人给一个S0状态的人打电话，余者类推)：

每个[S1 to S0]会导致一个S0状态的学生变为一个状态S2的学生，S1状态人数不变

每个[S2 to S0]会导致一个S0状态的学生变为一个状态S2的学生，同时打电话者本人变化为S3状态

每个[S3 to S0]会导致一个S0状态的学生变为一个状态S2的学生，S3状态人数不变

由于老师没有接电话，所以S4人数不变

因此当k,j,l分别表示[S1 to S0]、[S2 to S0]、[S3 to S0]的人数时，各状态人数变化如下：

Case-T2：给处于S0状态的学生打电话

老师给S0状态的学生打电话，会导致一个学生从S0变到S1。同时，供S1,S2,S3打电话的S0的人数个数比Case-T1少了一个。

各状态人数变化状况可以参照Case-T1进行分析，此处不再赘述

Case-T3：接听某个处于S2状态的学生的电话。

注意只有当s2大于0时才有可能

老师接听某个S2状态的学生打电话，会导致某个S2状态学生变为S4。

其它S1,S2,S3打电话的S0的人数分配与Case-T1相同。

各状态人数变化状况可以参照Case-T1进行分析，此处不再赘述

各学生状态之间的转移

处于各个状态的人数的变化情况可以图示如下（注意，这个并不是有限状态机的状态转图，虽然看起来很像，我一时没有找到更好的表现方式）：

2.3 广度优先搜索

基于以上讨论，原问题可以重新表述为从状态（这个状态是指整个宏观状态，不要与以上学生状态S0~S4混淆！）[s0,s1,s2,s3,s4] = [N,0,0,0,0]出发，经过以上允许的联络方式变化到[0,k1,0,k2,k3]）所需要的最短的时间，显然这是一个图搜索之最短距离问题，因此可以用广度优先搜索算法来解决。

算法流程如下：

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Sun Oct 31 13:28:06 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
from   collections import deque
import itertools as it
import numpy as np

print(__doc__)

N = 12
start   = tuple([14,0,0,0,0]) #S0,S1,S2,S3,S4

q       = deque() # Used as Queue for BFS
visited = set()

q.append((start,0))
visited.add(start)

tStart  = time.perf_counter()    
dbg_cnt = 0
teacher_call_and_called_cnt = 0
while len(q) > 0:
    cur,step = q.popleft()    
    dbg_cnt += 1
    if dbg_cnt%10000 == 0:
        print('cur={}, step={}'.format(cur,step))
    # print('cur={}, step={}'.format(cur,step))
    # if dbg_cnt == 10:
    #     break

    s0,s1,s2,s3,s4 = cur
    print('dbg_cnt=',dbg_cnt,cur,s0,s1,s2,s3,s4)
    
    if cur[0]==0 and cur[2] == 0:
        print('Reach the goal!, dbg_cnt = {}'.format(dbg_cnt))
        break

    
    # Teacher wait
    for k in range(min(s0,s1)+1):             # S1 call S0
        for j in range(min(s0-k,s2)+1):       # S2 call S0
            for l in range(min(s0-k-j,s3)+1): # S3 call S0
                s0_nxt = s0 - (k+j+l) # S1 call S0: S0-->S3;
                s1_nxt = s1
                s2_nxt = s2 + k + l
                s3_nxt = s3 + j
                s4_nxt = s4
                nxt = tuple([s0_nxt,s1_nxt,s2_nxt,s3_nxt,s4_nxt])
                if nxt not in visited:
                    q.append((nxt,step+1))
                    visited.add(nxt)
    # Teacher call student in S0 state
    # T_call = False
    for k in range(min(s0-1,s1)+1):
        for j in range(min(s0-k-1,s2)+1):
            for l in range(min(s0-k-j-1,s3)+1):
                s0_nxt = s0 - (k+j+l) - 1
                s1_nxt = s1 + 1
                s2_nxt = s2 + k + l
                s3_nxt = s3 + j
                s4_nxt = s4
                nxt = tuple([s0_nxt,s1_nxt,s2_nxt,s3_nxt,s4_nxt])
                if nxt not in visited:
                    T_call = True
                    q.append((nxt,step+1))
                    visited.add(nxt)    
    # if T_call:
    #     teacher_call_and_called_cnt += 1
        
    # Teacher receives a call from state S2
    # T_called = False
    if s2 > 0:
        for k in range(min(s0,s1)+1):
            for j in range(min(s0-k,s2-1)+1):
                for l in range(min(s0-k-j,s3)+1):
                    s0_nxt = s0 - (k+j+l)
                    s1_nxt = s1
                    s2_nxt = s2 - 1 + l + k
                    s3_nxt = s3 + j
                    s4_nxt = s4 + 1
                    nxt = tuple([s0_nxt,s1_nxt,s2_nxt,s3_nxt,s4_nxt])
                    if nxt not in visited:
                        T_called = True
                        q.append((nxt,step+1))
                        visited.add(nxt)    
    # if T_called:
    #     teacher_call_and_called_cnt += 1
        
tCost  = time.perf_counter() - tStart
print('N={0}, steps = {1}, tCost = {2:6.3f}(sec)'.format(N,step,tCost))
# print('teacher_call_and_called_cnt = {}'.format(teacher_call_and_called_cnt))

Reach the goal!, dbg_cnt = 1246

N=12, steps = 7, tCost = 0.530(sec)

4. 后记

这道题是到目前为止碰到的最“硬”的，放在脑袋中想了好多天（后面的几乎所有问题都快扫荡完了）。关键在于不知道该如何把问题转化为容易为计算机处理的问题（大部分的算法难题都是这样的，找到适当的问题转化方式是关键），剩下还有一道Q56（鬼脚图中的横线）也是这样的。不过好歹坚持着不看原书答案给出了一个方案，在草稿纸上在白板上画了好多不同的思路和方案。。。只不过恰好原书不在手头，不知道这个答案是不是正确。而且以上题解还没有给出在最短联络时间条件下老师实际打电话和接电话的次数的统计--植入了代码的，但是应该是想错了，而且经过长途跋涉之后失去了耐心，留待后面再来解决追加吧。