Studoši

Može li netko slikati postupak 1. zadatka ZI 2020 sa simplexom? Pitam za prijatelja

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

Cvija Pošto ne mogu urediti, mislim da je ovdje došlo do zabune. Algoritam koji se koristi u zadacima je na 31 slajdu, to je onaj sa poljima, na 37 slajdu je sa stablima, možda sam tu pogriješio, ispričavam se na pogrešci.

saitama

Bobicki

member
Evo sad ću proći po algoritmu pa možda bude jasnije

Zadatak od kolege
member
Znači, na početku imamo ovakvo stanje
\begin{bmatrix}root && 1 && 2 && 3 && 4 && 5 && 6 \\ next && 1 && 2 && 3 && 4 && 5 && 6\\ length && 1 && 1 && 1 && 1 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Sad radimo Union(1, 2)
Po algoritmu, xs = root(x) = root(1) = 1
ys = root(y) = root(2) = 2

xs i ys nisu jednaki pa provjeravamo njihove duljine (lenght)
ys nema veću duljinu od xs (obje su 1) pa znači da radimo sljedeći set komandi
length[xs] += length[ys]
root[ys] = xs
svi u polju u kojem je korijen bio ys, za korijen im postavi xs
na kraju zamijeni sljedećeg od xs i sljedećeg od ys
Nakon tog seta operacija se dobije
\begin{bmatrix}root && 1 && 1 && 3 && 4 && 5 && 6 \\ next && 2 && 1 && 3 && 4 && 5 && 6\\ length && 2 && 1 && 1 && 1 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Onda ide Union(4, 3), isto sve
\begin{bmatrix}root && 1 && 1 && 4 && 4 && 5 && 6 \\ next && 2 && 1 && 4 && 3 && 5 && 6\\ length && 2 && 1 && 1 && 2 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Nakon Union(2, 3) [xs = 1, ys = 4]:
\begin{bmatrix}root && 1 && 1 && 1 && 1 && 5 && 6 \\ next && 3 && 1 && 4 && 2 && 5 && 6\\ length && 4 && 1 && 1 && 2 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Te na kraju nakon Union(1, 6)
\begin{bmatrix}root && 1 && 1 && 1 && 1 && 5 && 1 \\ next && 6 && 1 && 4 && 2 && 5 && 3\\ length && 5 && 1 && 1 && 2 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Nacrtat se može pomoću ove tablice

Jel samo meni ne radi zadnje predavanje, 1.sat od sredine? Ni treći sat

EDIT: Ma da, Brčić radi. Do Krleže je.

je li možda netko ima postupak uvježbavanje neurona na skupni način, već sam probao scrollat gore kako bi pronašao link na sliku gdje se upravo takav tip zadatka rješavao, ali link više ne radi.

ima netko provjeren ovaj zadatak, na materijalima je sve nesto kaoticno

[obrisani korisnik] Rješavao ga je Brčić na zadnjem predavanju (auditornima).

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

Kiflica Pogledaj protok u mrežama

Kiflica Ford-Fulkerson

Murin da

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

imaju li negdje objavljene snimke predavanja?

Ruleta na teamsu

ako se kao MST može dobit i a-b-c-e-d, s ukupnom težinom 6 kao i ovaj MST na slajdu, a iz njega dobijem hamiltonov ciklus a-b-c-e-d-a težine 8, što je manje od 10, kako znam odma koje stablo odabrat?

ZAD 4. ZI 14/15:
Imamo šest nezavisnih skupova s po jednim elementom. Elementi su prirodni brojevi od 1 do 6 i svi skupovi sadrže različite brojeve. Prikažite (skicirajte) rad Disjoint-Set strukture nad tim skupovima uslijed obavljanja sljedećih operacija: Union(1,2), Union(4,3), Union(2,3) i Union(1,6).

Jel rješenje:
1->2->4->3->6 , 5 (sam)
I da provjerim jel u tablici za čvor 4: root=1, next=3, length=2 (jer je prije bia root pa ostavim tu udaljenost ? tako je na prezi)

member Ne bi li trebalo biti:
1->6->3->4->2, 5 (sam)
Jer se kod union(2,3) krizaju skupovi 1->2 i 4->3….znaci uzima se prvi element iz 1->2 (1), pa cijeli drugi set 4->3 pocevsi od drugog elementa (3 pa 4), pa ostatak podskupa 1->2 (2)

Vrba I ja sam ovako dobio

member Za čvor 4 ti length ostane kakav je bio, da, ali ostale vrijednosti sam drugačije dobio

Vrba meni je isto ovako ispalo ali me zanima sto bi bilo kad bi morali napraviti union(2,4) umjesto union(2,3)?

saitama Šta se ne bi samo spojili 2 i 4?

member
saitama Po algoritmu, ne bi se ništa drugačije dogodilo, sve bi se isto dobilo

Može li netko objasniti što znači ovaj length u Union strukturi? Na prezentaciji piše da je to “duljina ciklusa kojem pripada vrh”, ali ne mogu shvatiti iz onog njihovog primjera.