摘要:目录前言前言递推关系递推关系代码及测试代码及测试后记后记前言参见程序员的算法趣题偷懒的算盘上一篇中给出的初始方案是暴力破解或者说全量搜索的方式,总共需要搜索种情况,因此非常耗时。
目录
上一篇中给出的初始方案是暴力破解(或者说全量搜索)的方式,总共需要搜索10!=3628800种情况,因此非常耗时。
本篇给出基于动态规划思想的题解。
由于10个数每个只用计算一次,考虑已经执行了若干个数的运算(它们构成visited集合),此时算盘上的计算结果为curSum,完成之后剩余的运算所需要的最少算珠移动数与之前若干个数的运算顺序(以及相应的算珠移动数)是无关的,仅与curSum有关。由此可以得到本问题的子问题分解结构,如下所述。
令f(unvisited)表示(在当前已经求得的和—即visited中的数的和—的基础上)执行剩余的unvisited的数的运算所需要的最少算珠移动数。注意,unvisited与visited是互补的,或者说一一对应的。则有以下递推关系成立:
其中,unvisited表示一个集合,“unvisited-k”则表示从unvisited中删除一个元素k的操作。
基于以上递推关系,可以以正向的标准的动态规划的方式实现,也可以以递归加Memoization的方式实现,鉴于后者代码显得更加简洁,以下代码采用后者。
因为10个数每个只能用一次,所以实际上visited或者unvisited(以下代码中是用visited)可以用10比特的二进制数来表示。
# -*- coding: utf-8 -*-"""Created on Tue Oct 12 07:43:10 2021@author: chenxy"""# import sysimport time# import datetime# import math# import random# from typing import List# from queue import Queue# from collections import dequeimport itertools as itimport numpy as npdef move(x: int, y: int)->int: """ 当前算盘上值为cursm时,再加上y需要移动算珠的个数 Parameters ---------- x : int The current number in abacus. y : int The number to be added. Returns ------- int The number of abacus-stone being moved in the above operation. """ # The representation of x a1 = 1 if x>=50 else 0 a2 = (x%50) // 10 a3 = 1 if (x%10)>=5 else 0 a4 = x%5 # The representation of x+y z = x + y b1 = 1 if z>=50 else 0 b2 = (z%50) // 10 b3 = 1 if (z%10)>=5 else 0 b4 = z%5 return z, abs(a1-b1)+abs(a2-b2)+abs(a3-b3)+abs(a4-b4)#3. Recursion + Memoizationmemo = dict()minMoves = 100def search1(bit10, moves)->int: """ Parameters ---------- bit10 : int 10 bits to represent whether each one of [1,2,...,10] is used. bit[0]:1; bit[1]:2; ...; bit[9]:10; moves : number of moves up to now. Returns ------- The minimum number of moves needed for the current condition. """ # print(bit10,moves) global minMoves if bit10 == 0b11_1111_1111: if minMoves > moves: minMoves = moves return if (bit10, moves) in memo: # Already visited, no need to continue. return cur_sum = 0 for k in range(10): if bit10>>k & 0x1 == 1: cur_sum = cur_sum + (k+1) for k in range(10): if bit10>>k & 0x1 == 0: _,cur_move = move(cur_sum, k+1) search1(bit10|(0x1<int: """ Parameters ---------- bit10 : int 10 bits to represent whether each one of [1,2,...,10] is used. bit[0]:1; bit[1]:2; ...; bit[9]:10; Returns ------- The minimum number of moves needed for the current condition. """ # print(bit10) if bit10 == 0b11_1111_1111: return 0 if bit10 in memo: # Already visited, no need to continue. return memo[bit10] cur_sum = 0 for k in range(10): if bit10>>k & 0x1 == 1: cur_sum = cur_sum + (k+1) minMoves = 100 for k in range(10): if bit10>>k & 0x1 == 0: _,cur_move = move(cur_sum, k+1) moves = search2(bit10|(0x1< (moves + cur_move): minMoves = (moves + cur_move) memo[bit10] = minMoves return minMoves tStart = time.perf_counter()minMoves = search2(0)tCost = time.perf_counter() - tStartprint("moves={0}, tCost = {1:6.3f}(sec)".format(minMoves,tCost))
运行结果:
moves=26, tCost = 0.028(sec)
moves=26, tCost = 0.007(sec)
以上包含两种同为“Recursion+Memoization”策略的实现方式,后一种又比前一种还要再快4倍。相比原始的暴力破解方案则快了三个数量级。
search1()与search2()为什么会有4倍的速度差异呢?
search1()将到目前visited为止的算珠移动次数通过函数接口传递,然后在到达目标(即所有数都运算完的状态)进行最小算珠移动次数判断,并且以{visited, moves}作为状态表示用于memo记忆。而Search2()则只计算从visited往后的最小算珠移动次数,因此只需要基于visited进行memo记忆。
很显然,search1()所需要考虑的{visited, moves}所表示的状态数会远远大于search2()的仅由visited所表示的状态数。或许这就是两者运算速度相差4倍的原因吧。
本系列总目录参见:程序员的算法趣题:详细分析和Python全解
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/122546.html
摘要:且听下回分解基于动态规划策略的优化解法参见程序员的算法趣题偷懒的算盘上一篇程序员的算法趣题同数包夹程序员的算法趣题同数包夹本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
摘要:假设有几个小朋友以相同间隔围成圆周,要结对用纸杯电话相互通话。如果绳子交叉,很有可能会缠绕起来,所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问...
摘要:可以在遍历所有矩阵时,对各种出现的次数进行计数,最后计数值为的个数即为所求结果。上一篇排序交换次数的最少化排序交换次数的最少化本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
摘要:本文先考虑深度优先搜索。深度优先搜索算法流程如下最后,将初始化为,初始化,和分别初始化为适当的全零数组,然后调用到最终退出后所得到的即为所求结果。 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 2. 解题分析 本题是要找最长路径,应该...
阅读 1080·2021-10-14 09:43
阅读 1105·2021-10-11 11:07
阅读 3095·2021-08-18 10:23
阅读 1456·2019-08-29 16:18
阅读 982·2019-08-28 18:21
阅读 1451·2019-08-26 12:12
阅读 3724·2019-08-26 10:11
阅读 2480·2019-08-23 18:04