程序员的算法趣题Q64: 麻烦的投接球

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（一千四百万）个状态节点，非常惊人！

有待考虑进一步的优化方案。