Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

BFS i DFS algoritmi

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Matematičko modeliranje
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
Gordan
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 03. 11. 2002. (18:01:44)
Postovi: (192)16
Spol: muško
Sarma = la pohva - posuda
= 20 - 12
Lokacija: Zagreb

PostPostano: 21:46 čet, 15. 12. 2005    Naslov: BFS i DFS algoritmi Citirajte i odgovorite

Jel moze netko molim vas napisat jedan konkretan graf i primjenu DFS i BFS algoritama na njemu. Naime, u biljeznici imam samo jedan graf koji je odveć jednostavan, a iz primjera (http://degiorgi.math.hr/forum/viewtopic.php?t=5664) mi baš nije sve 100% jasno :oops:

hvala
Jel moze netko molim vas napisat jedan konkretan graf i primjenu DFS i BFS algoritama na njemu. Naime, u biljeznici imam samo jedan graf koji je odveć jednostavan, a iz primjera (http://degiorgi.math.hr/forum/viewtopic.php?t=5664) mi baš nije sve 100% jasno Embarassed

hvala



_________________
http://mafija.gameland.com.hr - budi i ti mafijaš!
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
Grga
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 12. 2004. (23:05:23)
Postovi: (280)16
Spol: muško
Sarma = la pohva - posuda
99 = 124 - 25

PostPostano: 23:17 čet, 15. 12. 2005    Naslov: Citirajte i odgovorite

Probat cu ovako jer ne znam ljepse...

[code:1]
e_1 e_7
V_1-------------V_2------------V_7
| |
|e_2 |e_8
| e_3 |
V_3-------------V_4
| |
| |
|e_4 |e_5
| e_6 |
V_5-------------V_6
[/code:1]
Za pocetak (korijen) uzmes bilo koji vrh. Recimo V_1

BFS
Pronades sve vrhove koji su bridom povezani s V_1. To su V_2 i V_3. Njih dodas u stablo(naravno zajedno s bridom koji povezuje vrh iz kojeg si trazio s vrhom kojeg si nasao). Sada trazis iz vrhova koje si nasao u proslom koraku - za V_2 trazis sve vrhove koji su bridom povezani sa njim, osim vrhova koji se vec nalaze u stablu (dakle V_1, V_2, V_3). To su V_4 i V_7, njih dodas u stablo. Za V_3 radis istu stvar i nades V_5 (V_4 je vec u stablu), njega takoder dodas u stablo. U zadnjem koraku si pronasao V_7, V_4 i V_5, pa iz njih trazis susjede koji jos nisu u stablu. iz V_7 ne vidis nista, iz V_4 nades V_6, iz V_5 ne nades nista. Njega takoder dodas u stablo. Nastavljas sa trazenjem iz vrhova koje si nasao u prethodnom koraku, a to je samo V_6, ali ne nalazis nijedan novi vrh, sto je znak za kraj algoritma.
Stablo koje si dobio izgleda ovako:
[code:1]
e_1 e_7
V_1-------------V_2------------V_7
| |
|e_2 |e_8
| |
V_3 V_4
| |
| |
|e_4 |e_5
| |
V_5 V_6
[/code:1]

DFS
Opet pocnes s V_1, trazis vrh koji mu je susjedan, nalazis V_2, dodajes ga u stablo i ides na V_2. Iz V_2 trazis susjedan koji nije u stablu, nalazis V_7, dodajes ga u stablo i ides na V_7. Iz V_7 ne nalazis nijedan susjedan vrh pa se vracas natrag na V_2. Trazis novi vrh iz V_2 i vidis V_4, dodas ga, i ides na V_4, iz V_4 vidis V_3, dodas ga i ides na V_3. Iz V_3 vidis V_5, dodas ga i ides na njega, iz njega vidis V_6, dodas ga i ides na njega. Iz V_6 ne vidis novi vrh pa se vracas na V_5, opet nema novog pa se vracas na V_3, pa na V_4, pa na V_2, pa na V_1. Iz V_1 takoder nema novog vrha, sto je znak za kraj algoritma (alternativno, ako unaprijed znas koliko vrhova moras imati u stablu, sto ces kad vidis graf ocito znati, znas da je gotovo cim dodas zadnji vrh)
Dobijes ovakvo stablo:
[code:1]
e_1 e_7
V_1-------------V_2------------V_7
|
|e_8
e_3 |
V_3-------------V_4
|
|
|e_4
| e_6
V_5-------------V_6
[/code:1]

Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa :)[/code]
Probat cu ovako jer ne znam ljepse...

Kod:

          e_1                   e_7 
V_1-------------V_2------------V_7
  |              |
  |e_2           |e_8
  |       e_3    |
V_3-------------V_4
  |              |
  |              |
  |e_4           |e_5
  |       e_6    |
V_5-------------V_6

Za pocetak (korijen) uzmes bilo koji vrh. Recimo V_1

BFS
Pronades sve vrhove koji su bridom povezani s V_1. To su V_2 i V_3. Njih dodas u stablo(naravno zajedno s bridom koji povezuje vrh iz kojeg si trazio s vrhom kojeg si nasao). Sada trazis iz vrhova koje si nasao u proslom koraku - za V_2 trazis sve vrhove koji su bridom povezani sa njim, osim vrhova koji se vec nalaze u stablu (dakle V_1, V_2, V_3). To su V_4 i V_7, njih dodas u stablo. Za V_3 radis istu stvar i nades V_5 (V_4 je vec u stablu), njega takoder dodas u stablo. U zadnjem koraku si pronasao V_7, V_4 i V_5, pa iz njih trazis susjede koji jos nisu u stablu. iz V_7 ne vidis nista, iz V_4 nades V_6, iz V_5 ne nades nista. Njega takoder dodas u stablo. Nastavljas sa trazenjem iz vrhova koje si nasao u prethodnom koraku, a to je samo V_6, ali ne nalazis nijedan novi vrh, sto je znak za kraj algoritma.
Stablo koje si dobio izgleda ovako:
Kod:

          e_1                   e_7 
V_1-------------V_2------------V_7
  |              |
  |e_2           |e_8
  |              |
V_3            V_4
  |              |
  |              |
  |e_4           |e_5
  |              |
V_5             V_6


DFS
Opet pocnes s V_1, trazis vrh koji mu je susjedan, nalazis V_2, dodajes ga u stablo i ides na V_2. Iz V_2 trazis susjedan koji nije u stablu, nalazis V_7, dodajes ga u stablo i ides na V_7. Iz V_7 ne nalazis nijedan susjedan vrh pa se vracas natrag na V_2. Trazis novi vrh iz V_2 i vidis V_4, dodas ga, i ides na V_4, iz V_4 vidis V_3, dodas ga i ides na V_3. Iz V_3 vidis V_5, dodas ga i ides na njega, iz njega vidis V_6, dodas ga i ides na njega. Iz V_6 ne vidis novi vrh pa se vracas na V_5, opet nema novog pa se vracas na V_3, pa na V_4, pa na V_2, pa na V_1. Iz V_1 takoder nema novog vrha, sto je znak za kraj algoritma (alternativno, ako unaprijed znas koliko vrhova moras imati u stablu, sto ces kad vidis graf ocito znati, znas da je gotovo cim dodas zadnji vrh)
Dobijes ovakvo stablo:
Kod:

          e_1                   e_7 
V_1-------------V_2------------V_7
                 |
                 |e_8
          e_3    |
V_3-------------V_4
  |                   
  |                   
  |e_4               
  |       e_6       
V_5-------------V_6


Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa Smile[/code]



_________________
Bri
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Gordan
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 03. 11. 2002. (18:01:44)
Postovi: (192)16
Spol: muško
Sarma = la pohva - posuda
= 20 - 12
Lokacija: Zagreb

PostPostano: 23:57 čet, 15. 12. 2005    Naslov: Citirajte i odgovorite

HVALA :miniklap:
HVALA Applause



_________________
http://mafija.gameland.com.hr - budi i ti mafijaš!
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 0:53 pet, 16. 12. 2005    Naslov: Citirajte i odgovorite

[quote]Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa[/quote]

L O L
:boliglava: :biglol:
Citat:
Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa


L O L
Boli glava Uber-zabavno!



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
goranm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
218 = 249 - 31

PostPostano: 1:13 pet, 16. 12. 2005    Naslov: Citirajte i odgovorite

[quote="ahri"][quote]Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa[/quote]

L O L
:boliglava: :biglol:[/quote]
zake je to smiješno? :)
ahri (napisa):
Citat:
Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa


