towhid1zaman's blog

By towhid1zaman, history, 5 years ago, In English

How Can I solve this -( Unidirectional TSP ) problem !

Problem : Given an m x n matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i+1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix “wraps” so that it represents a horizontal cylinder. The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited.

Will be grateful if anyone can help. Thank You.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Define your states dp[row][col] which is the minimal weight path starting at cell (row, col)

Now transitioning should be easy:

  • a direct move is dp[row][col+1]
  • an UP move is dp[row-1][col+1] (or dp[n-1][col+1] if you're currently in row 0)
  • a DOWN move is dp[row+1][col+1] (or dp[0][col+1] if you're currently in row n-1)

    You just take the minimum of all 3

    The base case is that dp[i][m-1] = a[i][m-1] for all i