Studoši

tito samo pomnožiš s -1

member
Treba li onda raditi dvofazni simpleks?
Posto imamo >=?

Zbog čega se u 1. iteraciji uzeo 3. redak za pivot, a ne prvi?

Atem
mislim da je mogao i jedan i drugi

Atem Da se nadovežem na kolegu, specifično zašto je ovdje zgodnije odabrati 3. redak je zato što ćeš dozvoljenim operacijama s njime napraviti manje “nereda”. Jer npr. ak bi s 1. retkom išao poništavati 2. i 3. redak, stvorit ćeš više ne-nul vrijednosti u njima nego obrnuto. Ako 3. retkom ideš poništavati 1. i 2., onda ćeš njima samo jednu nul vrijednost pretvoriti u ne-nul, a bolje ti je imati što više 0 (tj. što manje ne-nul vrijednosti) da ti je lakše računati.

Atem koji je ovo materijal?

Chet
Ne dopušta mi da pošaljem taj file, ali našao sam ga na Studoši materijalima za NASP. Zove se “NAISP_2019-20_tutorial_zadaci”.
Piše zadaci za godinu 2019/2020, ali ima zadataka sa mnogo godina

tito
Je li tko rjesio ovaj zadatak?
Moze li postat svoje rjesenje ili barem rec koj je rez?

nakon eulerizacije, kad trazimo ciklus u grafu, tj. da dodjemo nazad u pocetku tocku, a da smo svakim bridom prosli samo jednom, to se moze napraviti na vise nacina, zar ne? odnosno, zadatak ima vise od jednog tocnog rjesenja?

Adri ako je rezultantni graf takav da ima više eulerovih puteva, yes, onda ima i više načina kako se taj put ostvaruje (izvan trivijalnih početaka u različitoj točki)

Koji je najbolji video koji objašnjava union find?

Zna li netko što očekuju od nas u b zadatku. Nije mi jasno ovo “crtež nije dovoljan”. Zar to nije doslovno povlacanje crte preko bridova?

stoper5 je doslovno povlacenje crte samo jos napisi koji su to bridovi i njihove tezine

stoper5

Je li minimalni presjek skup bridova od s do t koji sve zbrojeno ima najmanju tezinu ili?

stoper5 Kako se uopce rjesava ovaj zadatak? Po kojem algoritmu se to rješava?

stoper5
ima netko rješenje ovog?

Murin da

Kiflica Ford Fulkerson (na yt upisi max flow min cut)

Murin 4 dana kasno ali ja to sebi ponavljam pa tu pisem… minimalni presjek (najmanji zbroj tezina) ujedno daje i maksimalni flow kroz mrezu, jer ocito ako imas npr. spojene cijevi od 3 L, 5 L i 2 L, kolko god vode utrpali unutra, maksimalno moze proci 2 L. Kad pogledas sve sto izlazi iz pocetnog cvora, to je upper bound koliki ti max flow moze biti, a s min cutom ga zapravo smanjujes dok nedobijes najmanji moguci, to je zapravo najveci flow.

Isto tako, kad presjecas, s i t uvijek moraju biti odvojeni (jedan u jednom skupu, drugi u drugom) i pazi da racunas tezine samo onih bridova koji idu iz “lijevog” (s skup) skupa u “desni” (t skup)

ZI 2019./2020.
Zna li tko kako se ovakav zadatak rješava?

Cvija Pa moraš provesti algoritam, a kako se to konkretno radi, pa nacrtaš graf iz tablice, i onda dodaješ bridove dok ne napraviš zatvarač (na 13.1 prezentaciji 21. slajd). I onda u tom novom grafu nađeš hamiltonov ciklus i napraviš ispis iz a

S tim da ako ti je graf već hamiltonski i nije zatvarač, izgleda da moraš uzeti neki hamiltonski ciklus koji ne opisuje ujedno i originalni graf (znači neki shitniji hamiltonski ciklus XD), to bi se dalo zaključiti po ovoj zadnjoj rečenici.

Cvija imas dobar tutorial na materijalima za taj zadatak, ali evo ti moje rješenje, mozda ti pomogne

zaba Koja je logika za uklanjanje ovih bridova u 3. koraku, nije mi baš jasno. I što je opće poanta tog zadatka? Ovo “Početni odabrani Hamiltonov ciklus mora sadržavati barem jedan brid iz maksimalno proširenog grafa G’” mi je malo zbunjujuće.

Imate li neke dobre tutoriale za ove zadatke:

• pronalazak najvećeg protoka
• kineski poštar
• disjoint-set
• trgovački putnik
• pronalazak Eulerovog ciklusa (pretpostavljam Fleury?)
• pronalazak Hamiltonovog ciklusa (pretpostavljam Bondy-Chvatal?)

Bobicki
Za Fleuryjev algoritam sam pronašao ovaj tutorial koji mi je bio prihvatljiv

Za Bondy-Chvatal algoritam je kolega dao hint da postoji tutorial na materijalima… I ja ga planiram još detaljnije pogledati
https://github.com/studosi-fer/NAISP/blob/master/razno/tutoriali/NAISP_tutorial_bondy-chvatal.docx

Za Kineskog poštara sam ovo pogledao

Za trgovačkog putnika, ova 2-mst heuristika, video mi se čini okej i do osme minute objašnjava ono što je potrebno

Protok još tražim dodatna objašnjenja, ali ovaj video sam već pogledao i intuicija mi je jasnija

Bobicki Što se tiče Dijoint-set, misliš na Union find algoritam?
To je doslovno pratiš algoritam kako ide… Pseudokod algoritma imaš na 37 slajdu prezentacije 11_Grafovi2