L O L
Boli glava Uber-zabavno!

zake je to smiješno? Smile



_________________
The Dude Abides
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Grga
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 12. 2004. (23:05:23)
Postovi: (280)16
Spol: muško
Sarma = la pohva - posuda
99 = 124 - 25

PostPostano: 1:23 pet, 16. 12. 2005    Naslov: Citirajte i odgovorite

[quote="ahri"][quote]Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa[/quote]

L O L
:boliglava: :biglol:[/quote]

Zanimljiva reakcija :) Ako nista drugo. bar sam nekog razveselio :P
Daj mi molim te protuprimjer kad je DFS bolji za pronalazenje stabla gledajuci graf. Ili kad imas tome najslicniji zapis (popis susjednih vrhova svakom vrhu) u kompjutoru i das mu da pronade stablo :D


No sad stvarno, u kojem je to slucaju DFS bolji :?:
ahri (napisa):
Citat:
Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa


L O L
Boli glava Uber-zabavno!


Zanimljiva reakcija Smile Ako nista drugo. bar sam nekog razveselio Razz
Daj mi molim te protuprimjer kad je DFS bolji za pronalazenje stabla gledajuci graf. Ili kad imas tome najslicniji zapis (popis susjednih vrhova svakom vrhu) u kompjutoru i das mu da pronade stablo Very Happy


