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

Groups > pl.comp.programming > #28237 > unrolled thread

Równoległe przeszukiwanie drzewa

Back to article view | Back to pl.comp.programming

Contents

  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

#28237 — Równoległe przeszukiwanie drzewa

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?
W szachach jest podobnie, ale tam szukanie na głębokość n+1, zawiera w 
sobie szukanie całych poddrzew poczynając od korzenia, z drugiej strony 
inaczej trzeba by zapamiętywać pozycje, a przy współczynniku 
rozgałęzienia kilkadziesiąt, koszt szukania od nowa jest pomijalny.
Ale co gdy mamy rozgałęzienie zwykle 2, czasami trzy?

[toc] | [next] | [standalone]

#28238

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

[toc] | [prev] | [next] | [standalone]

#28239

On Thursday, December 17, 2015 at 1:36:08 PM UTC+1, 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?
> W szachach jest podobnie, ale tam szukanie na głębokość n+1, zawiera w 
> sobie szukanie całych poddrzew poczynając od korzenia, z drugiej strony 
> inaczej trzeba by zapamiętywać pozycje, a przy współczynniku 
> rozgałęzienia kilkadziesiąt, koszt szukania od nowa jest pomijalny.
> Ale co gdy mamy rozgałęzienie zwykle 2, czasami trzy?

Odpowiadam mniej/więcej to samo co Bartek. Stos, jakbyś się uparł, można
też zastosować, ale nie jeden, lecz dwa :) Można użyć flagi 'odwiedzony'
zamiast kolejki, ale wtedy musi być tyle flag, ile wątków i oznacza
stały* narzut pamięciowy. W przypadku kolejki na pamięć jest zapotrzebowanie
jest tylko wtedy gdy wątki przeszukują.

*przez cały czas przechowywania struktury drzewa/grafu w pamięci programu.

Pozdrawiam

P.S.
A do czego to jest potrzebne?

[toc] | [prev] | [next] | [standalone]

#28240

On 17.12.2015 14:28, M.M. wrote:
> On Thursday, December 17, 2015 at 1:36:08 PM UTC+1, 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?
>> W szachach jest podobnie, ale tam szukanie na głębokość n+1, zawiera w
>> sobie szukanie całych poddrzew poczynając od korzenia, z drugiej strony
>> inaczej trzeba by zapamiętywać pozycje, a przy współczynniku
>> rozgałęzienia kilkadziesiąt, koszt szukania od nowa jest pomijalny.
>> Ale co gdy mamy rozgałęzienie zwykle 2, czasami trzy?
>
> Odpowiadam mniej/więcej to samo co Bartek. Stos, jakbyś się uparł, można
> też zastosować, ale nie jeden, lecz dwa :) Można użyć flagi 'odwiedzony'
> zamiast kolejki, ale wtedy musi być tyle flag, ile wątków i oznacza
> stały* narzut pamięciowy. W przypadku kolejki na pamięć jest zapotrzebowanie
> jest tylko wtedy gdy wątki przeszukują.

Dobrze, masz flagę, ale jak przechodzisz drzewo?

Co do wątków, mam podejrzenie, że 'równoległe' pojawia się
w poście z braku znajomośći poprzwnego sformułowania - "w szerz",
nie dlatego, by zbobić to wielowątkowo.

>
> *przez cały czas przechowywania struktury drzewa/grafu w pamięci programu.
>
> Pozdrawiam
>
> P.S.
> A do czego to jest potrzebne?


Wyglada, że chce przeszukać drzewo do zadanej głębokośći lub do
głębokości, na której znajduje się rozwiązanie, ale nie głębiej.
Właśnie do tego BFS zostało stworzone;-)

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28241

On Thursday, December 17, 2015 at 2:43:38 PM UTC+1, bartekltg wrote:
> On 17.12.2015 14:28, M.M. wrote:
> > On Thursday, December 17, 2015 at 1:36:08 PM UTC+1, 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?
> >> W szachach jest podobnie, ale tam szukanie na głębokość n+1, zawiera w
> >> sobie szukanie całych poddrzew poczynając od korzenia, z drugiej strony
> >> inaczej trzeba by zapamiętywać pozycje, a przy współczynniku
> >> rozgałęzienia kilkadziesiąt, koszt szukania od nowa jest pomijalny.
> >> Ale co gdy mamy rozgałęzienie zwykle 2, czasami trzy?
> >
> > Odpowiadam mniej/więcej to samo co Bartek. Stos, jakbyś się uparł, można
> > też zastosować, ale nie jeden, lecz dwa :) Można użyć flagi 'odwiedzony'
> > zamiast kolejki, ale wtedy musi być tyle flag, ile wątków i oznacza
> > stały* narzut pamięciowy. W przypadku kolejki na pamięć jest zapotrzebowanie
> > jest tylko wtedy gdy wątki przeszukują.
> 
> Dobrze, masz flagę, ale jak przechodzisz drzewo?
Można, ale zupełnie inna sprawa czy to ma praktyczny sens :)


struct Node {
  void *data
  int  *children;
  uint flags
};


Node tree[SIZE];

root = 0;
tree[root].flags = 1<<CURR_THREAD;
tree[not_root].flags = 0; // sory za metakod

int queue;
do {
  queue = 0;
  for( i=0 ; i<SIZE ; i++ ) {
    if( tree[i].flags & CURR_THREAD ) {
      tree[i].flags ^= 1<<CURR_THRED;
      queue++;
      print( i );
      for( j=0 ; tree[i].children[j] >= 0 ; j++ ) // dowolna kolejność
        tree[ tree[i].children[j] ].flags |= 1<<CURR_THREAD;
    }
  }
} while( queue > 0 );

Pozdrawiam

> 
> Co do wątków, mam podejrzenie, że 'równoległe' pojawia się
> w poście z braku znajomośći poprzwnego sformułowania - "w szerz",
> nie dlatego, by zbobić to wielowątkowo.
Hmmmm.



> Wyglada, że chce przeszukać drzewo do zadanej głębokośći lub do
> głębokości, na której znajduje się rozwiązanie, ale nie głębiej.
> Właśnie do tego BFS zostało stworzone;-)
To w mojej wersji jeszcze trzeba dać to ograniczenie głębokości :)


Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28242

On Thursday, December 17, 2015 at 3:03:38 PM UTC+1, M.M. wrote:
> > Wyglada, że chce przeszukać drzewo do zadanej głębokośći lub do
> > głębokości, na której znajduje się rozwiązanie, ale nie głębiej.
> > Właśnie do tego BFS zostało stworzone;-)
> To w mojej wersji jeszcze trzeba dać to ograniczenie głębokości :)

A no i jeszcze trzeba tablicę przeglądać od tyłu i mieć gwarancję że
dzieci są pod adresem większym niż rodzic - bo inaczej w powyższej
wersji nie będzie gwarancji że przeszukało się dokładnie na głębokość N :)

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28244

oooo... koledzy widzę specjaliści od zmiennej pomocniczej... no no...

[toc] | [prev] | [next] | [standalone]

#28243

W dniu 17.12.2015 o 14:28, M.M. pisze:
> A do czego to jest potrzebne?

Zastanawiam się nad parserem lewostronnym, takim proceduralnym, gdzie 
każdej produkcji będzie odpowiadała procedura. Ale język niekoniecznie 
musi byc prosty LL(1) z jednym symbolem do podglądu, ale LL(*) z dowolną 
ilością, trzeba by podejrzeć ścieżki. ale (jeszcze nie wiem dokładnie) 
wybrać tę która w najbliższej odległości pasuje.

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web