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?

do góry

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

do góry

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?

do góry

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

do góry

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

do góry

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

do góry

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.

do góry

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

do góry