Studoši

[obrisani korisnik] Da, ocigledno je da se moze iscitati i udaljenost nekog vrha do ostalih vrhova, ali ne znam kak onda razlikovati kad koristiti Dijkstru, a kad BF ako u zadatku ne piše. Osim ako se vidi da ima negativnih bridova pa je jasno.

niknik Jedini razlog zas bi koristio BF je ako ima negativnih bridova, to je cijela poanta BF-a. Mislim ak u zadatku ne piše “najefikasnijim algoritmom” onda možeš odabrat BF al ne znam zas bi to radio…

Da li u trgovačkom putniku prilikom euleriziranja uvijek poduplavamo samo bridove ili?

Jesam ja lud ili u ovom grafu nema hamiltonovog ciklusa? (ZR2019)

Postoji li negdje bolje definiran nacin provedbe Bondy-Chvatal teorema? Kada pokusam primijeniti onaj algoritam iz prezentacije na zadatak iz auditornih vjezbi zavrsim s nepovezanim grafom, a postupak iz pdf-a (auditorne) ne razumijem bas

kerovac Ne znam da negdje postoji definirano al ovako sam ga ja shvatila:

1) Izrada zatvarača grafa
Prvo moraš napraviti zatvarač grafa. U auditornima kaže da se prvo dodaju unutarnji bridovi, a zatim vanjski ako je to moguće. No to se ne može raditi bilo kojim redoslijedom (u smislu, ne možeš samo doći i random povezivati npr. čvor A s F ili D jer su to unutarnji bridovi). Zapravo tražiš 2 vrha koja nisu susjedna (tj nisu spojeni bridom) a da zbroj njihovih stupnjeva bude barem jednak broju vrhova (u ovom slučaju 7). Ako pogledaš svi vrhovi imaju stupnjeve 2 (A, E) ili 3 (B, D, F, G) i njihov zbroj nikad neće biti jednak 7 (2+2 = 4, 2+3 = 5, 3+3 = 6). Osim C. C ima stupanj 4 i kad ga se zbraja s ovima koji imaju 3, to daje 7 (npr. deg© + deg(F) = 4+3 = 7). Super, našli smo koje čvorove bi mogli uzeti u obzir za dodavanje novog brida. Sad se vraćamo na ono “ne smiju biti susjedi”. Od ovih ponuđenih (B, D, F, G) C nije spojen jedino s G, dakle to nam je jedina opcije za dodavanje bridova. Dodamo brid cg i označimo ga brojem 1 jer je prvi dodan.
Nakon toga , gledamo dalje situaciju. Sad C ima stupanj 5, a njegov jedini ne-susjed je E sa stupnjem 2, dakle u zbroju je 7, možemo i njih spojiti i označiti taj brid brojem 2.
I tako se ide dalje ovisno o tome kako se situacija sa stupnjevima mijenja. Ako u nekom trenutku imaš više opcija koji brid možeš dodati, uvijek prije dodaj unutarnji a za kraj ostavi vanjske.

2) Odabir Hamiltonovog ciklusa
Uzmeš neki Hamiltonov ciklus, ja sam krenula od ovog vanjskog prstena.

3) Izgradnja Hamitonovog ciklusa iz početnog grafa
Cilj je što prije riješiti se ovih dodanih bridova. Zato se kao prvi uv brid uzima EF (ima prioritet 11). Zatim ideš dalje po ciklusu i biraš svoj pq brid. Nebitno je li E=u, a F=v ili obratno, samo kod biranja p i q moraš biti konzistentan (dakle ako si išao u smjeru kazaljke na satu pa je E=v, a F=u, onda obavezno ideš dalje u smjeru kazaljke na satu pa je npr. za odabrani brid AG, A=p i G=q). Ja sam išla u suprotnom smjeru, odabrala brid AG jer mi je to bio prvi brid na koji sam naišla a da je dodan kao dio zatvarača. Mogla sam odabrati i neki drugi brid (npr. AB), isto bi bilo dobro, ali evo odlučila sam se za ovaj. Mogla sam odabrat i neki koji nije naknadno dodan u zatvaraču, ali cilj nam je što prije riješiti se dodanih bridova (jer tražimo ciklus u originalnom grafu). Budući da se spajaju p i u te q i v, dodala sam bridove EG i AF (oba su manjeg prioriteta!) te izbrisala EF i AG. Nakon toga ide iduća iteracija u kojoj sam odabrala AB kao uv (brid s najvećim prioritetom) i EG (sljedeći brid po ciklusu koji je naknadno dodan u zatvaraču).

