Dynamic Programming algorithms ::

Developing dynamic programming algorithms ::

When developing a dynamic programming algorithm, we follow a sequence of four steps ::

  1. Characterize the structure of an optimal solution
  2. Recursively define the value of an optimal solution
  3. Compute the value of an optimal solution, typically in a bottom-up fashion
  4. Construct an optimal solution from the computed information

Top down approach ::

  • Write the procedure recursively in a natural manner
  • Save the result of each subproblem you already computed
  • When it becomes necessary to solve a subproblem, we first check whether we have solved this particular problem before –> save computation !

Bottom up approach ::

  • typically depends on some natural notion of the “size” of a subproblem, such that solving any particular subproblem depends only on solving “smaller” subproblems.
  • Sort the subpoblems by size and solve them in size order, smallest first. Save all results
  • When solving a particular subproblem, we have already solved all of the smaller subproblems.

Which one to use ::

  • Usually both approaches have similiar running times
  • In some cases, top-down is faster because it does not have to look at all sub-problems.
  • Bottom-up is often easier to implement, because of less overhead for procedure calls

Caveat of Dynamic programming algorithms ::

Dynamic programming only works if the subproblems we need to combine to get the larger solution are independent from each other. Example would be :: shortest path vs longest path in a graph.

  • Assume the shortest path between u and v contains vertex w. Then combining any shortest path u to w and w to v results in a shortest path between u and v
  • For the longest simple path problem, this is not true however. Assume you know that the longest simple path between u and v contains w. Then this path is not necessarily the combination of the longest paths between u and w and w and v

WHY ? Because we cannot guarantee that there is not other vertex where there exists an even longer path between the given vertex >> we previously only searched for the shortest path, not saving or finding the longest connection!

Problems that can be solved with DPA ::

==Absolutely necessary condition:==

  • optimal substructure optimal solution can be constructed from optimal solutions to its subrpoblems - this faield in longest simple path problem

==Desirable condition==:

  • the problem can be broken into subrpoblems which are reused several times.

Examples of Dynamic Programming Algorithms ::

Eight queens problem

![[Pasted image 20230113114335.png]] place 8 queens on the field without them interfering each other.

We can give several approaches to solve this problem, each is dependant on how much trials we give it.

Enumeration strategy 1 ::

We know that a chess field contains 64 fields. Now we simply test every condition and check whether it is possible or not. This results with = 8.446.744.000.000.000.000steps to be taken. >> waaay too long, ==undesirable==!

Enumeration strategy 2 ::

Actually we only have to place 8 queens at most. So we could use = 64 * 63 * … = 9.993.927.307.714.560 >> not as much possibilities left >> yet still way too long !

Enumeration strategy 3 ::

We can improve our previous strategy because we are basically doubling several occurences, like (3,1), (3,1) >> that occure multiple times yet would be the same computation. We can further reduce the amount of computations due to : The amount of computations is reduced because we are converting to ordered vectors of positions, thus avoiding double occurences of values lie (3,1) .. .

Enumeration Strategy 4 ::

We know that each column must have exactly one queen :: we have a total of 8 queens, further there are only 8 columns. Per Definition a queen is able to move a whole line vertically and horizontally, thus we can only place one queen at each column at max.

![[Pasted image 20230113132327.png]]

Our resulting amount of computations lowers to ::

Enumeration strategy 5 ::

By exploiting our requirements we can further decrease the amount of computation require ::

Not only are we limited to at most one queen per column, but also per row. This means that our computation could lower to : .

We could further improve by introducing more constraints, such as rotations, reflections, yet that will be difficult to implement and thus not worth the effort, as 40k computations are low enough already.

To give an estimate what time we saved with those constraints :: Strategy 1 18.446.744.000.000.000.000 58 million years
Strategy 2 9.993.927.307.714.560 3000 years
Strategy 3 4.426.165.368 5 days
Strategy 4 16.777.216 28 min
Strategy 5 40.320 4 sec

it makes a difference which enumeration strategy is used. We should therefore always exploit as much knowledeg as possible #Tip