این یه برنامه داینامیک به حساب میاد و خیلی هم مساله معروفیه! البته خود همین مساله نه اما مشابهش.
Unidirectional TSP Problem:
Input: An m*n matrix, each cell contains the cost of passing thru that cell.
Output: A path with minimum path-sum from column 0 (leftmost) to column n-1 (rightmost). The path can wraps horizontally.
Let M(i,j) be the minimum value of Unidirectional TSP problem for row i and column j and A[i,j] be the value of the matrix of size m*n. i and j starts from index 0.
Recurrence Relation:
;; For first column (col 0), the minimum value is the array value itself.
M[i][0] = A[i][0];
;; For all column j > 0, the minimum value is between one of these three,
;; plus the value of A[i][j].
M[i][j] = A[i][j] + Min(M[(i+m-1)%m][j-1],
M[i][j-1],
M[(i+1)%m)][j-1]);
;; To output the path, remember the previous row that we choose at current
;; column.
منبع Steven Halim Website
پاسخ با نقل قول
