[Pascal] Ciekawy program na zaliczenie...

0

Ostatnio na zaliczenie miałem takie ciekawe zadanie na 5, którego nie zabardzo umiałem i umiem rozwiązać dlatego zrobiłem tylko na 4... :( Dobra ale do rzeczy. Ma się tabelę 15x15 i wypełnia się ją liczbami losowymi! z jakiegoś zakresu (np od 1 do 5, lub innym) i trzeba znaleźć drogę o najmniejszej wartości sumy liczb zawartych w polu przez które sie przechodzi z komórki (1,1) do komórki (15,15) a następnie ją wypisać... Można się poruszać o jedną komórkę w poziomie i pionie.

Ma ktoś pomysł na ten program, pomysł, nie rozwiązanie, nie gotowiec!

0

może sprawdzać wartości następnych możliwych ruchów i przechodzić na pole o najmniejszej możliwej wartości do tego poruszać się albo w lewo albo w dół... ale to chyba nie tak by wyszło.

0123456 algorytm <ort>najkrutszej </ort>drogi: poruszamy się od 0 na pole o kolejnej wartości
1234567 tylko, że ta losowa tablica trochę komplikuje.
2345678
3456789
456789X

0

rekurencyjne wołanie siebie dla 4 sąsiadów z pamiętaniem ścieżki i "kosztu".
po dojściu sprawdzam czy osiągnąłem mniejszy koszt niż wcześniej
być może istnieje dowcipniejszy sposób, takie podejście powinno też zadziałać
parę wierszy, ale jakiej złożoności należy oczekiwać?

0

No właśnie w tym problem, że sor nie dał żadnym wskazówek, mówił,że trzeba mieć SPOSÓB, a nie sprawdzać każdą drogę. Najlpeszym wyjściem też mi się wydawało jest szukanie sąsiedniego pola o najmniejszej wartości i to by się sprawdzało dla 99%, bo ten sposób obala taki przypadek:
user image

Żółta trasa odpada...

0

oczywiście że to jest zły sposób, bo niskie wartości z 'dalszej' drogi od danego punktu mogą rekompensować drogi koszt drogi do niego.
a może jakieś wyznaczniki ? :P myślę również, że w jakiś sposób mogła by się przydać tablica wartości sum z wszystkich kolumn, wierszy, i ukośnie również / .
a tak poza tym to ciekawy problem, zauważcie że nawet dla człowieka znalezienie rozwiązania nie jest oczywiste.

0

Chyba na pierwszy rzut oka powinno się odrzucić sposób polegający tylko na sprawdzaniu minimalnego sąsiada. Ale intuicja to mniej niż dowód.

chym, parę trywialnych wniosków:
minimalna długość ścieżki to N+1, oczywiście że nie musi to być najtańsze rozwiązanie.
macierz jest nieujemna, czyli minimalny koszt to t[1,1]+t[n,n]+"cóś"
czy "cóś" może być zerem? (zabawa polega na minimalizacji "cósia")
może, i wcale nie wymaga to zer w całej tablicy (poza t[1,1] i t[n,n])

tak na czuja to jest to jakoś podobne do problemu szukania podciągu o maksymalnej sumie

ciekawe, na ile sposobów można przejść od [1,1] do [n,n]?
na początek to właśnie pobadam

0

Na mój gust, rozwiązanie to potraktowanie tej tablicy jako grafu i zastosowanie algorytmu Dijkstry (czyli wyszukania najkrótszej (oczywiście z uwzględnieniem "wag") ścieżki).

0

Dokladnie o tym myslalem, bylo to troche dawno bo chyba na drugim semestrze ale mnie sie zdaje ze tych algorytmow na szukanie najkrotszej drogi bylo kilka. Poszperaj.

0

Nauczyciel raz juz dał na lekcji taki program do zorbienia, nikt nie miał pomysłu, a nauczyciel nie dał wskazówek... Te liczby mogą być z każdego zakresu również od 0. Przecież dobry program powinien działać dla każdego zakresu lokowanych w tablicę liczb.

Intrygujące zadanie co? :D

mgr.Dobrowolski, po magister (mgr) nie stawia się kropki :)

0

na pewno nie trzeba sprawdzać wszystkich dróg do końca, bo po przejściu 1szej w ten sposób, mogę przy następnej w pewny momencie sprawdzić:
'mając już taką sumę, nawet idąc najkrótszą możliwą stąd drogą zakładając że po drodze będą najniższe z możliwych wartości, otrzymana suma całkowita będzie większa od sumy z najlepszego jak do tej pory (czyli z 1szego) wyniku'

