1. 問題描述

2. 解題分析

老規矩，先來一個最基本的方案，

由于是找最小需要的投接次數，所以可以看作是一個圖搜索問題的最短路徑問題，

廣度優先搜索，

2.1 狀態標識

12個人對應12個位置，可以表示為一個陣列，

11個球可以標記為0,1,2, ... ,10，空的位置（即當前不持球的人）填入“-1”（可以認為是持有“空球”）（當然其實就用11表示“空球”也可以），

因此初始狀態就是：[0,1,2, ... ,10, -1]，而目標狀態則是[-1,1,2, ... ,10, 0]，

對于每個人（位置），允許向他投擲球的人（位置）是固定的，可以預先建立一張查找表，比如說:

0: (6,7); 1: (6,7,8); ...; 10: (3,4,5); 11: (4,5);

當然允許投擲的前提是當前這個人未持球（空的），

這樣，問題就轉變成從狀態出發[0,1,2, ... ,10, -1]，在規定的投擲動作要求下到達目標狀態[-1,1,2, ... ,10, 0]所需要的最少投擲次數（投擲可以看作是空球”-1”與投擲位置處現有的球的位置交換），

2.2 演算法流程

演算法流程如下：

3. 代碼及測驗

# -*- coding: utf-8 -*-
"""
Created on Thu Oct 28 17:39:51 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      = np.arange(N)
start[-1]  = -1  # Indicated that no ball in hand
target     = np.arange(N)
target[0]  = -1
target[-1] = 0
target     = tuple(target)

throw_dict = dict()
throw_dict[0] = (6,7)
throw_dict[1] = (6,7,8)
throw_dict[2] = (7,8,9)
throw_dict[3] = (8,9,10)
throw_dict[4] = (9,10,11)
throw_dict[5] = (10,11)
throw_dict[6] = (0,1)
throw_dict[7] = (0,1,2)
throw_dict[8] = (1,2,3)
throw_dict[9] = (2,3,4)
throw_dict[10]= (3,4,5)
throw_dict[11]= (4,5)


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

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

tStart  = time.perf_counter()    
dbg_cnt = 0
while len(q) > 0:
    cur,step = q.popleft()    
    dbg_cnt += 1
    # if dbg_cnt%1000 == 0:
        # print('cur={}, step={}'.format(cur,step))
    #     break
    if tuple(cur) == target:
        print('Reach the goal!, dbg_cnt = {}'.format(dbg_cnt))
        break
    
    c = np.array(cur)
    empty = np.where(c==-1)[0][0] # Find where is the empty people
    
    for k in throw_dict[empty]:
        # print('empty ={}, throw_set = {}, k={}, cur={}'.format(empty, throw_dict[empty],k,cur))
        nxt = c.copy()
        nxt[empty] = cur[k]
        nxt[k]     = -1
        if tuple(nxt) not in visited:
            visited.add(tuple(nxt))
            q.append((tuple(nxt),step+1))

tCost  = time.perf_counter() - tStart
print('N={0}, steps = {1}, tCost = {2:6.3f}(sec)'.format(N,step,tCost))

運行結果：

Reach the goal!, dbg_cnt = 14105117
N=12, steps = 37, tCost = 232.754(sec)

4. 后記

一如既往，基本方案非常之慢，

以上代碼中追加了個列印資訊，關于總共探索了多少個狀態節點得資訊，從列印結果來看，總共探索了14105117（一千四百萬）個狀態節點，非常驚人！

有待考慮進一步的優化方案，

上一篇：Q63: 迷宮會合

下一篇：Q65: 圖形的一筆畫

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342031.html

標籤：其他

上一篇：力扣——最后一個單詞的長度