1. 問題描述
2. 解題分析
搜索最短距離，圖搜索問題中的最短距離問題，可以用廣度優先搜索策略來解決，
2.1 搜索樹示意圖
搜索樹示意圖如下：
2.2 演算法流程
用一維陣串列示當前狀態，但是要注意實際上表達的是圍成一圈的狀態，
2.3 實作要點
- 0號玩家第一步固定地從把手絹丟在位置0（1號玩家）后面開始，因此BFS從1號玩家作為runner開始，0號玩家需要的步數不要忘記
- 搜索程序中不僅要記錄當前狀態，還需要記錄到目前為止累積步數，當前runner，已經當前runner從哪個位置出發
- 計算當前runner丟手絹交換位置的步數時，需要注意runner需要先跑到預定位置，然后再跑一圈才能進入位置
- 考慮到圍成一圈的對成性以及本題只要求相對位置變為逆序，因此在以上用一維陣列來表示排列狀態時，目標狀態不是一個而是經過回圈移位后等價的N個，參見代碼中的isTargets()
3. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Sat Oct 23 08:04:30 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__)
def isTargets(a, target):
for k in range(len(target)):
if np.array_equal(a, np.roll(target,k)):
return True
return False
N = 6
s0 = np.arange(1,N+1) # [1,2,3,...,N]
target = s0[::-1] # In fact, all the circular shift of it are targets
s1 = s0.copy()
s1[0] = 0 # [0,2,3,...,N]
q = deque()
visited = set()
q.append((tuple(s1),N,1,0)) # (states, step, runner, start)
visited.add(tuple(s0))
visited.add(tuple(s1))
# flog = open("Q58.log", "w")
# flog.write('state, steps, runner, start')
tStart = time.perf_counter()
isOK = False
while len(q) > 0:
cur,step,runner,start = q.popleft() #used as Queue instead of Stack in BFS.
# print(cur,step,runner,start)
# flog.write('{0}, {1}, {2}, {3},\n'.format(cur,step,runner,start))
if isTargets(cur, target):
isOK = True
break
for k in range(N):
nxt = np.array(cur)
# interchange between runner and nxt[k]
nxt_runner = nxt[k]
nxt[k] = runner
if tuple(nxt) not in visited:
visited.add(tuple(nxt))
curSteps = ((k-start) if (k-start)>=0 else (k-start+N)) + N
q.append((tuple(nxt),step+curSteps,nxt_runner,k))
if not isOK:
print('Fails to reach the target states!')
# flog.close()
tCost = time.perf_counter() - tStart
print('N={0}, steps = {1}, tCost = {2:6.3f}(sec)'.format(N,step,tCost))運行結果：
N=6, steps = 48, tCost = 0.113(sec)
N=8, steps = 96, tCost = 21.311(sec)
4. 后記
運行時間太長了，需要進一步考慮優化，
N=8時的答案與原書答案是一致的，但是N=6時與原書給的題解要小（48 vs 51），經過仔細查驗，確信原書給的答案不正確，原書給的移動程序所需要的步驟數的確更短，但是就總的移動距離而言我的更短，，，N=6時的我所得到的移動程序如下所示：
以上N=6的移動程序有興趣的小伙伴可以檢驗，
心中有點小小的激動，找出一個“錯誤”不是一件容易的事情^-^，
上一篇：Q55: 平分蛋糕
下一篇：Q59: 合并單元格的方式
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/333514.html
標籤：其他