目錄
1. 問題描述
2. 解題分析
2.1 Naive Approach--正向全量搜索
2.2 縮小搜索范圍
2.3 以遞回的方式實作
2.4 反向搜索
3. 代碼及測驗
4. 后記
1. 問題描述
2. 解題分析
把每種排序狀態看作是一個節點（共有9!=362880種狀態/節點，本系列中通常把節點和狀態交換使用），把各狀態到達“終點”狀態所需要最少重排次數視為該節點到達“終點”的距離，到此為止，本問題似乎跟Q38是完全相同型別的問題，但是，本問題與Q38相比有一個根本性的差異：不存在一個統一的終點，Q38中的統一的終點是“全白”狀態，而本問題中，從任意狀態出發，它對應的“終點”狀態是以1開始的排列，總共有8！=40320中可能的“終點”狀態！所以不能單純地像Q38那樣采樣逆向思考來解決問題，
2.1 Naive Approach--正向全量搜索
作為Na?ve approach，遍歷從每個狀態出發，然后搜索它們到某個“終點”狀態的距離（即所需重排次數），然后再進行比較，演算法流程如下：
2.2 縮小搜索范圍
根據題設的重新排列規則，任何一個排列狀態，只要它滿足以下條件：它的第k個數恰好為k，則它肯定可以由將前k個數逆序排列得到的狀態按照題設規則重新排列而得，因此它肯定距離最遠的狀態，比如說，[1,3,4,6,5,2,7,8,9]的第5個數恰好是5，它可以由[5,6,4,3,1,2,7,8,9]根據題設規則重排而得，滿足這樣條件的排列就可以從搜索串列中排除出去，可以節省一定的搜索時間，演算法流程如下：
2.3 以遞回的方式實作
從任意狀態開始的搜索程序也可以用遞回的方式實作，遞回函式的實作流程如下：
2.4 反向搜索
雖然，前面說了不能像Q38那樣單純從單一狀態逆向搜索來求解，但是，畢竟可能的終點狀態數只是8!，是所有可能狀態數9！的1/9，所以從每一個可能的終點狀態進行逆向搜索還是大大縮小了搜索范圍（？），不過事情并沒有這么簡單，正向搜索的話，雖然起點比較多，但是從起點到終點是單一路徑（即每個狀態向下一個狀態轉移是唯一的）；而反向搜索的話，則從一個狀態可能到達多個狀態（對應于正向搜索中，可能從多個狀態出發到達同一個狀態，比如說[2,1,3]和[3,2,1]根據題規則都是到達[1,2,3]），所以反向搜索的起點數雖然少，但是從的搜索復雜度不一定比正向搜索低，定量的分析很難（超出了本渣的能力范圍），所以是騾子是馬拉出來遛一遛，不妨寫出代碼來比一比，流程如下所示：
3. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 25 09:05:40 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
# import random
from typing import List
# from queue import Queue
from collections import deque
import itertools as it
import numpy as np
def reordering1(N:int):
maxstep = 0
for start in it.permutations(range(1,N+1)):
# print(start)
ordering = list(start)
step = 0
while ordering[0] != 1:
k = ordering[0]
# print(k)
tmp = ordering[0:k]
tmp.reverse()
ordering = tmp + ordering[k:]
step = step + 1
if maxstep < step:
maxstep = step
maxstart = start
return maxstep, maxstart
def reordering2(N:int):
maxstep = 0
for start in it.permutations(range(1,N+1)):
skip = False
for i in range(N):
if start[i] == i+1:
skip = True
if skip:
# Skip and go to the next.
continue
ordering = list(start)
step = 0
while ordering[0] != 1:
k = ordering[0]
# print(k)
tmp = ordering[0:k]
tmp.reverse()
ordering = tmp + ordering[k:]
step = step + 1
if maxstep < step:
maxstep = step
maxstart = start
return maxstep, maxstart
def reordering3(N: int):
global maxstep
global maxstart
maxstep = 0
maxstart= None
def recur(cur, start, step):
# print(cur)
global maxstep
global maxstart
if cur[0] == 1:
if maxstep < step:
maxstep = step
maxstart = start
# print(cur, maxstep, maxstart)
return
k = cur[0]
tmp = cur[0:k]
tmp.reverse()
nxt = tmp + cur[k:]
recur(nxt, start, step+1)
for start in it.permutations(range(1,N+1)):
skip = False
for i in range(N):
if start[i] == i+1:
skip = True
if skip:
# Skip and go to the next.
continue
start = list(start)
recur(start, start, 0)
return maxstep, maxstart
def reordering4(N: int):
maxstep = 0
maxstart= None
for start in it.permutations(range(1,N+1)):
if start[0] != 1:
# Skip and go to the next.
continue
# For each one of them, perform BFS to find the max distance.
visited = set()
q = deque()
q.append((start,0))
visited.add(start)
while len(q) > 0:
cur, step = q.popleft()
# print(cur,step)
for k in range(1,N):
# Search for the next state
if cur[k] == k+1:
tmp = list(cur[0:k+1])
tmp.reverse()
nxt = tuple(tmp + list(cur[k+1:]))
if nxt not in visited and nxt[0]!=1:
visited.add(nxt)
q.append((nxt,step+1))
if maxstep < step:
maxstep = step
# maxstart = start
maxstart = cur # In reverse search, the final state corresponds to the start in forward search
return maxstep, maxstartif __name__ == '__main__':
N = 9
tStart = time.perf_counter()
maxstep,maxstart = reordering1(N)
tCost = time.perf_counter() - tStart
print('N={0}, maxstep = {1}, maxstart = {2}, tCost = {3:6.3f}(sec)'.format(N,maxstep,maxstart,tCost))
tStart = time.perf_counter()
maxstep,maxstart = reordering2(N)
tCost = time.perf_counter() - tStart
print('N={0}, maxstep = {1}, maxstart = {2}, tCost = {3:6.3f}(sec)'.format(N,maxstep,maxstart,tCost))
tStart = time.perf_counter()
maxstep,maxstart = reordering3(N)
tCost = time.perf_counter() - tStart
print('N={0}, maxstep = {1}, maxstart = {2}, tCost = {3:6.3f}(sec)'.format(N,maxstep,maxstart,tCost))
tStart = time.perf_counter()
maxstep,maxstart = reordering4(N)
tCost = time.perf_counter() - tStart
print('N={0}, maxstep = {1}, maxstart = {2}, tCost = {3:6.3f}(sec)'.format(N,maxstep,maxstart,tCost)) 運行結果：
4. 后記
4種實作方式的運行時間居然沒有什么顯著的差異，
不過，寫多種解法本身也是一種很有益的聯系，
當然，這個問題是不是還有更高效的解決方案是一個開放的問題，還有待進一步琢磨，
上一篇：Q38: 填充白色
下一篇：Q40: 優雅的IP地址
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302988.html
標籤：其他