0
Wilkołak napisał(a)

...mgr.Dobrowolski, po magister (mgr) nie stawia się kropki :)

Ty to wiesz i ja to wiem, kiedyś może (ale raczej nie) przestanę używać kropki.

0

zadanie żaby na pierwszym etapie OI w tamtym roku

tu masz moj kod:
http://pastebin.4programmers.net/1657

wytniesz sobie tylko generowanie mapy i swoje wstawisz i włala :)

EDIT: nie doczytalem dokladnie :P. No ale moze cos z tego zadania wpadnie Ci do glowy ;)

EDIT: a jednak jak sie zastanowilem, to wlasciwie kod gotowy :D. Tylko sobie pare rzeczy musisz odwrocic...

ogolnie na zasadzie - w kolejce (priorytetowej?) sobie siedzą wszystkie pola graniczne, stopniowo podnosisz "poprzeczkę" i włączasz punkty które zaczynają się zaliczać pod poprzeczkę z kolejki, dodajesz sąsiadów nieodwiedzonych. Koniec jest, jeżeli sąsiadem jest koniec ścieżki. W tablixy 15x15 zapisujesz:

  • czy punkt jest odwiedzony/w kolejce (bool)
  • jaka ma minimalna odleglosc (zapisywane przy dodawaniu do kolejki)
0

Liczba sposobów w jakie można przejść od [1,1] do [N, N] rośnie okropnie szybko, już dla 6*6 przekracza milion.
Kilka początkowych wartości:
1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100

0

no i co z tego - kto powiedzial, ze nalezy sprawdzic wszystkie?

powyzej podalem sposob liniowo zalezny od wielkosci planszy, co wiecej prawie sprawdzil sie dla n=1000 (czyli plansza 10^6 pol). Prawie, bo gdzies jakis glupi blad zrobilem i program podawal lekko zle odpowiedzi.

nie chce byc niemily, ale jaka jest mozliwa liczba drog dla planszy 1000*1000? :>. I dlaczego moj program liczy to w 3.5s wlaczajac czas potrzebny na obliczenie mapy?

0

jest to przykład zadanka którego nie da się rozwiązać sprawdzając wszystkie możliwości.
Dla mapy 15x15 istnieje 227449714676812739631826459327989863387613323440 możliwych dróg :-)
(48 cyfr) ciekawe ile czasu zajęłoby to wszystkim komputerom spiętym internetem?

24! (silnia) ma 24 cyfry - gdyby generować milion permutacji na sekundę, to czas potrzebny na utworzenie wszystkich, przekracza wiek wszechświata

0

Zawsze można to zrobić sprawdzając wszystkie możliwe drogi i trasę najtańszej zapisywać ;)

Eee mgr.Dobrowolski mnie wyprzedził :P

0

czy tu mnie ktos slucha? :D

po co sprawdzac wszystkie drogi? Po co sprawdzac w ogole drogi? Nie zawsze, jesli w zadaniu jest mowa o drogach nalezy je jako drogi traktowac - w tym przypadku jest to wyliczanie zawartosci tablicy - znajac dlugosc najkrotszej drogi (wg. mojego rozwiazania) nie mozemy jej bezposrednio podac, jezeli nie zapisywalismy dodatkowych informacji!

poza tym - podalem dzialajace rozwiazanie, co tu sie jeszcze glowic? :D Rownie dobrze mozna rozwazac setki dowodow, dla ktorych google nie mialo by prawa dzialac (miliony zapytan do miliardów stron wykonuja sie srednio w ulamki sekund)

0

no właśnie, teraz tylko czekajmy na Wilkołaka aż się odezwie, jako główny zainteresowany wypadałoby, żeby sie Twoim rozwiązaniem zajął :)

0

Dobra, odzywam się :P

http://www.matematyka.pl/viewtopic.php?p=137212#137212 zajrzyjcie tu :)

Problem, o który pytasz, jest dokładnie opisany w książce M.M.Sysło 'Piramidy, szyszki i inne konstrukcje algorytmiczne' - serdecznie polecam przeczytanie, jeśli nie chcesz zobaczyć gotowca. Oczywiście aby uzyskać optymalne rozwiązanie w tym zadaniu należy tu użyć metody programowania dynamicznego. Pozdrawiam 😉

Ma ktoś tą książkę?