No sad stvarno, u kojem je to slucaju DFS bolji Question



_________________
Bri
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 2:04 pet, 16. 12. 2005    Naslov: Citirajte i odgovorite

DFS i BFS su algoritmi PRETRAZIVANJA (S = Search), ne generiranja stabala :).

Oba algoritma su jednako brza - O(n) - niti jedan vrh nece obzervirati vise od jednom. I jedan i drugi mogu u zadnjoj iteraciji pronaci trazeni vrh, isto tako kao sto mogu u drugoj.
DFS i BFS su algoritmi PRETRAZIVANJA (S = Search), ne generiranja stabala :).

Oba algoritma su jednako brza - O(n) - niti jedan vrh nece obzervirati vise od jednom. I jedan i drugi mogu u zadnjoj iteraciji pronaci trazeni vrh, isto tako kao sto mogu u drugoj.



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Grga
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 12. 2004. (23:05:23)
Postovi: (280)16
Spol: muško
Sarma = la pohva - posuda
99 = 124 - 25

PostPostano: 2:23 pet, 16. 12. 2005    Naslov: Citirajte i odgovorite

[quote="ahri"]DFS i BFS su algoritmi PRETRAZIVANJA (S = Search), ne generiranja stabala :).

Oba algoritma su jednako brza - O(n) - niti jedan vrh nece obzervirati vise od jednom. I jedan i drugi mogu u zadnjoj iteraciji pronaci trazeni vrh, isto tako kao sto mogu u drugoj.[/quote]

