2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q26: 高效的立体停车场

时间:12-28来源:作者:点击数:44

1. 问题描述

最近,一些公寓等建筑也都配备了立体停车场。立体停车场可以充分利用窄小的土地,通过上下左右移动来停车、出库,从而尽可能多地停车。

现在有一个立体停车场,车出库时是把车往没有车的位置移动,从而把某台车移动到出库位置。假设要把左上角的车移动到右下角,试找出路径最短时的操作步数。

举个例子,在 3×2的停车场用如图13所示的方式移动时,需要移动13步。

图1车从左上角移动到右下角的示例1(13步)

不过,如果用如下图所示的移动方法,则只需要移动 9步。

图2车从左上角移动到右下角的示例1(9步)

问题:

求在 10×10的停车场中,把车从左上角移动到右下角时按最短路径移动时需要的最少步数。

2. 解题分析

因为是求最短路径,所以可以用广度优先搜索策略来解决。

广度优先搜索有与深度优先搜索相同的三个基本要素:

  1. 基本算法流程
  2. 状态表示方法
  3. 遍历下一个状态

其中(2)和(3)相关联的,合理的状态表示和遍历方法的选择是解决问题的效率的关键。

2.1 BFS基本流程

2.2 状态表示方法

本题考虑以车和空位的位置坐标表示当前状态(或节点),再加上对应的层数,即[[x1,y1, x2,y2], layer].其中[x1,y1]表示车的位置,[x2,y2]表示空位的位置。

车的其实位置为[0,0], 空位的其实坐标为[N-1,M-1],N和M分别为车库的行数和列数。

当车的位置移动到[N-1,M-1],即算到达目标。

2.3 遍历下一个状态

本问题搜索下一个状态(或者说移动方式)是一件麻烦事。

焦点是空位的移动。因为空位是一定移动的,车则不一定,车只有在与空位相邻的时候才有机会移动。要点如下:

  1. 空位在中心位置的话,有4个方向都可以移动
  2. 空位在边缘的话就会受到限制
  3. 如果车恰好在空位某个方向的相邻位置,则空位往这个方向的移动是交换车和空位的位置

参见findNext()函数。本题解中findNext()函数写得比较冗长,暂时没有想到更简洁的写法。不过这个不是关键点,暂时将就一下。

3. 代码及测试

  • # -*- coding: utf-8 -*-
  • """
  • Created on Mon Sep 13 07:10:26 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
  • class Solution:
  • def parkingMove(self,N,M):
  • '''
  • The content stored in Queue:
  • [[x1,y1,x2,y2], layer]. (x1,y1): car position; (x2,y2): empty position
  • 'visited' is implemented as dict() for faster item search, the value is irrelant, hence set to ''.
  • (x1,y1,x2,y2) is used as the key of 'visited', instead of [x1,y1,x2,y2], because list is unhashable type.
  • Returns
  • -------
  • The number of moves needed to move car to the right-down lot, from top-left lot.
  • '''
  • def findNext(curState):
  • nxtStateLst = []
  • # empty up
  • carPos,emptyPos = curState[0:2], curState[2:]
  • if emptyPos[0] > 0:
  • # print('up')
  • if carPos[0] == emptyPos[0] - 1 and carPos[1] == emptyPos[1]:
  • carPos[0] = carPos[0] + 1
  • emptyPos[0] = emptyPos[0] - 1
  • nxtStateLst.append(carPos+emptyPos)
  • # empty down
  • carPos,emptyPos = curState[0:2], curState[2:]
  • if emptyPos[0] < N-1:
  • # print('down')
  • if carPos[0] == emptyPos[0] + 1 and carPos[1] == emptyPos[1]:
  • carPos[0] = carPos[0] - 1
  • emptyPos[0] = emptyPos[0] + 1
  • nxtStateLst.append(carPos+emptyPos)
  • # empty left
  • carPos,emptyPos = curState[0:2], curState[2:]
  • if emptyPos[1] > 0:
  • # print('left')
  • if carPos[1] == emptyPos[1] - 1 and carPos[0] == emptyPos[0]:
  • carPos[1] = carPos[1] + 1
  • emptyPos[1] = emptyPos[1] - 1
  • nxtStateLst.append(carPos+emptyPos)
  • # empty right
  • carPos,emptyPos = curState[0:2], curState[2:]
  • if emptyPos[1] < M-1:
  • # print('right')
  • if carPos[1] == emptyPos[1] + 1 and carPos[0] == emptyPos[0]:
  • carPos[1] = carPos[1] - 1
  • emptyPos[1] = emptyPos[1] + 1
  • nxtStateLst.append(carPos+emptyPos)
  • # print('findNext: ',curState,' -> ',nxtStateLst)
  • return nxtStateLst
  • # Initialization
  • q = deque()
  • visited = dict()
  • car_start, empty_start = [0,0], [N-1,M-1]
  • car_target = [N-1,M-1]
  • q.append([car_start + empty_start, 0])
  • visited[tuple(car_start + empty_start)] = ''
  • while len(q) != 0:
  • node = q.popleft()
  • # print(node)
  • car_pos = node[0][0:2]
  • layer = node[1]
  • if car_pos == car_target:
  • return layer
  • nxtStateLst = findNext(node[0])
  • for nxtState in nxtStateLst:
  • if tuple(nxtState) not in visited:
  • visited[tuple(nxtState)] = ''
  • q.append([nxtState, layer+1])
  • if __name__ == '__main__':
  • sln = Solution()
  • tStart = time.perf_counter()
  • N,M = 10,10 # N*M parking-lots
  • numOfMoves = sln.parkingMove(N,M)
  • tCost = time.perf_counter() - tStart
  • print('N,M={0},{1}, num-of-moves = {2}, tCost = {3:6.3f}(sec)'.format(N,M,numOfMoves,tCost))

运行结果:

N,M=10,10, num-of-moves = 69, tCost = 0.145(sec)

4. 后记

以上题解中用deque来实现队列,需要注意的一点是,deque是双向队列,其入队离队方法为append(), pop(), appendleft(), popleft(),其中append()与popleft()构成一对,appendleft()与pop()构成一对。如果配错对了就不是队列而变成栈了,那就得不到最短距离解了。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门