Trójkąt liczbowy. Optymalizacja kodu.

Mam taki sobie trójkąt liczbowy podobny do tego:

    1
  2  3
4  5  6

7 8 9 10

I mam znaleźć największą sumę jaka powstanie poprzez przechodzenie w dół w lewo lub prawo. Np: 1->3->6->10 i tu wyjdzie największa liczba '20'. Nie można iść w taki sposób 1->3->4->10. Mój problem jest taki, że mój trójkąt ma 200 poziomów i są w nim rozmieszczone (losowo) liczby od 0 do 99. Program, który sprawdza wszystkie możliwości będzie robił 2^200 obliczeń. Zajmie to miliony lat. Ulepszyłem, więc lekko ten program aby na każdym szczeblu sprawdzał czy ma szansę mieć większą liczbę niż dotychczasowe maximum. Jeśli nie to omija tą możliwość.

Dam kod mojego programu. (Jest troszę duży więc dam tylko linka http://niteria.webpark.pl/main.cpp) Tylko proszę się nie śmiać, bo kodzik trochę lamerski. W tablicy a[200][200] mam ten trójkąt jako podobną do tego tablicę:

1 0 0 0
2 3 0 0
4 5 6 0
7 8 9 10

Jeśli ktoś ma jakiś pomysł jak zmienić ten kod aby działał szybciej lub ma pomysł na lepszy algorytm do zrobienia tego to proszę o pomoc.

Acha sam[200] to kolejne sumy na kolejnych szczeblach.

Z góry dzięki!

Twój problem jest problemem zlożoności typu O(N!). Oznacza to że czeka cię eksplozja wykładnicza jeśli czegoś nie zmienisz. Czyli przyjmując że twój procesor np. jest w stanie dokonać miliona przeliczen na sekunde to mając 18 poziomowy trójkąt zajęło by mu to jakieś 200 lat. Istnieje metoda "brute force" gdzie zawsze wybierasz większą z dwóch liczb, jednak często to rozwiązanie nie daje największej możliwej liczby. Można też zrobić stosując technikę "dziel i zwyciężaj" dzieląc duży trójkąt na na mniejsze i te mniejsze na jeszcze mniejsze. Polecem ci poszukanie w google problemu "komiwojażera" bo to jest podobny problem do twojego.

ja mysle ze to bedzie cos takiego:

#include <ctime>
#include <iostream>

using namespace std;

const unsigned ILOSC_POZIOMOW = 10;
const unsigned ILOSC_ELEMENTOW = ((ILOSC_POZIOMOW + 1)*ILOSC_POZIOMOW) / 2;

struct TElement{
  unsigned wartosc; //wartosc danego elementu
  unsigned ponizej; //wartosc elementow maksymalnych ponizej
  unsigned wybor; //jaki element nalezy wybrac ponizej
};


TElement elementy[ILOSC_ELEMENTOW];

unsigned s1(unsigned r){//zwraca pozycje lewego syna rodzica r
  unsigned poziom = 0, l = 0;
  while(poziom <= r){
    poziom += l;
    l++;
  }
  return l + r - 1;
}

int main(){
  srand(clock());
  for (unsigned i = 0; i < ILOSC_ELEMENTOW; i++){
    elementy[i].wartosc = rand() % 100;
    elementy[i].ponizej = elementy[i].wybor = 0;
  }
  unsigned poziom = ILOSC_POZIOMOW - 1;//idziemy od przedostaniego poziomu
  //ustawienie wskaznika na koniec przedostatniego poziomu
  TElement * wsk = elementy + ILOSC_ELEMENTOW - 1 - ILOSC_POZIOMOW;
  while (poziom){//najmniejszym poziomem jest 1
    for (unsigned i = 0; i < poziom; i++){//dla danego poziomu
      //ustal syna, dla ktorego jest najwieksza suma ponizej i wlacznie z nim
      unsigned syn = s1(wsk - elementy);
      if ( (elementy[syn].wartosc + elementy[syn].ponizej) >
           (elementy[syn + 1].wartosc + elementy[syn + 1].ponizej) ){
        wsk->ponizej = elementy[syn].wartosc + elementy[syn].ponizej;
        wsk->wybor = syn;
      } else {
        wsk->ponizej = elementy[syn + 1].wartosc + elementy[syn + 1].ponizej;
        wsk->wybor = syn + 1;
      }
      wsk--;//przejdz do kolejnego elementu na poziomie
    }
    poziom--;//przejdz poziom w gore
  }
/*
** Wypisanie wygenerowanego trojkata
*/
  unsigned l = 0;
  poziom = 1;
  while (l < ILOSC_ELEMENTOW){
   for(unsigned i = 0; i < poziom; i++)
    cout << elementy[l++].wartosc << " ";
   poziom ++;
   cout << endl;
  }
/************************************************************************/
  cout << "\n\nWynik\n";
  wsk = elementy;
  do{
    cout << wsk->wartosc << " ";
    wsk = &elementy[wsk->wybor];
  } while (wsk->wybor);
  cout << wsk->wartosc << endl;
  cin.get();
  return 0;
}

Dzięki. Czy zna ktoś dobry tutor na temat programowania dynamicznego??

nit3ria napisał(a)

Czy zna ktoś dobry tutor na temat programowania dynamicznego??
A cóż to takiego "programowanie dynamiczne"? :)

//do postu poniżej
dzięki :)

Programowanie Dynamiczne