Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic programming - Coggle Diagram

- - - - //Applies dynamic programming to find the minimum number of coins
      - //of denominations d1 < d2 < ... < dm where d1 = 1 that add up to a
      - //given amount n
      - //Input: Positive integer n and array D[1..m] of increasing positive
      - // integers indicating the coin denominations where D[1] = 1
      - //Output: The minimum number of coins that add up to n
  - - - //Applies dynamic programming to compute the largest number of
      - //coins a robot can collect on an n × m board by starting at (1, 1)
      - //and moving right and down from upper left to down right corner
      - //Input: Matrix C[1..n, 1..m] whose elements are equal to 1 and 0
      - //for cells with and without a coin, respectively
- - - - The following well-known greedy algorithm is based on the nearest-neighbor
      - heuristic: always go next to the nearest unvisited city.
      - Step 1 Choose an arbitrary city as the start.
      - Step 2 Repeat the following operation until all the cities have been visited:
      - go to the unvisited city nearest the one visited last (ties can be broken
      - arbitrarily).
      - Step 3 Return to the starting city
  - - - Step 1 Construct a minimum spanning tree of the graph corresponding to a given instance of the traveling salesman problem.
      - given instance of the traveling salesman problem.
      - Step 2 Starting at an arbitrary vertex, perform a walk around the minimum spanning tree recording all the vertices passed by. (This can be done by a DFS traversal.)
      - Step 3 Scan the vertex list obtained in Step 2 and eliminate from it all repeated
      - occurrences of the same vertex except the starting one at the end of
      - the list. (This step is equivalent to making shortcuts in the walk.) The
      - vertices remaining on the list will form a Hamiltonian circuit, which is
      - the output of the algorithm.