[NAISP] Gradivo

Rene

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

reygrep

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

[obrisani korisnik]

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

huhu

Jel zna netko negdje gdje ima zadataka za vjezbu s rjesenjima?

[obrisani korisnik]

huhu ima par rjesenih primjera na predavanjima na starom predmetu, nazalost ne za svo gradivo

postoji i na studosi githubu ali se ne bih bas pouzdao u ta rjesenja, bolje samostalno generirati primjere i rjesavati uz pomoc nekog online solvera

ZalutaliStudent

Sicsile
Uglavnom isto kao 0.1 približni algoritam, razlika je što stvari 4 i 5 imaju veću v’ vrijednost pa je i tablica malo drukčija, ali na kraju se dobije isti rezultat.
Naravno sve ovo stoji ako sam ja to dobro riješio, ostavljam mogućnost da sam u krivu.

VelikiMarko

ZalutaliStudent Kako si ti dobio za polje u redu 7, stupcu 7 7? Zar ne bi u tom polju bila default vrijednost jer kad smo gledali koji kapacitet je manji, uspoređuje se 9 (default vrijednost) i 5+4 (4 uzeto s polja koja je u retku 6-5=1 i stupca 3), što je opet 9. Jer ja kad sam to rješavao dobio sam da uzmemo samo stvar 5.

vrdrli23

Jel netko na ispitima od prošlih godina primjetio da u zadacima sa WFI, Bellman-Ford(i Dijkstra potencijalno) su grafovi neusmjereni? Kako se postupa u tim slučajevima? Što sam vidio po primjerima na auditornima, internetu i prezama, ti algoritmi se provode na usmjerenima, kako onda uopće postaviti kad smo u neusmjerenom, jel proizvoljno mi dodajemo smjerove ili što?

AnamarijaM

vrdrli23 Sigurno ne dodaješ proizvoljno smjerove kad se ocjenjuje u edgaru. Dijkstra se normalno izvodi nad neusmjerenim grafom (imaš videa na youtubeu koliko hoćeš, radilo se na MAT3R ako ima u materijalima). U WFI samo upisuješ istu težinu brida u matricu i za A->B i B->A, pa samo imaš manje posla za računat. Za Bellman-Ford nisam vidjela nigdje na ispitima da je s neusmjerenim grafom, on se primarno koristi za usmjerene grafove. Kaže internet da bi se mogao koristiti tako da kad pišeš bridove zapišeš svaki duplo, AB i BA, ali nisam isprobavala.

ZalutaliStudent

VelikiMarko Najiskrenije nisam ništa skužio što me pitaš.
Stupac 7 nemam pa ne kužim na kaj se referiraš. Možeš možda slikati svoj postupak, ili na papiru skicirati šta ti nije jasno pa da zajedno probamo doć do točnog rješenja.

VelikiMarko

ZalutaliStudent Pardon, krivo napisao broj stupca, mislio sam na stupac 4. Evo moje tablice, moguce je da sam i ja pogriješio negdje u izračunu.

ZalutaliStudent

VelikiMarko A okej kužim… Dakle prva tri stupca (za stvari 1, 2 i 3 su nam iste i mislim da su točne), stupac za stvar 4 se popunjava na sljedeći način:

stvar 4 ima vrijednost 5, veličina je 5, dakle u redak pod broj 5 pišemo veličina 5 (to si dobro napravio), i onda idu strelice iz stupca 3, prvo zbrojimo vrijednost iz stupca 3, retka 1 koja iznosi 4, plus ovih 5 to je 9, dakle ništa ne upisujemo, onda se spuštamo dalje, imamo stupac 3, redak 2 -> vrijednost 2, nju zbrojimo s naših 5 i to je broj 7 koji upisujem u stupac 4, redak 7. Ta vrijednost zapravo govori da veličina 7 (stvar 3 plus stvar 4) daje vrijednost 7.

niknik

ZalutaliStudent Ni to nije tocno sto je stavio VelikiMarko, ovako bi to trebalo ici kako je na slici, 99% sam siguran da je to tocno.

Tonii

niknik Mislim da ti nije dobro zašto uzimaš vrijednost u 6. retku koji predstavlja vrijednost 6 sa kapacitetom 7 kad imaš ispod njega 7. redak cija je vrijednost 7 sa istim kapacitetom(možda sam u krivu ali tako sam ja svoje riješavao), kao idem uvijek u najdonji redak i iz njega uzimam najdesniju vrijednost, a ne iz najdesnije vrijednosti uzimam zadnji redak

Tonii

Zulul Ok da se nadovezem moje objasnjenje je kretenizam, ali krivo ti je jer vidiš da ti skroz desni stupac označava {1,2,3,4,5}, a ti nisi samo stavio u zadnji stupac v’ = 7 iz prethodnog stupca tako da će ti on biti u kutu tablice

niknik

Zulul Pravilo je da se ide u zadnji stupac i iz njega se gleda zadnji redak koji nije defaultne vrijednosti….jer ako bi se islo u zadnji redak prvo onda se u ovom slucaju uopce nebi ispitivala stvar 5 sto je krivo.

niknik

Zulul Ispavka…u stupcu 5 i retku 7 ipak mora ici vrijednost 7 jer se gleda MIN(7, 0+7) i to je 7 i onda se ne uzima stvar 5 nego 4 i 3.

Tonii

Jel može netko ispraviti ako da li sam dobro skužio primjenu određenih algoritama.
Udaljenost među svim vrhovima- WFI, udaljenost određenog vrha do svih vrhova/1 vrha -dijksta ili BF?

AnamarijaM

Zulul da, osim ako postoji negativni ciklus, onda ne mozes koristiti BF nego opet WFI

Tonii

niknik Kuzim to sam debilno razmisljao samo sam pokusao sebi objasniti zasto bi zaokruzio vrijednost 6 kad je moguca vrijednost 7

ZalutaliStudent

niknik jel to znaci da je moje rješenje dobro?

[obrisani korisnik]

jel kod 2-MST heuristike pri dodavanju bridova određene težine (npr. 2) dodajemo sve te bridove, čak i kada je npr. jedan od njih više dovoljan da svaki vrh ima brid?

anon00

[obrisani korisnik] 2-MST dodajes redom bridove s najmanjom cijenom, ali ako naiđeš na neki koji bi napravio ciklus njega preskocis. I tako dok ne povezes sve cvorove (bez ciklusa)

« Prethodna stranica