Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Jos jedan zadatak

[es] :: C/C++ programiranje :: C/C++ za početnike :: Jos jedan zadatak

[ Pregleda: 2806 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Burgos
Nemanja Borić
Amazon Web Services
Berlin

Član broj: 12484
Poruke: 1947
*.smin.sezampro.yu.

Sajt: stackoverflow.com/users/1..


+480 Profil

icon Jos jedan zadatak09.03.2007. u 13:05 - pre 207 meseci
E, kolege, došlo vreme da i meni zatreba pomoć. Zadatak glasi ovako:

Citat:

Data je mapa grada koji se sastoji od M dvosvernih ulica na pravcu istok-zapad i N dvosmernih ulica na pravcu sever-jug (M, N <= 50). Svake dve ulice grada na mapi su ili paralelne ili se seku po tačno jednoj raskrsnici gde su nadmorske visine raskrsnica različite i unose se u matrici H(i, j) - štp predstavlja nadmorsku visinu raskrsnice u kojoj se seku i-ta ulica pravca istok-zapad i j-ta ulica pravca sever-jug. Deo bili koje ulice između svake dve susedne raskrsnice je duž. Za date dve raskrsnice A i B zadane koordinatama položaja ispitati da li postoji put ulicama tog grada kojim sse stiže iz A u B kretanjem nizbrdo (kretanjem od raskrsnice sa VEĆOM visinom ka susednoj raskrsnici sa MANJOM visinom).

Ukoliko postoji traženi put ispisati koordinate raskrsnica koje se prolaze uz zahtev da je broj tranzitnih raskrsnica što je moguće manji.


Ja sam rešenje tog zadatka osmislio ovako: matricu H ispuniti nekim velikim brojem koji ne može biti nadmorska visina (npr. MAXINT / 2). Zatim učitati nadmorske visine u matricu H i učitati početne i krajnje koordinate. Problem bi rešio backtrackingom i rekurzijom: iz krajnje tačke polazim u svako susedno polje koje sadrži manju vrednost, pa onda iz svakog susednog polja u svako susedno polje koje sadrži manju vrednost sve dok se ne dodje do krajnjeg. Ukoliko se ne može stići do krajnjeg polja neka vrednost koju bi funkcija vratila, a pokazivala bi broj koraka vratila bi -1, a ukoliko postoji putanja nizbrdo ta vrednost bi vratila broj koraka do zadatog polja i niz koordinata tranzitnih raskrsnica. Na kraju izabrao bih onu vrednost koja je najmanja i to bi bilo konačno rešenje.

Verujem da ovakav pristup ima mane i greške, pa vas pitam, postoji li jednostavnije rešenje tog problema ili da radim ovo.


 
Odgovor na temu

jovchica
Jovko Jacimovic
logisticar, Marbo Product
bgd

Član broj: 96573
Poruke: 4
195.252.119.*



Profil

icon Re: Jos jedan zadatak13.03.2007. u 08:12 - pre 207 meseci
Ovaj tvoj problem je malo vise komplikovan, ako iz svakog polja ides u drugo polje koje ima manju vrednost ti mozes imati maksimalno 2 ^n putanja, tj da proveris u krajnjem slucaju sve putanje izmedju svih cvorova na mrezi, a takvi zadaci su neresivi, mislim da u ovom zadatku mora da postoji jos neko ogranicenje. da bi on bio resiv. Zapravo taj zadatak bi mogao da se resi primenom genetickog programiranja ili nekom slicnom tehnikom ali mislim da to nije bio cilj.
J ovchica
 
Odgovor na temu

karas

Član broj: 5574
Poruke: 482
*.routotelecom.com.



+1 Profil

icon Re: Jos jedan zadatak14.03.2007. u 08:18 - pre 207 meseci
Meni ovo liči na problem dinamičkog programiranja, pokušao bih sa određivanjem hijerarhije problema i nalaženja optimalnog rešenja. Za svake dve raskrsnice treba pamtiti optimalno rastojanje i eventualno ga popraviti u sledećoj iteraciji. Tada broj rešenja podproblema ne bi rastao eksponencijalno.
Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

jovchica
Jovko Jacimovic
logisticar, Marbo Product
bgd

Član broj: 96573
Poruke: 4
195.252.119.*



Profil

icon Re: Jos jedan zadatak14.03.2007. u 12:20 - pre 207 meseci
Bilo bi fenomenalno kada vi to bio zadatak dinamickog programiranja, za to postoji algoritam, i resava se relativno jednostavno, ali sta ako on krene da iz jedne raskrsnice ( od izvora tri putica posto ne moze da se vrati nazad), odabere skleci cvor nebitno da li po rastojanju ili po nadmorskoj visini Dodje u narecenu raskrsnicu a sve ostale imaju vecu nadmorsku visinu. Zaglavio se u lokalnom minimumu i sta dalje (sve klasicne gradijentne tehnike ze zaglavljuju u lokalnom minimumu i ne mogu da dostignu globalni koji nama treba). Naravno da je njemu lako da se vrati jedan cvor unazad, ali sta ako ode 5-6 koraka i nema dalje. Mislim da resenje nije uopste jednostavno ili zadatak nije dobro postavljen.
J ovchica
 
Odgovor na temu

karas

Član broj: 5574
Poruke: 482
*.routotelecom.com.



+1 Profil

icon Re: Jos jedan zadatak14.03.2007. u 13:06 - pre 207 meseci
Ne vidim zašto ne bi mogao da se vrati i 5-6 koraka unazad jer on mora da pamti sve međurezultate kako bi našao optimalno rešenje. Ako naiđe na veću nadmorsku visinu, taj put će svakako označiti kao nemoguć, tako da u narednim traženjima neće ponovo ići tuda. Optimalan put svakako sadrži i optimalne podputeve inače bi on sam mogao da se poboljša. Zato mi se čini da treba pokušati sa dinamičkim programiranjem. Parametar za podprobleme bi osim dužine puta možda bila i nadmorska visina raskrsnica. Ne znam, možda i nije moguće takvo rešenje, ovako na prvi pogled bih pokušao tako nešto.
Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

karas

Član broj: 5574
Poruke: 482
*.routotelecom.com.



+1 Profil

icon Re: Jos jedan zadatak14.03.2007. u 14:04 - pre 207 meseci
Ako su sve visine raskrsnica različite, onda bi se iz mape mogao izdvojiti usmereni graf na sledeći način: polazni čvor bi bio grad iz kojeg se polazi a dolazni čvor bi bio grad u koji se dolazi (source i sink grafa). Ivice grafa bi bile one ulice kod kojih je početni čvor sa većom nadmorskom visinom od krajnjeg čvora. Ovakav usmereni graf ne bi imao ciklusa jer ne možemo uvek ići nizbrdo i stići u polazni grad. Čini mi se da bi onda traženje najkraćeg puta bilo znatno olakšano.

Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

jovchica
Jovko Jacimovic
logisticar, Marbo Product
bgd

Član broj: 96573
Poruke: 4
*.dynamic.sbb.co.yu.



Profil

icon Re: Jos jedan zadatak14.03.2007. u 22:28 - pre 207 meseci
Ajmo polako, npr probaj da resis zadatak za dimenzije 5 x 5 cvorova u mrezi, pretpostavimo da od cvora A koji je u gornjem desnom uglu do cvora B koji je u donjem levom uglu opadaju nadmorske visine cvorova ( ovo se ne kosi sa uslovima zadatka zapravo A se nalazi na vrhu brda a B u podnozju ) znaci samo sa dimenzijama 5x5 videces koliko resenja imas a i da ne mozes da uspostavis algoritam po kome ce da se odvija pretrazivanje prostora. Sto se tice grafa to je isti problem i dalje nije tu problem usmerenje vec je problem put kroz graf tj broj puteva kroz graf. Ali da se ne bi ubedjivali probaj da resis.
J ovchica
 
Odgovor na temu

karas

Član broj: 5574
Poruke: 482
*.routotelecom.com.



+1 Profil

icon Re: Jos jedan zadatak15.03.2007. u 08:38 - pre 207 meseci
Neka su čvorovi u grafu predstavljeni matricom X dimenzije 5 x 5. Neka je čvor A dat elementom x(1, 1) a čvor B elementom x(5, 5). Najgori slučaj je kada sve nadmorske visine od A do B opadaju i imamo ulicu izmedju svaka dva susedna grada; tada ima 40 ulica. Dakle, A je čvor iz koga se polazi (source) a B u koji se dolazi (sink). Čvorovi dati sa x(1, 2) i x(2, 1) su prvi "sloj" u grafu; x(1, 3), x(2, 2), x(3, 1) drugi; x(1, 4), x(2, 3), x(3, 2), x(4, 1) treći; itd. do sedmog sloja x(4, 5) i x(5, 4); na kraju je čvor B dat sa x(5, 5). Ako se ovako posmatra graf, onda se pretragom u širinu mogu naći svi putevi i videti koji je najkraći.
U opštem slučaju za n čvorova ima 2 * n * (n - 1) = O(n ^ 2) ulica i pretraga će trajati O(n ^ 2).

Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

Burgos
Nemanja Borić
Amazon Web Services
Berlin

Član broj: 12484
Poruke: 1947
*.smin.sezampro.yu.

Sajt: stackoverflow.com/users/1..


+480 Profil

icon Re: Jos jedan zadatak15.03.2007. u 15:11 - pre 207 meseci
A ja taman odustao :).

Salu, na stranu, hvala, evo sad cu da pogledam ovo. Inace, tekst je tacan, nema dodatnih uslova i zadatak potice iz knjige Milana Cabarkape "C Osnovi Programiranja".
 
Odgovor na temu

karas

Član broj: 5574
Poruke: 482
*.routotelecom.com.



+1 Profil

icon Re: Jos jedan zadatak16.03.2007. u 09:54 - pre 207 meseci
Rešenje sa uočavanjem usmerenog grafa i pretragom u širinu bi trebalo da prolazi, dok pristup preko dinamičkog programiranja izgleda da ne ide.
Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: Jos jedan zadatak

[ Pregleda: 2806 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.