用Python展示动态规则法用以解决重叠子问题的示例

动态规划是一种用来解决定义了一个状态空间的问题的算法策略。这些问题可分解为新的子问题,子问题有自己的参数。为了解决它们,我们必须搜索这个状态空间并且在每一步作决策时进行求值。得益于这类问题会有大量相同的状态的这个事实,这种技术不会在解决重叠的子问题上浪费时间。

正如我们看到的,它也会导致大量地使用递归,这通常会很有趣。

为了说明这种算法策略,我会用一个很好玩的问题来作为例子,这个问题是我最近参加的 一个编程竞赛中的 Tuenti Challenge #4 中的第 14 个挑战问题。
Train Empire

我们面对的是一个叫 Train Empire 的棋盘游戏(Board Game)。在这个问题中,你必须为火车规划出一条最高效的路线来运输在每个火车站的货车。规则很简单:

  • 每个车站都有一个在等待着的将要运送到其他的车站的货车。
  • 每个货车被送到了目的地会奖励玩家一些分数。货车可以放在任意车站。
  • 火车只在一条单一的路线上运行,每次能装一个货车,因为燃料有限只能移动一定的距离。

我们可以把我们的问题原先的图美化一下。为了在燃料限制下赢得最大的分数,我们需要知道货车在哪里装载,以及在哪里卸载。

我们在图片中可以看到,我们有两条火车路线:红色和蓝色。车站位于某些坐标点上,所以我们很容易就能算出它们之间的距离。每一个车站有一个以它的终点命名的货车,以及当我们成功送达它可以得到的分数奖励。

现在,假定我们的货车能跑3千米远。红色路线上的火车可以把 A 车站的火车送到它的 终点 E (5点分数),蓝色路线上的火车可以运送货车 C(10点分数),然后运送货车 B(5点分数)。 可以取得最高分20分。
状态表示

我们把火车的位置,以及火车所走的距离和每个车站的货车表格叫做一个问题状态。 改变这些值我们得到的仍是相同的问题,但是参数变了。我们可以看到每次我们移动 一列火车,我们的问题就演变到一个不同的子问题。为了算出最佳的移动方案,我们 必须遍历这些状态然后基于这些状态作出决策。让我们开始把。

我们将从定义火车路线开始。因为这些路线不是直线,所以图是最好的表示方法。

import math
from decimal import Decimal
from collections import namedtuple, defaultdict

class TrainRoute:

  def __init__(self, start, connections):
    self.start = start

    self.E = defaultdict(set)
    self.stations = set()
    for u, v in connections:
      self.E[u].add(v)
      self.E[v].add(u)
      self.stations.add(u)
      self.stations.add(v)

  def next_stations(self, u):
    if u not in self.E:
      return
    yield from self.E[u]

  def fuel(self, u, v):
    x = abs(u.pos[0] - v.pos[0])
    y = abs(u.pos[1] - v.pos[1])
    return Decimal(math.sqrt(x * x + y * y))

TrainRoute 类实现了一个非常基本的有向图,它把顶点作为车站存在一个集合中,把车站间 的连接存在一个字典中。请注意我们把 (u, v) 和 (v, u) 两条边都加上了,因为火车可以 向前向后移动。

在 next_stations 方法中有一个有趣东西,在这里我使用了一个很酷的 Python 3 的特性yield from。这允许一个生成器 可以委派到另外一个生成器或者迭代器中。因为每一个车站都映射到一个车站的集合,我们只 需要迭代它就可以了。

让我们来看一下 main class:

TrainWagon = namedtuple('TrainWagon', ('dest', 'value'))
TrainStation = namedtuple('TrainStation', ('name', 'pos', 'wagons'))

class TrainEmpire:

  def __init__(self, fuel, stations, routes):
    self.fuel = fuel
    self.stations = self._build_stations(stations)
    self.routes = self._build_routes(routes)

  def _build_stations(self, station_lines):
    # ...

  def _build_routes(self, route_lines):
    # ...

  def maximum_route_score(self, route):

    def score(state):
      return sum(w.value for (w, s) in state.wgs if w.dest == s.name)

    def wagon_choices(state, t):
      # ...

    def delivered(state):
      # ...

    def next_states(state):
      # ...

    def backtrack(state):
      # ...

    # ...

  def maximum_score(self):
    return sum(self.maximum_route_score(r) for r in self.routes)