Nisam mislio da imas tako nisko misljenje o meni da mislis da ne znam sto znaci BFS i DFS :(

Izgleda da me asistent Raguz ipak uspio uvjeriti u nesto sto nije istina, valjda zbog toga sto puno vise volim BFS nego DFS :?
ahri (napisa):
DFS i BFS su algoritmi PRETRAZIVANJA (S = Search), ne generiranja stabala Smile.

Oba algoritma su jednako brza - O(n) - niti jedan vrh nece obzervirati vise od jednom. I jedan i drugi mogu u zadnjoj iteraciji pronaci trazeni vrh, isto tako kao sto mogu u drugoj.


Nisam mislio da imas tako nisko misljenje o meni da mislis da ne znam sto znaci BFS i DFS Sad

Izgleda da me asistent Raguz ipak uspio uvjeriti u nesto sto nije istina, valjda zbog toga sto puno vise volim BFS nego DFS Confused



_________________
Bri
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 12:47 pet, 16. 12. 2005    Naslov: Citirajte i odgovorite

Ne znam tko si, pa sam napisao sto su, jer si izrekao nonsence :).
Ja npr vise volim DFS jer mi ga je puno lakse iskodirati ;)
Ne znam tko si, pa sam napisao sto su, jer si izrekao nonsence :).
Ja npr vise volim DFS jer mi ga je puno lakse iskodirati ;)



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Melkor
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 10. 2004. (18:48:00)
Postovi: (291)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
140 = 152 - 12
Lokacija: Void

PostPostano: 9:51 sub, 17. 12. 2005    Naslov: Citirajte i odgovorite

U biti, algoritam koji je bolje odabrati za pretraživanje ponekad ovisi o samoj prirodi problema. Recimo, ako znamo da se ono što tražimo nalazi "blizu" vrha koji nam je početni, bolje je odabrati BFS. Ako nam je bitno da je rješenje "najbliže" početnom vrhu, isto je bolje odabrati BFS.

Kao što ahri kaže, DFS je puno lakše iskodirati i ne troši previše memorije. BFS bi nam možda prije riješio problem, ali memorijski je zahtjevniji jer koristi queue za spremanje vrhova koje mora posjetiti.

I tako, svaki ima svoje prednosti i mane. Ako je svejedno koji se koristi, ja bih isto uvijek prije odabrao DFS nego BFS zbog jednostavnosti.
U biti, algoritam koji je bolje odabrati za pretraživanje ponekad ovisi o samoj prirodi problema. Recimo, ako znamo da se ono što tražimo nalazi "blizu" vrha koji nam je početni, bolje je odabrati BFS. Ako nam je bitno da je rješenje "najbliže" početnom vrhu, isto je bolje odabrati BFS.

Kao što ahri kaže, DFS je puno lakše iskodirati i ne troši previše memorije. BFS bi nam možda prije riješio problem, ali memorijski je zahtjevniji jer koristi queue za spremanje vrhova koje mora posjetiti.

I tako, svaki ima svoje prednosti i mane. Ako je svejedno koji se koristi, ja bih isto uvijek prije odabrao DFS nego BFS zbog jednostavnosti.



_________________
I don't know half of you half as well as I should like; and I like less than half of you half as well as you deserve.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Grga
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 12. 2004. (23:05:23)
Postovi: (280)16
Spol: muško
Sarma = la pohva - posuda
99 = 124 - 25

PostPostano: 10:09 sub, 17. 12. 2005    Naslov: Citirajte i odgovorite

Pa to su sad neke isprike... 8)
Mislim, tesko da ti se moze dogodit da ti queue bude prevelik jer ne moze zauzimat vise mjesta od broja vrhova.
A i ne znam zasto mislite da je tako tezi za iskodirat, meni se cini da je podjednako (ne)problematicno. :D
Pa to su sad neke isprike... Cool
Mislim, tesko da ti se moze dogodit da ti queue bude prevelik jer ne moze zauzimat vise mjesta od broja vrhova.
A i ne znam zasto mislite da je tako tezi za iskodirat, meni se cini da je podjednako (ne)problematicno. Very Happy



_________________
Bri
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Melkor
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 10. 2004. (18:48:00)
Postovi: (291)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
140 = 152 - 12
Lokacija: Void

PostPostano: 10:22 sub, 17. 12. 2005    Naslov: Citirajte i odgovorite

A što ako graf ima puno vrhova? Možda ti ne stane još i queue u memoriju. :-s

