目錄

1. 問題描述

2. 解題分析

2.1 基本思路

2.2 演算法流程

2.3 實作要點

3. 代碼及測驗

4. 后記

1. 問題描述

問題：當有4*6=24個人，以12人為一組分為兩組時，求所需移動次數最多的起始狀態有多少種？

2. 解題分析

2.1 基本思路

由于終止狀態是確定的（4個），所以適合于逆向搜索（本系列前面出現過不少逆向思維解決的問題例），

位置交換動作是可逆的，從4個確定性的終止狀態開始，通過合理的位置交換操作（確保距離最小化）尋找距離4個確定性的終止狀態最遠的初始狀態，這個顯然是圖搜索中最大距離問題，適合于用廣度優先搜索演算法，

另外，由于本題要求不僅找出最大距離，還要求找出滿足這一條件的初始狀態的個數，所以相當于要找出再廣度優先搜索中出現在最遠一層的所有狀態的個數，

2.2 演算法流程

基于廣度優先搜索的演算法流程如下所示：

2.3 實作要點

當前人員狀態用二維陣列（本題解用numpy陣列）表示，為了方便判斷，與棋盤問題類似采用了外加圍欄的方式，

如以上演算法流程圖中所述，由于最后需要最終層的所有狀態個數，因此visited以字典的方式記錄狀態以及其對應的距離，

由于numpy陣列不能用作dict的key，所以，表示狀態的numpy二維陣列先變換為一維陣列，然后轉變為tuple，用作visited的key，而距離（層數, curStep），存入佇列時，則是將前述visited的key與距離（層數, curStep）組成一個嵌套式的tuple再存入，注意佇列q與visited的這兩種存盤方式的區別，

在每個格子上查詢是否可以交換時，只考慮它與右邊一格以及下邊一格交換的可能性，這樣按行掃描下去，不會遺漏也不會產生不必要的重復，這個技巧也是在前面的題目中已經出現過，

3. 代碼及測驗

# -*- coding: utf-8 -*-
"""
Created on Mon Oct 18 07:39:04 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

N = 4
M = 6

seat = np.ones((N,M))
initState1 = seat.copy()
initState1[:,:M//2] = -1
initState2 = seat.copy()
initState2[:,M//2:] = -1
initState3 = seat.copy()
initState3[:N//2,:] = -1
initState4 = seat.copy()
initState4[N//2:,:] = -1

q = deque()
visited = dict()

q.append((tuple(np.reshape(initState1, (N*M,))),0))
q.append((tuple(np.reshape(initState2, (N*M,))),0))
q.append((tuple(np.reshape(initState3, (N*M,))),0))
q.append((tuple(np.reshape(initState4, (N*M,))),0))

visited[tuple(np.reshape(initState1, (N*M,)))] = 0
visited[tuple(np.reshape(initState2, (N*M,)))] = 0
visited[tuple(np.reshape(initState3, (N*M,)))] = 0
visited[tuple(np.reshape(initState4, (N*M,)))] = 0

ansLst = []
tStart = time.perf_counter()
while len(q) > 0:    
    curState, curStep = q.popleft()
    # print(curState,curStep)
    curExt = np.zeros((N+2,M+2))
    curExt[1:N+1,1:M+1] = np.reshape(curState, (N,M))
    for k in range(1,N+1):
        for l in range(1,M+1):
            if curExt[k,l] * curExt[k,l+1] == -1:
                curExt[k,l] *= -1
                curExt[k,l+1] *= -1
                nxtState = curExt[1:N+1,1:M+1]
                if tuple(np.reshape(nxtState, (N*M,))) not in visited:
                    q.append((tuple(np.reshape(nxtState, (N*M,))),curStep+1))
                    visited[tuple(np.reshape(nxtState, (N*M,)))] = curStep+1                    
                curExt[k,l] *= -1
                curExt[k,l+1] *= -1            
            if curExt[k,l] * curExt[k+1,l] == -1:
                curExt[k,l] *= -1
                curExt[k+1,l] *= -1
                nxtState = curExt[1:N+1,1:M+1]
                if tuple(np.reshape(nxtState, (N*M,))) not in visited:
                    q.append((tuple(np.reshape(nxtState, (N*M,))),curStep+1))
                    visited[tuple(np.reshape(nxtState, (N*M,)))] = curStep+1                    
                curExt[k,l] *= -1
                curExt[k+1,l] *= -1


ansSteps = curStep    
numStates = 0
for key in visited:
    if visited[key] == ansSteps:
        ansLst.append(key)
        numStates += 1
tCost  = time.perf_counter() - tStart

print('N={0}, M={1}, ansSteps={2}, numStates={3}, {4:6.3f}(sec)'.format(N,M,ansSteps,numStates,tCost))        

運行結果：

N=4, M=4, ansSteps=10, numStates=64, 1.380(sec)

N=4, M=6, ansSteps=20, numStates=4, 479.002(sec)

4. 后記

這本書的壓卷之題，但是看著順眼一點（思路對上了^-^）所以就先拉出來辦了，但是，以上題解雖然給出了正確解答，速度卻實在不能恭維！需要嚴重優化，不過也是，壓軸之題如果就這么簡單地解決了也著實不像話(太不把村長當干不了)，欲知后事如何，且聽下回分解，我會回來的，，，

本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解