Waszych metod nie testowałem, mam teraz dużo pracy (klasówka za klasówką i olimpiada :) ).

0

od czasu do czasu widać tę książkę na Allegro (ostatnio coś koło 40zł).

kurdę głupio mi, ale jakoś nie czuję rozwiązania Tomkiewicza
zapisałem to sobie tak na wprost:
jeżeli bieżący koszt przewyższa uzyskane wcześniej minimum, nie warto badać dalej.
nie warto bo każdy krok doda nieujemną wartość.
długość najkrótszej drogi to 2N-1, jeżeli losowane wartości to coś od zera a MaxVal,
wtedy, na początek, koszt minimalnej drogi to (2
N-1)MaxVal.
dla 15
15 działa powiedzmy sensownie
Tomkiewiczu, a powiedz czym pierwotnie zajmował się Twój program?
Mówiłeś o pewnych problemach z programem, na czym polegały?

0

optymalizacje, o ktorych mowisz przyspiesza bruta tak na oko dwukrotnie ;).

zadanie wyglada tak: na polu sa rozmieszczone odstraszacze żab, żaba przechodzi przez nie jak najdalej od odstraszaczy. wypisz kwadrat (tw. pitagorasa) odleglosci od najblizszego odstraszacza, obok ktorego prszeszla zaba. W szczegolnosci zero.

Blad (tak mysle) polegal na obliczaniu mapy odleglosci - nie sprawdzilem jakiegos warunku i nie liczyl jej dokladnie - pola odstraszania to okregi, ja pierwotnie robilem romby, potem jeszcze jakos to ulepszylem, ale jak widac niedostatecznie. Tak czy inaczej generowanie mapy w tym przykladzie trzeba inaczej zrobic

precyzujac moje rozwiazanie (rzeczywiscie to co podalem wymaga jeszcze zastanowienia jak mape przygotowac) - algorytm "mądrze" zachłanny:
1 generujemy mape
2 zerujemy tablice odwiedzono (bool)
3 dodajemy punkt startowy do kolejki priorytetowej i oznaczamy jako odwiedzoony, zapisujemy jako wartosci po prostu wartosc z mapy
4 1 petla (dopoki jest cos w kolejce)
4 2 bierzemy punkt z kolejki o najnizszej wartosci
4 3 petla (wszyscy nieodwiedzeni sasiedzi)
4 4 1 oznaczamy jako odwiedzony
4 4 2 do wartosci na mapie dodajemy wartosc zdjeta z kolejki priorytetowej w 4.2
4 4 3 dodajemy punkt do kolejki z wartoscia jako wlasnie wyliczona wartoscia z mapy
4 4 4 jezeli punkt jest punktem konca to przerwij petle i podaj wynik
5 jezeli petla sie zakonczyla bez podania wyniku, to droga nie istnieje

złożoność pesymistyczna (pomimo dwoch pętli) - O(n), gdzie n to ilosc pol. Poniewaz kazde pole jest wrzucane do kolejki najwyzej raz. Do optymalizacji można pominąć zapis wartości na mapę, ale wydrukowanie mapy pozwala na łatwiejsze debugowanie - punkty 4.4.2 i 4.4.3 skladaja sie w jeden

uzasadnienie czesci algorytmu mozna by bylo zerznac bezposrednio od dijkstry :)

0
tomkiewicz napisał(a)

optymalizacje, o ktorych mowisz przyspiesza bruta tak na oko dwukrotnie ;).
Przyśpieszenie jest znacznie większe. Dowodem niech będzie, że można doczekać się wyników.
Dla 15x15 czas mierzy się w sekundach.

0
mgr.Dobrowolski napisał(a)

Przyśpieszenie jest znacznie większe. Dowodem niech będzie, że można doczekać się wyników.
Dla 15x15 czas mierzy się w sekundach.

to jest dowodem, ze nie napisales az tak brutalnego bruta ;). Inna sprawa, ze dla wielkosci rzedu 1000x1000 bedzie juz kiszka, ale wykladowca chyba nie oczekiwal takiego rozwiazania jak podalem, skoro dal tak drobne limity. Inna sprawa, ze jak w takim przypadku Wilkołak zaprezentuje tablice 1000x1000, albo i jeszcze wieksza, to sor moze sie ucieszyc ;)

0

Już się rozwiązanie pojawiło na lekcji informatyki, metodą zaprezentowaną w podanej przeze mnie książce, nie miałem jednak okazji zrozumienia tego algorytmu bo kompy siadły :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1