DFS je lakše iskodirati zato što je to obično neka mala rekurzija bez nekakvih dodatnih struktura podataka. I IMHO izgleda elegantnije. :)
A što ako graf ima puno vrhova? Možda ti ne stane još i queue u memoriju. Eh?

DFS je lakše iskodirati zato što je to obično neka mala rekurzija bez nekakvih dodatnih struktura podataka. I IMHO izgleda elegantnije. Smile



_________________
I don't know half of you half as well as I should like; and I like less than half of you half as well as you deserve.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Grga
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 12. 2004. (23:05:23)
Postovi: (280)16
Spol: muško
Sarma = la pohva - posuda
99 = 124 - 25

PostPostano: 10:38 sub, 17. 12. 2005    Naslov: Citirajte i odgovorite

[quote="Melkor"]A što ako graf ima puno vrhova? Možda ti ne stane još i queue u memoriju. :-s

DFS je lakše iskodirati zato što je to obično neka mala rekurzija bez nekakvih dodatnih struktura podataka. I IMHO izgleda elegantnije. :)[/quote]

Pa za to bi trebalo stvarno puno vrhova, recimo koji milijun.

A ako vec imas puno vrhova, rekurzija ti bez problema dozivi stack overflow, pa ti je kompliciranije napravit DFS.
:D
Melkor (napisa):
A što ako graf ima puno vrhova? Možda ti ne stane još i queue u memoriju. Eh?

DFS je lakše iskodirati zato što je to obično neka mala rekurzija bez nekakvih dodatnih struktura podataka. I IMHO izgleda elegantnije. Smile


Pa za to bi trebalo stvarno puno vrhova, recimo koji milijun.

A ako vec imas puno vrhova, rekurzija ti bez problema dozivi stack overflow, pa ti je kompliciranije napravit DFS.
Very Happy



_________________
Bri
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 13:19 sub, 17. 12. 2005    Naslov: Citirajte i odgovorite

[quote="Grga"]Pa za to bi trebalo stvarno puno vrhova, recimo koji milijun.[/quote]

U praksi, to i nije puno... :shock:

Evo jedan primjer: u magisteriju imam graf s [latex]n^2[/latex] vrhova i [latex]2n^2 - n[/latex] bridova. :? Ako se doticni "ispravno" posloze, taj graf mi producira skup od otprilike [latex]O(n^n)[/latex] generatora konusa (nekakvi vektori u [latex](2n^2 - n)[/latex]-dimenzionalnom prostoru). :shock:

Nema nikakve veze s BSF/DSF; samo pokazuje kako brojevi u praksi jako lako narastu, pa milijun stvarno nije nesto... :?
Grga (napisa):
Pa za to bi trebalo stvarno puno vrhova, recimo koji milijun.


U praksi, to i nije puno... Shocked

Evo jedan primjer: u magisteriju imam graf s vrhova i bridova. Confused Ako se doticni "ispravno" posloze, taj graf mi producira skup od otprilike generatora konusa (nekakvi vektori u -dimenzionalnom prostoru). Shocked

Nema nikakve veze s BSF/DSF; samo pokazuje kako brojevi u praksi jako lako narastu, pa milijun stvarno nije nesto... Confused



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
vili
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 06. 2005. (22:40:59)
Postovi: (14A)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
31 = 55 - 24
Lokacija: Keglić

PostPostano: 16:15 sub, 17. 12. 2005    Naslov: Citirajte i odgovorite

[quote="ahri"][quote]Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa[/quote]

L O L
:boliglava: :biglol:[/quote]

:ccc: Nije lijepo od tebe, no need to showoff.

[quote="ahri"]ne znam tko si[/quote]

:shock:
ahri (napisa):
Citat:
Uglavnom BFS ti je, iako to mozda iz ovog primjera nije ocito, puno brzi i bolji od DFSa


L O L
Boli glava Uber-zabavno!


Ccc.... Sram te bilo... Nije lijepo od tebe, no need to showoff.

