Ovo neće biti lako objasniti samo rečima...
Imaš polaznu matricu koja je puna nekih brojeva. Imaš zbirnu matricu istih dimenzija, koja je u početku popunjena nulama, i vrednosti iz prve kolone su iskopirane iz polazne matrice. Cilj je da u zbirnoj matrici "skupljaš maksimalne zbirove". Zbirnu matricu obrađuješ kolonu po kolonu, tako što za svako polje iz tekuće kolone gledaš kuda sve može da se skoči iz tog polja. Svaki put kad obrađuješ novi skok dodaješ novi sabirak iz polazne matrice na postojeću vrednost iz zbirne matrice. Ako je dati zbir veći od onog koji već stoji u doskočenom polju onda postavljaš tu novu vrednost u doskočeno polje. Kada se to desi faktički si pronašla bolje rešenje da se dođe do tog polja od onog koje si nešto ranije našla.
Teško je ovo rečima pojmiti, pa zato hajde da probamo primerom. Polazna matrica je data, i ja ću simulirati svaki od dvanaest koraka.
1 0 0 0 1 0 0 0 1 0 8 0 1 11 8 0 1 11 8 0 . 1 11 14 0 1 11 14 0 1 11 14 0 1 11 14 26 1 11 14 26 . .
5 0 0 0 5 0 8 0 5 0 8 0 5 0 16 0 5 0 16 19 . 5 0 16 19 5 0 16 19 5 0 16 19 5 0 16 19 5 0 16 19 . .
9 0 0 0 9 11 0 0 9 11 16 0 9 11 16 0 9 11 22 0 . 9 11 22 0 9 11 22 26 9 11 22 26 9 11 22 26 9 11 22 26 . .
14 16 22 26
Boldovano je polje koje trenutno obrađujemo, crveno su polja na koja trenutno polje može da utiče. U četvrtom redu je krajnji rezultat. Rešenje za ovaj primer je 26. Tačke između pete i šeste matrice označavaju da nije moguće dopreti do polja u kome stoji vrednost 6. Pošto nije moguće dopreti onda se i ne uzima u obzir. Ovde ima mali problem kako detektovati to polje, ali to ćemo nekom drugom prilikom. Tačkice posle poslednje matrice označavaju da obrada poslednja dva polja neće doneti veći zbir (to jest poslednja matrica bi se ponovila još dva puta, a rezultat bi ostao 26).
Registrovani: 4 ( daca80, privremeni, Woodoo, backbiter17 )
[Zadatak] Odredjivanje optimalne putanje u matrici