Dynamic programming is used to solve the problem of overlapping sample (Python version)

By Dan Brown,2015-05-19 07:58
17 views 0
Dynamic programming is used to solve the problem of overlapping sample (Python version)

    Dynamic programming is used to solve the problem

    of overlapping sample (Python version)

    [editor's note] : Dynamic programming (Dynamic programming) is used in mathematics, computer science and economics, through the original problem is decomposed into relatively simple way of subproblems to solve complex problems.Dynamic programming is often applied to overlap the son and the structural properties of sub problems, dynamic programming method is time consuming is often far less than simple solutions.

    The basic idea is very simple behind dynamic programming.Generally, if want to solve a given problem, we need to solve the different parts (subproblems), then merge the subproblems in a solution of original problem.Often many problems are very similar, dynamic programming for trying to solve the problem of each child only once, so as to reduce the amount of calculation: once a solution has been worked out for the stator problems, it is memory storage, so that next time we need to the same solution when the look-up table directly.This kind of practice in the number of repeat subproblems about the size of the input is especially useful when exponentially.--wikipedia

    Dynamic programming is a kind of used to solve the problem of defining a state space algorithm strategy.These problems can be decomposed into new sub-problem, subproblems have their own parameters.In order to solve them, we must search the state space and make decisions at each step is evaluated.Thanks to this kind of problem will have a lot of the same state the fact that this technology is not to deal with the problem of overlapping sub is a waste of time.

    As we see, it can also lead to a lot of use of recursion, which usually would be fun.

    To illustrate this algorithm strategy, I will use a very fun, as an example, the problem of the problem is that I attend a recentlyprogramming14 a Challenge in the race of Tuenti Challenge # 4.

    Train Empire

    Are we facing a called "Train" Empire of Board games (Board Game).In this problem, you have to train planning out the most efficient route to transport trucks at each station.The rules are simple:

    ; Each station has a waiting for will be delivered to the other station


    ; Each truck was sent to the destination will reward players some

    points.Trucks can be placed in any station.

    ; Trains run on a single route, only can hold one truck at a time,

    because the fuel was limited only moving distance.

    We can put our problem of the original figure to ornament.In order to win the largest fraction under fuel limit, we need to know the truck loading, and where is the unloading.

    We can see in the picture, we have two train route: red and blue.Station located at some coordinate point, so we can easily calculate the distance between them.Each station has a truck, named after the end of it, and when we successfully delivered it can get scores.

    Now, assume that our truck can run 3 km away.Red lines on the train to A station on the train to its destination E (5 points), the blue line on the train can transport truck C (10 points), and then transport truck B (5 points).Can be obtained by 20 points.

    State said

    We took the train location and train the walking distance and each station wagon form called a problem.Change these values is still the same problem we get, but the parameters are changed.We can see that each time we move a train, our problem turned into a different problem.In order to calculate the best mobile solutions, we must traverse the status and then make decisions based on the state.Let's getstarted.

    We'llstart with defining the train route.Because the line is not straight, so the figure is the best.

1 import math

    2 from decimal import Decimal

3 from collections import namedtuple, default



     class TrainRoute: 5

     def __init__( self ,start, connections): 6

     self .start =start 7

     self .E = defaultdict( set ) 8

     self .stations = set () 9

     for u, v in connections: 10

     self .E[u].add(v) 11

     self .E[v].add(u) 12

     self .stations.add(u) 13

     self .stations.add(v) 14

     def next_stations( self , u): 15

     if u not in self .E: 16



     yield from self .E[u] 18

     def fuel( self , u, v): 19

     x = abs (u.pos[ 0 ] - v.pos[ 0 ]) 20

     y = abs (u.pos[ 1 ] - v.pos[ 1 ]) 21

     return Decimal(math.sqrt(x * x + y * y))






    TrainRoute class implements a very basic directed graph, it put the height as a collection, the station is the connection between the station there is a dictionary.Please note that we have (u, v) and (v, u) two sides added, because the train can move backward and forward.

    In next_stations approach has an interesting thing, here I use a cool Python 3 featuresyield from.This allows a generator Can be assigned to another generator or iterator.Because each station is mapped to a collection of the station, we only need to iterate through it.

    Let's take a look at the main class:

1 TrainWagon = namedtuple( 'TrainWagon' , ( '

     dest' , 'value' ))


     TrainStation = namedtuple( 'TrainStation' ,

    3 ( 'name' , 'pos' , 'wagons' ))

4 class TrainEmpire:

5 def __init__( self , fuel, stations, route



     self .fuel = fuel


     self .stations = self ._build_stations(stat

    8 ions)

9 self .routes = self ._build_routes(routes)

10 def _build_stations( self , station_lines):

11 # ...

    12 def _build_routes( self , route_lines):

13 # ...

    14 def maximum_route_score( self , route):

    15 def score(state):

16 return sum (w.value for (w, s) in state.wgs

     if w.dest = = 17

     def wagon_choices(state, t): 18

     # ...


     def delivered(state): 20

     # ...


     def next_states(state): 22

     # ...


     def backtrack(state): 24

     # ...


     # ...


     def maximum_score( self ): 27

     return sum ( self .maximum_route_score(r) f

    28 or r in self .routes)










    I omitted some code, but we can see some interesting things.twoNaming a tupleWill help keep our data and tidy and simple.The main class have our train can run the longest distance, fuel, and route of these parameters and the station.Maximum_score method to calculate the sum of scores on every route, will become the interface to solve the problem, so we have:

    ; A main class to hold the connection between the line and station

    ; A station a tuple, the entity name, position and the current

    existence of truck list

    ; A station wagon with a value and purpose

    Dynamic programming

    I have tried to explain the dynamic planning how to efficiently search the key to the state space, and based on the existing state of the optimal decisions.We have a defined the position of the train, the train of the rest of the fuel, and the position of the each truck's state space - so we can already said initial state.

    We must now consider each decision in each station.We should loading a truck and then send it to the destination?If we get off at the next station found a truck is more valuable?We should to send it back or move?Or still not move with the truck?

    Obviously, the answers to these questions is that we can get more scores.In order to get the answer, we must find out all possible cases after the previous state and the value of a state.Of course we use function score to evaluate the value of each state.

1 def maximum_score( self ):

    2 return sum ( self .maximum_route_score(r) f

     or r in self .routes)


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

5 wgs = set ()

6 for s in route.stations:

7 for w in s.wagons:

8 wgs.add((w, s))

    9 initial = State(route.start, self .fuel, tu

     ple (wgs))


    From each state has several options: either with a truck to move to the next

    station, or not to bring a truck to move.Stay still not to enter a new state,

    because everything is not changed.If the current stations have more than one

    truck, move one of them will be into a different state.

1 def wagon_choices(state, t):

    2 yield state.wgs # not moving wagons is an o

     ption too


     wgs = set (state.wgs)


     other_wagons = {(w, s) for (w, s) in wgs if5 s ! = state.s}

6 state_wagons = wgs - other_wagons

7 for (w, s) in state_wagons:

8 parked = state_wagons - {(w, s)}

9 twgs = other_wagons | parked | {(w, t)}

10 yield tuple (twgs)

11 def delivered(state):

12 return all (w.dest = = for (w, s) in



     def next_states(state):


     if delivered(state):




     for s in route.next_stations(state.s):


     f = state.f - route.fuel(state.s, s)


     if f < 0 :




     for wgs in wagon_choices(state, s):


     yield State(s, f, wgs)



    Next_states is a state of a state as a parameter and return all this can reach the state of the generator.Note how it is in all the freight moved to stop at the destination, or into a state it only to those who still enough fuel.Wagon_choices function may seem a bit complicated, but in fact it can return only those from the current collection station to the next station wagon.

    So we have realized the dynamic programming algorithm need all of the things.Westart from the initial state search our decisions, and then select a most strategy.Look!Initial state will evolve into a different state, the state will also evolve to a different state!We are designing is a recursive algorithm:

    ; To obtain state

    ; Our decision

    ; To make the optimal decision

    Obviously each of the next state will make this a series of the same thing.Our

    recursive function will be the fuel used up or all of the trucks were carrying

    destination when to stop.

1 max_score = {}

    2 def backtrack(state):

3 if state.f < = 0 :

4 return state

5 choices = []

    6 for s in next_states(state):

    7 if s not in max_score:

    8 max_score[s] = backtrack(s)

    9 choices.append(max_score[s])

10 if not choices:

11 return state

12 return max (choices, key = lambda s: score



     max_score[initial] = backtrack(initial) 14

     return score(max_score[initial]) 15


    Last trap: complete dynamic planning strategy in the code, you can see I use a max_score dictionary, it actually caching algorithm through each state.So we don't repeat over and over again through our decisions we have already experienced.

    When we search the state space, a station may reach several times, some of these may lead to the same fuel, the same truck.The train arrived here how it doesn't matter, only have influence on the decision at that time to do.If we we calculated the state once and saved as a result, we no longer need to search again this subspace.

    If we did not use itMemory,Technology, we can do a lot of the same search.This usually results in our algorithm to efficiently solve our problems. conclusion

    "Train" Empire provides an excellent example of how to display the dynamic programming in the problem of overlapping problems make the optimal decision.Python is a powerful expression ability let us once again simply can implement the idea, and write a clear and effective algorithm.

Report this document

For any questions or suggestions please email