ahri (napisa):
ne znam tko si


Shocked


[Vrh]
Korisnički profil Pošaljite privatnu poruku
goranm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
218 = 249 - 31

PostPostano: 16:24 sub, 17. 12. 2005    Naslov: Citirajte i odgovorite

Pa dobro, što se tiče modeliranja kao predmeta, BFS i DFS se mogu smatrati algoritmima za generiranje stabla. Barem u ljudskom kompjuteru, mozgu, se mogu tako smatrati.
I tada ako mozak smatramo procesorom, tada BFS je stvarno brži u većini slučajeva. Neću reći u svim, jer možda postoji neki primjer gdje DFS brže izgenerira stablo, ali takav primjer nismo napravili na vježbama, niti sam ga ja vidio igdje drugdje. :)
Pa dobro, što se tiče modeliranja kao predmeta, BFS i DFS se mogu smatrati algoritmima za generiranje stabla. Barem u ljudskom kompjuteru, mozgu, se mogu tako smatrati.
I tada ako mozak smatramo procesorom, tada BFS je stvarno brži u većini slučajeva. Neću reći u svim, jer možda postoji neki primjer gdje DFS brže izgenerira stablo, ali takav primjer nismo napravili na vježbama, niti sam ga ja vidio igdje drugdje. Smile



_________________
The Dude Abides
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 22:50 sub, 17. 12. 2005    Naslov: Citirajte i odgovorite

mozak je neuronska mreza i malo drugacije sastavlja stablo ;).

vili: kad sam vidio tko je to napisao... doslo mi je da se ili rasplacem ili nasmijem. ;)
mozak je neuronska mreza i malo drugacije sastavlja stablo ;).

vili: kad sam vidio tko je to napisao... doslo mi je da se ili rasplacem ili nasmijem. ;)



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
vili
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 06. 2005. (22:40:59)
Postovi: (14A)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
31 = 55 - 24
Lokacija: Keglić

PostPostano: 12:14 ned, 18. 12. 2005    Naslov: Citirajte i odgovorite

[quote="ahri"]vili: kad sam vidio tko je to napisao... doslo mi je da se ili rasplacem ili nasmijem. ;)[/quote]

Misliš na ono što sam ja napisao ili Grga?

A i mislio sam da znaš Grgu. Barem mi je on tak reko :PP
ahri (napisa):
vili: kad sam vidio tko je to napisao... doslo mi je da se ili rasplacem ili nasmijem. Wink


Misliš na ono što sam ja napisao ili Grga?

A i mislio sam da znaš Grgu. Barem mi je on tak reko Weeee-heeee!!!


[Vrh]
Korisnički profil Pošaljite privatnu poruku
Grga
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 12. 2004. (23:05:23)
Postovi: (280)16
Spol: muško
Sarma = la pohva - posuda
99 = 124 - 25

PostPostano: 15:08 ned, 18. 12. 2005    Naslov: Citirajte i odgovorite

[quote="vsego"][quote="Grga"]Pa za to bi trebalo stvarno puno vrhova, recimo koji milijun.[/quote]

U praksi, to i nije puno... :shock:

Evo jedan primjer: u magisteriju imam graf s [latex]n^2[/latex] vrhova i [latex]2n^2 - n[/latex] bridova. :? Ako se doticni "ispravno" posloze, taj graf mi producira skup od otprilike [latex]O(n^n)[/latex] generatora konusa (nekakvi vektori u [latex](2n^2 - n)[/latex]-dimenzionalnom prostoru). :shock:

Nema nikakve veze s BSF/DSF; samo pokazuje kako brojevi u praksi jako lako narastu, pa milijun stvarno nije nesto... :?[/quote]

