Tablica Dwuwymiarowa - Algorytm znajdujący drogę z największą sumą.

pytanie zadane 11 października 2015 w Algorytmy przez WWOTEX Mądrala (6,200 p.)

Witam,
Mam problem algorytmiczny w pewnym zadaniu...
Dana jest tablica dwuwymiarowa i każdy z elementów tablicy to liczba.
Muszę znaleźć taką drogę z punktu A do punktu B, aby była to jedna z najkrótszych (czyli poruszać mogę się tylko w dół i prawo) oraz żeby suma miniętych liczb była największa.
Ta tablica może być nawet długa i szeroka na 10000 elementów, więc jak zrobić to w szybki sposób? W sensie, żeby nie musieć sprawdzać każdej drogi po kolei, bo ich będzie mnóstwo.

A 2 3 4
1 3 4 5
9 2 9 B -> utaj np droga najlepsza to A 1 9 2 9 B

Z góry dziękuję za pomoc!

1 odpowiedź

odpowiedź 11 października 2015 przez adrian17 Ekspert (344,860 p.)
wybrane 11 października 2015 przez WWOTEX

Najlepsza

Napisz swojego rodzaju BFS. Wiesz, że do każdego punktu można się dostać tylko z dwóch stron, góry i lewej, więc "wartość" drogi do tego punktu jest sumą większej z poprzednio policzonych dwóch możliwych dróg do tych dwóch sąsiadów z tym punktem.

Można wyobrazić sobie takie "czoło" po kolei liczące największą możliwą sumę do tego punktu:

A  *  *  *
*  *  *  *
*  *  *  B

A  2  *  *
1  *  *  *
*  *  *  B

A  2  5  *
1  5  *  *
10 *  *  B

A  2  5  9
1  5  9  *
10 12 *  B

A  2  5  9
1  5  9  14
10 12 21 B

komentarz 11 października 2015 przez WWOTEX Mądrala (6,200 p.)

NORMALNIE GENIUSZ!!!! Dzięki, :D

komentarz 12 października 2015 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Moim zdaniem przy zadaniach algorytmicznych nie powinno podawać prawie, że odpowiedzi ale wskazówki. Lecz to tylko moja sugestia. Jak już padła odpowiedź to róznież dobrym pomysłem było by programowanie dynamiczne. Tylko w tym przypadku dynamik się pokrywa z BFS`em.

komentarz 12 października 2015 przez WWOTEX Mądrala (6,200 p.)

dynamiczne w sensie na wskaźnikach? ta macierz jest u mnie na wskaźnikach

komentarz 12 października 2015 przez adrian17 Ekspert (344,860 p.)

Moim zdaniem przy zadaniach algorytmicznych nie powinno podawać prawie, że odpowiedzi ale wskazówki.

Faktycznie, możesz mieć rację że powiedziałem za dużo na raz.

dynamiczne w sensie na wskaźnikach? ta macierz jest u mnie na wskaźnikach

Nie, to zupełnie inny temat. "programowanie dynamiczne" to sposób tworzenia algorytmów rozwiązujących problemy. Najlepiej wrzuć termin do wikipedii i poczytaj.

I tak, w tym przypadku tak się składa że to co napisałem można uznać za rozwiązanie DP :P

komentarz 12 października 2015 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

"I tak, w tym przypadku tak się składa że to co napisałem można uznać za rozwiązanie DP :P" Dlatego napisałem, że się w tym przypadku pokrywają :) Nie rozdrabniajmy się nad błachostkami.

Wyjaśnienie dynamicznego programowania -> http://www.algorytm.org/kurs-algorytmiki/programowanie-dynamiczne.html

Jeśli bawisz się w algorytmikę to nie radzę bawić się w wskaźniki, tylko jak potrzebujesz tablicę z 50000 elementami to ją deklarujesz po za mainem ( sądzę, że kodzisz w c++ ) .