動態(tài)規(guī)劃是一種用來解決定義了一個狀態(tài)空間的問題的算法策略。這些問題可分解為新的子問題，子問題有自己的參數(shù)。為了解決它們，我們必須搜索這個狀態(tài)空間并且在每一步作決策時進行求值。得益于這類問題會有大量相同的狀態(tài)的這個事實，這種技術(shù)不會在解決重疊的子問題上浪費時間。

正如我們看到的，它也會導(dǎo)致大量地使用遞歸，這通常會很有趣。

為了說明這種算法策略，我會用一個很好玩的問題來作為例子，這個問題是我最近參加的 一個編程競賽中的 Tuenti Challenge #4 中的第 14 個挑戰(zhàn)問題。
Train Empire

我們面對的是一個叫 Train Empire 的棋盤游戲（Board Game）。在這個問題中，你必須為火車規(guī)劃出一條最高效的路線來運輸在每個火車站的貨車。規(guī)則很簡單：

•     每個車站都有一個在等待著的將要運送到其他的車站的貨車。
•     每個貨車被送到了目的地會獎勵玩家一些分數(shù)。貨車可以放在任意車站。
•     火車只在一條單一的路線上運行，每次能裝一個貨車，因為燃料有限只能移動一定的距離。

我們可以把我們的問題原先的圖美化一下。為了在燃料限制下贏得最大的分數(shù)，我們需要知道貨車在哪里裝載，以及在哪里卸載。

我們在圖片中可以看到，我們有兩條火車路線：紅色和藍色。車站位于某些坐標(biāo)點上，所以我們很容易就能算出它們之間的距離。每一個車站有一個以它的終點命名的貨車，以及當(dāng)我們成功送達它可以得到的分數(shù)獎勵。

現(xiàn)在，假定我們的貨車能跑3千米遠。紅色路線上的火車可以把 A 車站的火車送到它的 終點 E (5點分數(shù))，藍色路線上的火車可以運送貨車 C(10點分數(shù))，然后運送貨車 B(5點分數(shù))。 可以取得最高分20分。
狀態(tài)表示

我們把火車的位置，以及火車所走的距離和每個車站的貨車表格叫做一個問題狀態(tài)。 改變這些值我們得到的仍是相同的問題，但是參數(shù)變了。我們可以看到每次我們移動 一列火車，我們的問題就演變到一個不同的子問題。為了算出最佳的移動方案，我們 必須遍歷這些狀態(tài)然后基于這些狀態(tài)作出決策。讓我們開始把。

我們將從定義火車路線開始。因為這些路線不是直線，所以圖是最好的表示方法。

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 類實現(xiàn)了一個非常基本的有向圖，它把頂點作為車站存在一個集合中，把車站間 的連接存在一個字典中。請注意我們把 (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)

我省略了一些代碼，但是我們可以看到一些有趣的東西。兩個 命名元組 將會幫助保持我們的數(shù)據(jù)整齊而簡單。main class 有我們的火車能夠運行的最長的距離，燃料， 和路線以及車站這些參數(shù)。maximum_score 方法計算每條路線的分數(shù)的總和，將成為解決問題的 接口，所以我們有：

•     一個 main class 持有路線和車站之間的連接
•     一個車站元組，存有名字，位置和當(dāng)前存在的貨車列表
•     一個帶有一個值和目的車站的貨車

動態(tài)規(guī)劃

我已經(jīng)嘗試解釋了動態(tài)規(guī)劃如何高效地搜索狀態(tài)空間的關(guān)鍵，以及基于已有的狀態(tài)進行最優(yōu)的決策。 我們有一個定義了火車的位置，火車剩余的燃料，以及每個貨車的位置的狀態(tài)空間——所以我們已經(jīng)可以表示初始狀態(tài)。

我們現(xiàn)在必須考慮在每個車站的每一種決策。我們應(yīng)該裝載一個貨車然后把它送到目的地嗎？ 如果我們在下一個車站發(fā)現(xiàn)了一個更有價值的貨車怎么辦？我們應(yīng)該把它送回去或者還是往前 移動？或者還是不帶著貨車移動？

很顯然，這些問題的答案是那個可以使我們獲得更多的分數(shù)的那個。為了得到答案，我們必須求出 所有可能的情形下的前一個狀態(tài)和后一個狀態(tài)的值。當(dāng)然我們用求分函數(shù) score 來求每個狀態(tài)的值。
 

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))

從每個狀態(tài)出發(fā)都有幾個選擇：要么帶著貨車移動到下一個車站，要么不帶貨車移動。停留不動不會進入一個新的 狀態(tài)，因為什么東西都沒改變。如果當(dāng)前的車站有多個貨車，移動它們中的一個都將會進入一個不同的狀態(tài)。

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 是一個以一個狀態(tài)為參數(shù)然后返回所有這個狀態(tài)能到達的狀態(tài)的生成器。 注意它是如何在所有的貨車都移動到了目的地后停止的，或者它只進入到那些燃料仍然足夠的狀態(tài)。wagon_choices 函數(shù)可能看起來有點復(fù)雜，其實它僅僅返回那些可以從當(dāng)前車站到下一個車站的貨車集合。

這樣我們就有了實現(xiàn)動態(tài)規(guī)劃算法需要的所有東西。我們從初始狀態(tài)開始搜索我們的決策，然后選擇 一個最有策略?？?！初始狀態(tài)將會演變到一個不同的狀態(tài)，這個狀態(tài)也會演變到一個不同的狀態(tài)！ 我們正在設(shè)計的是一個遞歸算法：

•     獲取狀態(tài)
•     計算我們的決策
•     做出最優(yōu)決策

顯然每個下一個狀態(tài)都將做這一系列的同樣的事情。我們的遞歸函數(shù)將會在燃料用盡或者所有的貨車都被運送都目的地了時停止。
 

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])

完成動態(tài)規(guī)劃策略的最后一個陷阱：在代碼中，你可以看到我使用了一個 max_score 字典， 它實際上緩存著算法經(jīng)歷的每一個狀態(tài)。這樣我們就不會重復(fù)一遍又一遍地遍歷我們的我們早就已經(jīng) 經(jīng)歷過的狀態(tài)的決策。

當(dāng)我們搜索狀態(tài)空間的時候，一個車站可能會到達多次，這其中的一些可能會導(dǎo)致相同的燃料，相同的貨車。 火車怎么到達這里的沒關(guān)系，只有在那個時候做的決策有影響。如果我們我們計算過那個狀態(tài)一次并且保存了 結(jié)果，我們就不在需要再搜索一遍這個子空間了。

如果我們沒有用這種記憶化技術(shù)，我們會做大量完全相同的搜索。 這通常會導(dǎo)致我們的算法很難高效地解決我們的問題。
總結(jié)

Train Empire 提供了一個絕佳的的例子，以展示動態(tài)規(guī)劃是如何在有重疊子問題的問題做出最優(yōu)決策。 Python 強大的表達能力再一次讓我們很簡單地就能把想法實現(xiàn)，并且寫出清晰且高效的算法。

完整的代碼在 contest repository。

最新評論