Istina da mi je argument losh, ono sto sam trebao reci je:
Ako imamo n vrhova, a graf je jednostavan, mozemo imati [latex]\frac{n(n-1)}{2}[/latex] bridova.
Pa sad, ako smo imali memorije za n^2 bridova, queue od do n vrhova ne bi trebao biti tako problematican.
S druge strane, u rekurziji se stack overflow pojavljuje prilicno brzo, vec kod kojih 100-200 poziva u dubinu (iteracija, rekurzivnih poziva, ili kako god se to vec zove, ti izrazi mi nikad nisu isli :oops: ).

Mislim, ocito je da DFS necemu sluzi, jer inace ga se ne bi ni spominjalo (ocito se npr koristi u stvarnom zivotu, jer malo je teze uzivo primijeniti BFS :lol: npr. ako moramo pronaci izlaz iz labirinta :P), ali u svakom problemu koji meni pada na pamet, DFS je u najboljem slucaju jednako dobar kao BFS (osim ako imamo srece, ali to nije dobar argument :D).

@vili: Pa naravno da me ahri nije skuzio, kad ne zna moj nick na forumu, a nije tako lako povezati moj nick na forumu i onaj irl :P
Doduse, reakcija bi mi bila razumljivija da je znao da sam to ja, a ne da tako ismijava neku nepoznatu osobu, koja je, btw, samo htjela pomoci (ccc ahri) :shock:
vsego (napisa):
Grga (napisa):
Pa za to bi trebalo stvarno puno vrhova, recimo koji milijun.


U praksi, to i nije puno... Shocked

Evo jedan primjer: u magisteriju imam graf s vrhova i bridova. Confused Ako se doticni "ispravno" posloze, taj graf mi producira skup od otprilike generatora konusa (nekakvi vektori u -dimenzionalnom prostoru). Shocked

Nema nikakve veze s BSF/DSF; samo pokazuje kako brojevi u praksi jako lako narastu, pa milijun stvarno nije nesto... Confused


Istina da mi je argument losh, ono sto sam trebao reci je:
Ako imamo n vrhova, a graf je jednostavan, mozemo imati bridova.
Pa sad, ako smo imali memorije za n^2 bridova, queue od do n vrhova ne bi trebao biti tako problematican.
S druge strane, u rekurziji se stack overflow pojavljuje prilicno brzo, vec kod kojih 100-200 poziva u dubinu (iteracija, rekurzivnih poziva, ili kako god se to vec zove, ti izrazi mi nikad nisu isli Embarassed ).

Mislim, ocito je da DFS necemu sluzi, jer inace ga se ne bi ni spominjalo (ocito se npr koristi u stvarnom zivotu, jer malo je teze uzivo primijeniti BFS Laughing npr. ako moramo pronaci izlaz iz labirinta Razz), ali u svakom problemu koji meni pada na pamet, DFS je u najboljem slucaju jednako dobar kao BFS (osim ako imamo srece, ali to nije dobar argument Very Happy).

@vili: Pa naravno da me ahri nije skuzio, kad ne zna moj nick na forumu, a nije tako lako povezati moj nick na forumu i onaj irl Razz
Doduse, reakcija bi mi bila razumljivija da je znao da sam to ja, a ne da tako ismijava neku nepoznatu osobu, koja je, btw, samo htjela pomoci (ccc ahri) Shocked



_________________
Bri
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 23:10 ned, 18. 12. 2005    Naslov: Citirajte i odgovorite

pa prvo sam pomislio da si to ti, ali kada sam vidio sto si napisao, nisam bio bas tako siguran ;).

"sreca" :). pa to je to... hoce li prvo BFS ili DFS nabasati na rjesenje. ponekad bfs - ponekad dfs... jednaka je vjerojatnost :)

za labirint je ofkors bolji bfs
pa prvo sam pomislio da si to ti, ali kada sam vidio sto si napisao, nisam bio bas tako siguran ;).

"sreca" :). pa to je to... hoce li prvo BFS ili DFS nabasati na rjesenje. ponekad bfs - ponekad dfs... jednaka je vjerojatnost :)

za labirint je ofkors bolji bfs



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Matematičko modeliranje Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Možete otvarati nove teme.
Možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan