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