我省略了一些代码,但是我们可以看到一些有趣的东西。两个 命名元组 将会帮助保持我们的数据整齐而简单。main class 有我们的火车能够运行的最长的距离,燃料, 和路线以及车站这些参数。maximum_score 方法计算每条路线的分数的总和,将成为解决问题的 接口,所以我们有:

  • 一个 main class 持有路线和车站之间的连接
  • 一个车站元组,存有名字,位置和当前存在的货车列表
  • 一个带有一个值和目的车站的货车

动态规划

我已经尝试解释了动态规划如何高效地搜索状态空间的关键,以及基于已有的状态进行最优的决策。 我们有一个定义了火车的位置,火车剩余的燃料,以及每个货车的位置的状态空间——所以我们已经可以表示初始状态。

我们现在必须考虑在每个车站的每一种决策。我们应该装载一个货车然后把它送到目的地吗? 如果我们在下一个车站发现了一个更有价值的货车怎么办?我们应该把它送回去或者还是往前 移动?或者还是不带着货车移动?

很显然,这些问题的答案是那个可以使我们获得更多的分数的那个。为了得到答案,我们必须求出 所有可能的情形下的前一个状态和后一个状态的值。当然我们用求分函数 score 来求每个状态的值。

def maximum_score(self):
  return sum(self.maximum_route_score(r) for r in self.routes)

State = namedtuple('State', ('s', 'f', 'wgs'))

wgs = set()
for s in route.stations:
  for w in s.wagons:
    wgs.add((w, s))
initial = State(route.start, self.fuel, tuple(wgs))

从每个状态出发都有几个选择:要么带着货车移动到下一个车站,要么不带货车移动。停留不动不会进入一个新的 状态,因为什么东西都没改变。如果当前的车站有多个货车,移动它们中的一个都将会进入一个不同的状态。

def wagon_choices(state, t):
  yield state.wgs # not moving wagons is an option too

  wgs = set(state.wgs)
  other_wagons = {(w, s) for (w, s) in wgs if s != state.s}
  state_wagons = wgs - other_wagons
  for (w, s) in state_wagons:
    parked = state_wagons - {(w, s)}
    twgs = other_wagons | parked | {(w, t)}
    yield tuple(twgs)

def delivered(state):
  return all(w.dest == s.name for (w, s) in state.wgs)

def next_states(state):
  if delivered(state):
    return
  for s in route.next_stations(state.s):
    f = state.f - route.fuel(state.s, s)
    if f < 0:
      continue
    for wgs in wagon_choices(state, s):
      yield State(s, f, wgs)

next_states 是一个以一个状态为参数然后返回所有这个状态能到达的状态的生成器。 注意它是如何在所有的货车都移动到了目的地后停止的,或者它只进入到那些燃料仍然足够的状态。wagon_choices 函数可能看起来有点复杂,其实它仅仅返回那些可以从当前车站到下一个车站的货车集合。

这样我们就有了实现动态规划算法需要的所有东西。我们从初始状态开始搜索我们的决策,然后选择 一个最有策略。看!初始状态将会演变到一个不同的状态,这个状态也会演变到一个不同的状态! 我们正在设计的是一个递归算法:

  • 获取状态
  • 计算我们的决策
  • 做出最优决策

显然每个下一个状态都将做这一系列的同样的事情。我们的递归函数将会在燃料用尽或者所有的货车都被运送都目的地了时停止。

max_score = {}

def backtrack(state):
  if state.f <= 0:
    return state
  choices = []
  for s in next_states(state):
    if s not in max_score:
      max_score[s] = backtrack(s)
    choices.append(max_score[s])
  if not choices:
    return state
  return max(choices, key=lambda s: score(s))

max_score[initial] = backtrack(initial)
return score(max_score[initial])

完成动态规划策略的最后一个陷阱:在代码中,你可以看到我使用了一个 max_score 字典, 它实际上缓存着算法经历的每一个状态。这样我们就不会重复一遍又一遍地遍历我们的我们早就已经 经历过的状态的决策。

