Studoši

je li samo do mene ili je prvi sat auditornih totalno nekoherentan u smislu objašnjavanja?
što više gledam, čini mi se da manje znam

Chet meni se cini da cijeli ovaj predmet nema smisla ucit preko predavanja, video-predavanja, auditornih ili bilo kojih “sluzbenih” materijala

Jel ima negdje dobro objasnjenje simplexa?
EDIT: Zapravo ono sto me muci je odabir pivot elementa

Ellie U retku fje cilja (zadnji do ove godine ili prvi u auditornima, od ove godine, ne kužin zašto ta promjena) nađeš najmanji negativni broj. Onda ćeš u stupcu u kojem je taj broj izabrat pivot element. To radiš pomoću stupca kojeg je u auditornima označia s RHS (zadnji). Te ćeš elemente podijelit s elem. iz stupca iz kojeg biraš pivot element. Ne moraš dijelit s nulama haha. Pogledaš koji je manji, a da je pozitivan. To je redak u kojem je pivot elem. Stupac mu već znaš…

Uostalom, imaš na slajdovima…

zimski rok 2019/20

ako neko moze rjesit / objasnit postupak i rjesenje koje bi se dobilo
ja san prvo isa sa WFI dobit najkrace udaljenosti svi-svi
iz toga mi se nudilo puno kombinacija parova i nakon trial and error dosa do dva brida koja su usmjerena , sto mi je pretvorilo sve ostale bridove u usmjerene …jer valjda triba vridit indeg(v) == outdeg(v)?
ukupni napor mi je ispa 14
a pustolovina koja krece iz 1 : 1 2 4 2 3 1 3 4 1
pa me zanima jel bi to bilo validno rjesavanje tog zadatka 💀

moji_prsti_prsti_klize_po_njoj ja sam spojio 1-2 (tezina -2, smjer 2 u 1 da vrijedi in==out) i 3-4 (tezina 3)… napor 14 😃

member
bas me kod ovoga buni sto kad na slajdu bira minimum između 3/2 i 4/1 (odnosno 1.5 i 4) izabere 4/1

Najbolji nacin za nauciti backtracking sa primjerima? ovi AC3 i PC2

Ellie a koje ti to slajdove gledaš?

Izabere se 3/2, a to je na ovim slajdovima indeks (1, 1), odnosno element 2
NAPOMENA: indeksi za retke počinju od nula, a za stupce od jedan

Chet

Uh da, imaš pravo, i hvala na objašnjenju!

Zbunila me i indeksacija i činjenica da je u tom prvom stupcu u retku 1 broj 2, a u retku 2 broj 1, vise nisam bila sigurna na što misli

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).

Ducius Ovo me toliko zbunjuje. U prezi piše da ako imamo negativne koeficijente s desne strane, oni se moraju pomnožit s -1 i postat pozitivni i onda valjda po tome moramo radit dvofazni jer ne smijemo imati -7 na desnoj strani. Ali u tutorialu je normalno riješeno s negativnim koeficijentima i to se rješenje lijepo poklapa sa uvjetima. Wtf.
Da usporedim, probala sam riješiti taj zadatak iz tutoriala sa jednofaznim i dvofaznim simpleksom.
S tim da sam dvofazni pratila kak je prof rješavao na auditornima i moguće je da sam negdje pogriješila. Uglavnom, sa dvofaznim dobijem manju vrijednost, a sa jednofaznim veću. Wtf again.

temari

Na tutorialu se radi neka fora gdje se uvijek prebaci u standardnu maksimiziaciju, navodno s tim postupkom mozes sve rijesit i ne moras razmisljati trebas li jednofazni ili dvofazni

Prednost je sto izbjegnes one umjetne varijable pa imas manje posla

Murin Mislim, ja sam na isti način postavila kao u tutorialu pri rješavanju jednofaznog, samo sam ignorirala ono da desna strana ne smije bit negativna. Pretvorba u std formu je ista kao na prezama osim te -7.

Edit: A za onaj zadatak s auditornih dobivam isti rez za jednofazni i dvofazni, lol.

U kojim auditornima je rijesen neki csp zadatak? Ako je

behappy98 mislim da je u trećim

je li moramo znat pretvaranje u graf s nenegativnim bridovima

pronalazak HCiklusa uz pomoć Bondy-Chvatalvog teorema
Ima neki video / tutorijal ?

adidas
Dakle : deg(n) je stupanj vrha - broj priležećih bridova.
k = 1;

1. korak - pospojiš sve parove vrhova za koje vrijedi deg(v1)+deg(v2) >= |V| (broj vrhova). Svaki na skici označiš isprekidano i zapišeš pored njega broj k i zatim uvećaš k za 1.
2. kad si sve pospojio i dobio “prošireni” graf, skica b), nađeš neki ciklus, vjerojatno će ti ić onak “u krug” (ovo zeleno sa slajdova, iz b) su izabrali zeleno i u c) su izdvojili samo taj dio.
3. Nakon toga uzmeš neki od ISPREKIDANIH vrhova (sa većim brojem) iz svojeg ciklusa i zamijeniš ga sa neka druga dva brida (može biti 2 isprekidana, dva puna ili 1-1) iz onog “proširenog” grafa tako da i dalje postoji ciklus, ali broj na novim isprekidanim, ako postoje mora biti MANJI od ovog kojeg si sada maknuo. Ako gledaš ovaj slajd gore, zamisli da su prvo (sa c) na d)) maknuli isprekidani brid sa brojem 6. i umjesto njega su uzeli dva nova brida - originalni brid af i isprekidani brid sa težinom 5 (5<6). sad automatski maknu i ovaj brid ba pošto ova dva nova brida ih spajaju natrag u ciklus. Nije bitno ako u postupku mičeš i originalne bridove i dodaješ iscrtkane, bitan je dio di uzmeš iscrtkani i zamijeniš ga sa manjim i tako ćeš doć do originalnog ciklusa.
4. profit

Serial Number Q5U4EX7YY2E9N Zasto su oni u prvom koraku isprekidano spojili b i d kad za njih ne vrijedi deg(b) + deg(d) >= |V| ? deg(b) = 2, deg(d) = 3, |V| = 6

edit: aha nevermind, i ovi isprekidani bridovi se racunaju

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.

Emma63194
Tako se rješavaš ovih fejk iscrtkanih bridova i polako imaš sve više pravih dok ne dođeš do krajnjeg ciklusa.
Poanta je nać ciklus xD ali mi radimo na manjim grafovima di je intuitivno rješenje iz početne skice, ali se ovo primjenjuje i na veće grafove ja mislim. Pa kao da NauČimO
A kaj se tiče ovog "Početni odabrani Hamiltonov ciklus mora sadržavati barem jedan brid iz maksimalno proširenog grafa G’”, ako proširiš maksimalno graf sa dodatnim bridovima, i i dalje ne možeš naći ciklus, onda ne postoji. Tako da sa proširenjem možeš dobit ciklus ako postoji u originalnom grafu.

jel u kineskom poštaru onda treba nekim posebnim algoritmom tražit min udaljenosti između vrhova neparnog stupnja ili se može napamet?

MJ3 mislim da nema razloga da se ne bi radilo napamet. Isto tako su i oni na prezentaciji samo stavili tablicu najkraćih udaljenosti nakon “provedenog algoritma”. Izgubio bi više vremena na samo WFI nego na cijeli zadatak ovako.