U 5. koraku kad je samo 1 brid naknadno dodan, njega se odabere kao uv, dakle A=u, F=v. Nakon toga gledaš dalje po ciklusu. Sljedeći brid je FG - njega ne možemo odabrati jer pq ne smije imati zajedničke vrhove s uv (a imao bi F).
Dakle gledamo dalje, sljedeća mogućnost je GB - njega bi teoretski mogli odabrati jer ne dijeli vrhove s AF, aali ima jedan problem. Ako GB odaberemo kao pq, onda će G=p a B=q, što zapravo znači da bi trebali spojiti A i G te B i F. No, ako se vratimo par koraka unazad, vidit ćemo da smo brid AG već maknuli + ima veći prioritet (9), nego AF (8). Čitaj: nema smisla to dodavati i vratit se u krug (nez ni jel bi smjeli zbog prioriteta).
Sljedeća mogućnost je BC, ali to je ista priča kao s AG, makli smo brid AB i taj brid je imao prioritet 10, dakle ćorak, ni to nije dobra opcija.
Sljedeći na redu je brid CD i s njim nemamo problema kao s ovim prethodnima: bridove CA i DF nismo još dodavali (+ DF ima prioritet 6, što je manje od 8).
Mislim da su ovim načinom razmišljanja došli do toga da u tom koraku odaberu baš CD brid kao pq.

Dakle kad tako ostane samo 1 brid koji je naknadno dodan, za ovaj sljedeći je bitno pripaziti da:

• ne dijeli vrhove s uv bridom i
• da bridove koje bi trebali dodati nisu već micani (tj. da nemaju veći prioritet od našeg uv brida)

Dalje se samo nastavlja s algoritmom.

Evo nadam se da je pomoglo, malo mi je teško natipkati objašnjenje. 😅

indythedog Piše najučinkovitijim, tak da je to Dijkstra, al ak oces za vijezbu rijesit BF-om, najlakse je da pretvoris u usmjereni tako da poduplaš sve bridove (odnosno napraviš ovo kaj si reko)

Jel mozemo svojim nekim postupkom rjesavat zadatke il moramo na nacin na koji su rjesavali na auditornim ?

𝐓𝐇𝐄 𝐒𝐄𝐂𝐑𝐄𝐓 - 𝐂𝐋𝐔𝐁 Na ZI-u 2018. je pisalo ovo:

Također, čak i da radiš svojim postupkom, on mora davat identične međurezultate kao i njihov jer su tak na MI-u provjeravali točnost međukoraka

kako se ovaj radi, spada li taj zadatak u gradivo? mislila sam da je to problem kineskog postara no neda se tako rijesiti?

*** zasto se ne da rjesiti? Sva 4 vrha su neparnog stupnja, napravis klasicni postupak i put je duljine 14. Jedino me ova strelica zbunjuje, mislim da to samo označava početak puta iz vrha 1, pa sam ignorirao. Ako je graf “miješani”, pa je to stvarno usmjereni brid, onda se ne može rješavati na ovaj način pa ne ulazi u naš ispit, valjda.

Jesam ja nešto fulao ili nema auditornih za dijkstraMST?

U videu 2-MST je ubacio i dijakstra jer su jako slicni
Auditorne 2.8 - TSP (2-MST heuristika).mov

Rene ahaa hvala, ma bunila me ta strelica mislila sam da je kao ulica jednosmjerna

jel se ne uzima u knapsacku vrijednost u donjem desnom kutu? zašto se tu uzimaju A,B i C predmeti? ja bi u ovom primjeru recimo uzeo E prvo (tak sam skuzio po auditornim)

NISAM ASISTENT Krivo je rješen zadatak, na dosta mjesta tablica nije ispravna. Evo točnog rješenja:

moze neko pojasnit logiku iza CPP i TSP zadataka, odnosno koji zadatak je za koji algoritam ako nije eksplicitno zadano u zadatku? zbunile su me ove auditorne i ovaj zadatak gore

u auditornim je za CPP rjesavo zadatak di moraju trazit macku i pitanje je bilo koji je najefikasniji put po susjedstvu, pocevsi iz C i da se na kraju vrate u C
za TSP je rjesavo zadatak di trgovac treba najefikasnijim putem obic sve klijente, pocevsi iz A i da se na kraju vrati u A

sad ne znam jesam ja glup al meni to zvuci ko isti kurac, zas je jedno TSP a drugo CPP

angello2 Tsp ti je obilazak svih vrhova, a cpp je obilazak svih bridova.

angello2 jer kad trazis macku zelis proci sve ulice, a ne samo “kuce” na pocetku ulica pa trazis Eulerov ciklus -> kineski postar
Trgovac zeli obici sve klijente, znaci bitno je samo da ih sve posjeti a ne da obide sve puteve izmedu njih, trazis Hamiltonov ciklus -> traveling salesman

jel nasao tko mozda na internetu 0-1 knapsack fptas i bondy chvatal solver/visualization? sve ostale sam nasla pa si provjeram postupak, jedino ti kao da su crni pačići no where to be seen

reygrep mislim da to ni nema smisla tražiti, tražio sam dugo vremena i jedino što sam o Bondy-Chvatalu pronašao je neki mali postupak u Drozdekovoj knjizi. Ostalo što bih pronašao su teorijska razmatranja, a nigdje nikakvi postupci i/ili solveri