当我们搜索状态空间的时候,一个车站可能会到达多次,这其中的一些可能会导致相同的燃料,相同的货车。 火车怎么到达这里的没关系,只有在那个时候做的决策有影响。如果我们我们计算过那个状态一次并且保存了 结果,我们就不在需要再搜索一遍这个子空间了。

如果我们没有用这种记忆化技术,我们会做大量完全相同的搜索。 这通常会导致我们的算法很难高效地解决我们的问题。
总结

Train Empire 提供了一个绝佳的的例子,以展示动态规划是如何在有重叠子问题的问题做出最优决策。 Python 强大的表达能力再一次让我们很简单地就能把想法实现,并且写出清晰且高效的算法。

完整的代码在 contest repository。

(0)

相关推荐

  • 数据挖掘之Apriori算法详解和Python实现代码分享

    关联规则挖掘(Association rule mining)是数据挖掘中最活跃的研究方法之一,可以用来发现事情之间的联系,最早是为了发现超市交易数据库中不同的商品之间的关系.(啤酒与尿布) 基本概念 1.支持度的定义:support(X-->Y) = |X交Y|/N=集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数.例如:support({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数/数据记录数 = 3/5=60%. 2.自信度的定义:confidence(X-->

  • 朴素贝叶斯算法的python实现方法

    本文实例讲述了朴素贝叶斯算法的python实现方法.分享给大家供大家参考.具体实现方法如下: 朴素贝叶斯算法优缺点 优点:在数据较少的情况下依然有效,可以处理多类别问题 缺点:对输入数据的准备方式敏感 适用数据类型:标称型数据 算法思想: 比如我们想判断一个邮件是不是垃圾邮件,那么我们知道的是这个邮件中的词的分布,那么我们还要知道:垃圾邮件中某些词的出现是多少,就可以利用贝叶斯定理得到. 朴素贝叶斯分类器中的一个假设是:每个特征同等重要 函数 loadDataSet() 创建数据集,这里的数据集

  • python k-近邻算法实例分享

    简单说明 这个算法主要工作是测量不同特征值之间的距离,有个这个距离,就可以进行分类了. 简称kNN. 已知:训练集,以及每个训练集的标签. 接下来:和训练集中的数据对比,计算最相似的k个距离.选择相似数据中最多的那个分类.作为新数据的分类. python实例 复制代码 代码如下: # -*- coding: cp936 -*- #win系统中应用cp936编码,linux中最好还是utf-8比较好.from numpy import *#引入科学计算包import operator #经典pyt

  • 用Python展示动态规则法用以解决重叠子问题的示例

    动态规划是一种用来解决定义了一个状态空间的问题的算法策略.这些问题可分解为新的子问题,子问题有自己的参数.为了解决它们,我们必须搜索这个状态空间并且在每一步作决策时进行求值.得益于这类问题会有大量相同的状态的这个事实,这种技术不会在解决重叠的子问题上浪费时间. 正如我们看到的,它也会导致大量地使用递归,这通常会很有趣. 为了说明这种算法策略,我会用一个很好玩的问题来作为例子,这个问题是我最近参加的 一个编程竞赛中的 Tuenti Challenge #4 中的第 14 个挑战问题. Train

  • Python实现动态添加类的属性或成员函数的解决方法

    某些时候我们需要让类动态的添加属性或方法,比如我们在做插件时就可以采用这种方法.用一个配置文件指定需要加载的模块,可以根据业务扩展任意加入需要的模块. 本文就此简述了Python实现动态添加类的属性或成员函数的解决方法,具体方法如下: 首先我们可以参考ulipad的实现:mixin. 这里做的比较简单,只是声明一个类,类初始化的时候读取配置文件,根据配置列表加载特定目录下的模块下的函数,函数和模块同名,将此函数动态加载为类的成员函数. 代码如下所示: class WinBAS(Bas): def

  • Python中动态创建类实例的方法

    简介 在Java中我们可以通过反射来根据类名创建类实例,那么在Python我们怎么实现类似功能呢? 其实在Python有一个builtin函数import,我们可以使用这个函数来在运行时动态加载一些模块.如下: def createInstance(module_name, class_name, *args, **kwargs): module_meta = __import__(module_name, globals(), locals(), [class_name]) class_met

  • Android实现登陆页logo随键盘收放动态伸缩(完美解决键盘弹出遮挡控件的问题)

    在最近的两个项目中,项目需求要求我们实现 /*登陆页面的内容能够随着键盘的弹出而被顶上去,避免键盘遮挡住登陆按钮*/ 这样的效果,宝宝心里苦呀,本来半天搞定的事还非得折腾一下,好吧我妥协,毕竟我还是一只非常注重用户体验的猿. 那就做吧,初步定下的方案是输入框和登陆按钮大小不变,在键盘弹出的时候让logo的大小和位置进行改变,从而给键盘腾出位置,当然在键盘收起的时候还要给它还原一下,就像什么都没发生一样,嗯对,就是这样,说了这么多,放张图先感受一下效果吧: 接下来上正餐,布局上比较简单,注意给图片

  • Python SqlAlchemy动态添加数据表字段实例解析

    本文研究的主要是Python SqlAlchemy动态添加数据表字段,具体如下. 我们知道使用SqlAlchemy创建类来映射数据表,类属性等于数据库字段,但有时候要在我们创建表的时候,不确定数据表字段数量,遇到这种情况,应如何解决? 先看常规用法 from sqlalchemy import create_engine,Column,String,Integer class Mybase(Base): #表名 __tablename__ ='mycars' #字段,属性 myid=Column

  • 用python生成(动态彩色)二维码的方法(使用myqr库实现)

    最近真的感觉到了python生态的强大(倒吸一口凉气) 现在介绍一个可以生成动态二维码的库(myqr) 效果如图: 第一步要安装myqr库 在cmd中直接用pip安装 pip install myqr 第二步 from MyQR import myqr import os version, level, qr_name = myqr.run( words="https://www.baidu.com", # 可以是字符串,也可以是网址(前面要加http(s)://) version=1

  • python实现动态创建类的方法分析

    本文实例讲述了python实现动态创建类的方法.分享给大家供大家参考,具体如下: python作为动态语言,如何在运行时动态创建类呢(python Creating classes dynamically),这在编程时,有时候很有用处,动态生成类,给予相应的属性和方法.通常来说有如下两种方式: 1. 根据条件,硬编码实现. 2. 利用 type metaclass  来实现. 根据条件硬编码 def choose_class(name): if name == 'foo': class Foo(

  • 详解python实现交叉验证法与留出法

    在机器学习中,我们经常在训练集上训练模型,在测试集上测试模型.最终的目标是希望我们的模型在测试集上有最好的表现. 但是,我们往往只有一个包含m个观测的数据集D,我们既要用它进行训练,又要对它进行测试.此时,我们就需要对数据集D进行划分. 对于数据集D的划分,我们尽量需要满足三个要求: 训练集样本量充足 训练模型时的计算量可以忍受 不同的划分方式会得出不同的训练集和测试集,从而得出不同的结果,我们需要消除这种影响 我们将分别介绍留出法.交叉验证法,以及各自的python实现.自助法(bootstr

  • python的命名规则知识点总结

    python命名规则 命名风格 python几种不同命名风格 驼峰式命名法(WjW) 混合式命名法(wjWj) 大写(WJWJWJ)或大写加下划线(WJWJWJ) 前缀(wjing)或后缀(ingwj)下划线,有时双下划线 变量 python变量分为: (1)常量 (2)公有和私有变量 1.常量 常量全局变量,使用大写加下划线.指定的变量表示一个常数值. BASE_DIR = os.path.dirname(os.path.dirname(os.path.abspath(file))) 2.命名

  • Python龙贝格法求积分实例

    我就废话不多说了,直接上代码吧! # 龙贝格法求积分 import math a=0 # 积分下限 b=1 # 积分上限 eps=10**-5 # 精度 T=[] # 复化梯形序列 S=[] # Simpson序列 C=[] # Cotes序列 R=[] # Romberg序列 def func(x): # 被积函数 y=math.exp(-x) return y def Romberg(a,b,eps,func): h = b - a T.append(h * (func(a) + func(

随机推荐