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

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

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)

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)

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