Двумерное динамическое программирование

[ashvosk]

opamagite reshit zadachu prashu ochen nado

дана A[n][m] матрица из натуральных чисел (2<=n,m<=100), и при прохождении (i,j) обьекта начисляется штраф A[i][j]. Наше задание попасть из любового элемента первой строчки в n-ную строчку. При этом из конкретного элемента можно продолжить движение к 3 соседним элементам нижней строчки.
Напишите программу которая выполнит данную задачу и минимизирует размер шрафа..
ashvosk на форуме Добавить отзыв для ashvosk Пожаловаться на это сообщение

(C++)

[p51x]

http://www.programmersforum.ru/showthread.php?t=300954

[ashvosk]

ne obezatelno reshit za meya mojna dat bodskazku

[p51x]

Так задача в лоб решается просто:
1. строим прямой путь от одного элемента до нужно, например, по прямой
2. https://en.wikipedia.org/wiki/Backtracking с параметром из предыдущего шага
3. по условию задачи отсекаем или добавляем решения

[Croessmah]

Звучит-то как, - "Двумерное программирование".

[olej.tsil]

Сообщение от ashvosk

mojna dat bodskazku

Даю бодсказку :

- это классически рекурсивная задача...
- для текущей позиции в цикле (по 3-м соседям) вызываете всё ту же функцию накопления штрафа...
- и суммируете значения штрафов...
- при этом где-то (в статической, глобальной переменной, дополнительном параметре функции...) храните минимально найденное до сих пор значение накопленного штрафа.

[olej.tsil]

Сообщение от olej.tsil

- это классически рекурсивная задача...

Интересно стало (задача).
У вас должно получиться что-то типа такого:

#include <vector> 
#include <iostream> 
using namespace std; 

typedef vector<vector<float>> matrix;

ostream& operator <<( ostream& out, vector<int>& v ) {
   out << "[ ";
   for( auto i = v.rbegin(); i < v.rend(); i++ ) cout << *i << " ";
   return out << "]";
} 

float min_trace( matrix& m, int y, int x, vector<int>& t ) {
   if( y == (int)m.size() - 1 ) {
      t.push_back( x );
      return m[ y ][ x ];
   }
   float mval = 1E99;
   vector<int> tvec;
   for( int ix = x - 1; ix <= x + 1; ix++ ) {
      if( ix < 0 ) continue;
      if( ix == (int)m[ y ].size() ) continue;
      vector<int> vec;
      float val = m[ y ][ x ] + min_trace( m, y + 1, ix, vec );
      if( val < mval ) {
         mval = val; 
         vec.push_back( x );
         t = vec;
      }
   }
   return mval; 
}

int main( void ) {
   matrix M = { 
      { 1, 2, 3, 4, 5, 4, 3, 2, 1 },
      { 2, 3, 4, 5, 4, 3, 2, 1, 0 },
      { 3, 4, 5, 4, 3, 2, 1, 0, 1 },
      { 4, 5, 4, 3, 2, 1, 0, 1, 2 }, 
   };
   cout << "матрица [ " << M.size() << "x" << M[ 0 ].size() << " ] :" << endl;
   for( auto &y : M ) {
      for( auto x : y ) cout << x << " ";
      cout << endl;
   }
   cout << "--------------------------------" << endl;   
   float mval = 1E99;      
   vector<int> tvec;
   for( int i = 0; i < (int)M[ 0 ].size(); i++ ) {
      vector<int> vec;
      float val = min_trace( M, 0, i, vec );
      if( val < mval ) {
         mval = val;
         tvec = vec;
      }   
   }
   cout << "минимальная трасса " << mval << " : ";
   cout << tvec << endl;
}

Это будет работать для матриц любой ширины и глубины:

$ ./straf 
матрица [ 4x9 ] :
1 2 3 4 5 4 3 2 1 
2 3 4 5 4 3 2 1 0 
3 4 5 4 3 2 1 0 1 
4 5 4 3 2 1 0 1 2 
--------------------------------
минимальная трасса 1 : [ 8 8 7 6 ]