Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28238

Re: Równoległe przeszukiwanie drzewa

From bartekltg <bartekltg@gmail.com>
Newsgroups pl.comp.programming
Subject Re: Równoległe przeszukiwanie drzewa
Date 2015-12-17 13:54 +0100
Organization ATMAN - ATM S.A.
Message-ID <n4uba5$old$1@node1.news.atman.pl> (permalink)
References <n4ua7n$20o$1@node2.news.atman.pl>

Show all headers | View raw

On 17.12.2015 13:36, Borneq wrote:
> Normalnie, przy rekurencyjnym przeszukiwaniu zaczyna się od najbardziej
> lewego poddrzewa, potem wybiera najbardziej lewą gałąź itd.
> A jak przeszukiwać w ten sposób że drzewo (niekoniecznie binarne)
> najpierw przeszukuje się do głębokości 1, potem do 2, w międzyczasie się
> rozgałęzia, więc więcej gałęzi szukamy. Czy to problem, gdzie przydadzą
> się coroutiny?

Nie. Kolejka zamiast stosu.
https://pl.wikipedia.org/wiki/Przeszukiwanie_w_g%C5%82%C4%85b [do 
porównania]
https://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz
https://en.wikipedia.org/wiki/Breadth-first_search

Pierwszy rozdział każdej książki do algorytmów.


> Ale co gdy mamy rozgałęzienie zwykle 2, czasami trzy?

A w czym problem z dowlnym rozgałęzieniemn?
W przeszukiwaniu w głąb wchodzisz w pętli rekurencjnie w każdą
odnogę == wrzucasz wszytkie odnogi na stos.
W przeszukiwaniu w szerz wrzucasz wszystkie odnogi do kolejki.


Kłopot z binarnymi jest przy 'numerowaniu' (kolejnośći prozechodzenia
wierzchołków, ciut inny prolbem niż powyższy). Tam jest
pre-order, post-order i in-order. Ostatni ma sans tylko dla binarnych.

pzdr
bartekltg

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Równoległe przeszukiwanie drzewa Borneq <borneq@antyspam.hidden.pl> - 2015-12-17 13:36 +0100
  Re: Równoległe przeszukiwanie drzewa bartekltg <bartekltg@gmail.com> - 2015-12-17 13:54 +0100
  Re: Równoległe przeszukiwanie drzewa "M.M." <mmarszik@gmail.com> - 2015-12-17 05:28 -0800
    Re: Równoległe przeszukiwanie drzewa bartekltg <bartekltg@gmail.com> - 2015-12-17 14:43 +0100
      Re: Równoległe przeszukiwanie drzewa "M.M." <mmarszik@gmail.com> - 2015-12-17 06:03 -0800
        Re: Równoległe przeszukiwanie drzewa "M.M." <mmarszik@gmail.com> - 2015-12-17 06:13 -0800
          Re: Równoległe przeszukiwanie drzewa platformowe głupki <NOSPAMtestowanije@go2.pl> - 2015-12-18 16:52 +0100
    Re: Równoległe przeszukiwanie drzewa Borneq <borneq@antyspam.hidden.pl> - 2015-12-17 17:09 +0100

csiph-web