Studoši

Prof je na auditornima spojio direktno. To je onda krivo ili?

DaL jesi siguran? mislim ako ih direktno spojis koja ti je tezina tog brida onda? nema smisla to

DaL

whatTheHel
Mislim da je svejedno jer ti je tak svejedno dodaš li između 2 čvora 2 brida preko nekog drugog čvora i ti bridovi onda budu težina npr 2 i 3 respectively, ili ih direktno povežeš bridom duljine 5.
Kolko se ja sjećam prof je 2 čvora spojio direktno a težina je bila zbroj težina bridova koji su na najkraćem putu između ta 2 čvora

DaL Nije li irelevantno spajamo li direktno ili ne? Ako spajamo direktno, samo bridu dodamo weight kao sumu intermediate bridova, inace samo poduplamo bridove preko intermediate.

Ako idemo preko intermediate dodajemo mu 2 brida, sto ne mijenja situaciju. Put ce mozda bit drugaciji, duljina se ne mijenja, al ionako put je manje bitan podatak jer ih ima vise. I da spajamo direktno ili ne, opet ce postojati put.

Takoder, odgovor na pitanje hoce li najkraci put ostati isti odgovor je ne, pogledaj u prezentacijama Transformacija tezina grafova, ili tako nesto. Bas su objasnili da apdejtanje tezina se ne moze provesti tako da dodas neki broj svim bridovima jer se mijenja nakrace rjesenje.

Kad smo vec kod tog, priznaju li rjesenje za kineskog postara ako odokativno vidimo najkraci put izmedu neparnih nodeova koje spajamo? Ili moramo provest Djikstru?

DaL

whatTheHel

temari

DaL

johndoe

Brčić says : “morate poduplati postojeće bridove jer treba fleuryevim onda proći tim ulicama”

M̵̧̩͑̀͝î̶͍̉ć̴̝̾́̀o̶̺̟̣͂̽ sto nije odgovor ne i ne?

Npr dodamo svima 7. Gledamo put izmedu F i C, prije je bio 3+2, no sada imamo 8+7<3+7+2+7

zaba Aha, imaš pravo, glup sam, uvijek razmišljam mijenja li se što kad se doda 1, ali pitanje je bilo koji pozitivan broj

whatTheHel

temari Tako je…za tezinu je stavio najkracu izmedu njih, a koju je dobio u prethodnom koraku

saitama 77?

johndoe Da se nadovezem, mozda da u zadatku napisu nesto u stilu “Mile iz Hrvatskih cesta se mora vratiti kroz iste ulice kroz koje je prosao, nema precica” u tom slucaju spajajte preko posrednih cvorova

ZI 2018/2019
Zasto smo se zaustavili ovdje, sto nemamo jos ovaj -7 koji ne bi trebao bit negativan?

Pitanje iz ispita: “Dijkstrin algoritam pronalazi najkraći put samo između polaznog vrha i točno jednog zadanog vrha u grafu.” True / False

Odgovor: "The algorithm exists in many variants. Dijkstra’s original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree."

Znaci tocan odgovor je “Ovisi”.

in1 Fleuryem mozemo proci i da ne duplamo nego da spojimo direktno, no dobro ajde da nebi Brko zajebavao na uvidima 😃

Kakav je ovo odgovor na d)? Pretpostavljam da je to trebao bit jedan od najkraćih mogućih obilazaka. Kad obilazim napisanim redoslijedom (i brišem obiđene bridove) naravno da mi ispadne da ne mogu proć kad drugi put dođe do E-H.
Jel može ko odgovorit kako bi išli ti najkraći obilasci? Jer recimo meni ostane EB neobiđen haha. Ostala sam bez ideja za taj obilazak. A radim ko ovi na yt Fleuryev alg.

member D-A-E-A-B-C-E-F-C-F-I-H-F-H-E-D-G-H-G-D
Jedino ne znam sta znaci da ti ostane EB neobiđen, nema tog brida

Koje je gradivo ovaj zadatak? (5. zadatak, ZI 2016.)

Bobicki Knapsack problem (čini mi se)

Bobicki knapsack s particijama

mijenja ti samo marginalno način rješavanja (u smislu da imaš 0-1 knapsack, ali 0-1 i za grupe), no na ispitu ne trebaš ništa previše filozofirat i pisati, samo na drukčiji način gledaš kad smiješ uzeti neki predmet.

Ako hoćeš poopćenje na normalni knapsack, onda možeš cijeni dodati trojku varijabli (znači da imaš (cijena, grupa 1, grupa, 2, grupa 3)), pa tretiraš kao da objekti iz grupe 1 npr. koštaju (cijena, 1, 0, 0). I onda na početku staviš da ti je budžet (kapacitet, 1, 1, 1), i riješavaš analogno algoritmu s predavanja. Ovo je zgodno kad imaš kompliciranije uvjete, npr. mogu reći da iz parnih grupa možeš uzeti 2 itema, a iz neparnih 1, i onda bi si mogao zadati početan budžet kao (kapacitet, 1, 2, 1).

Chet I meni izgleda kao knapsack, ali ove grupe me zbunjuju.

Bobicki Mislim da ti je to samo fora u očitavanju riješenja, kao ak uzmeš najbolje koje sadržava jedno od ovih iz 2. grupe, postupak stvaranja tablice je isti

Bobicki s obzirom da samo grupa 2 sadrži 2 jela, možda treba dva puta knapsack riješiti, jedno rješenje sa sladoledom u grupi 2, druga s pizzom pa onda uzeti bolje od ta dva