eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingZamknięta pętlaRe: Zamknięta pętla
  • Data: 2009-01-29 10:42:58
    Temat: Re: Zamknięta pętla
    Od: Tomasz Kiełpiński <F...@p...onet.pl> szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    'Twas brillig when bartekLTG wrote:
    [...]
    > Punkty siatki sa weirzcholkami grafu, oznaczone na 'tak'
    > kreski są krawedziemi grafu.
    > Zalozmy, ze dorysowujesz krawedz miedzy wierzcholkami
    > a i b ( (n,m) --- [(n+1,m) lub (n,m+1)] )
    > Kiedy zamykami petle? Wtedy, gdy _przed_ dodaniem
    > naszej krawedzi istnieje polaczenie miedzy a i b.
    > Wystarczy wiec, ze sprawdzisz, czy istnieje polaczenie
    > miedzy a i b. Jest to dosc czesto spotykane zagadnienie;)
    > Algorytm nazywa sie 'przeszukiwanie drzewa w szerz'
    > (Breadth-first search, w skrócie BFS) jest dobrze
    > opisany w ksiezkach i sieci. Dlaczego 'w szerz' a nie
    > 'w glab'? ze wzgledu na pesymistyczna ilosc operacji.
    > Jesli najkrotsza sciazka ma dlugosc L, to odwiedzisz
    > nie wiecej niz max(4L^2,M) a M to liczba wierzcholkow
    > do ktorych mozesz dojsc;)
    > Algorytm zybszy i prostrzy w implementacji niz proponowana
    > obok Dijkstra, potrzebujesz jedynie kolejki fifo, czyli
    > zwyklej listy.
    > Bieresz element z kolejki i wrzucasz do kolejki
    > wszyskich sasiadow (wierzcholki, do ktorych masz bezposrednie
    > polaczenie krawedzią 'tak'), przy okazji sprawdzajac,
    > czy to nie jest nasz cel i czy nie byl 'odhaczony' (tych
    > nie wrzucasz). Wrzucane wierzcholki zaznaczamy jako 'odhaczone'
    > W pierwszym kroku wrzucasz do kolejki wierzcholek startowy.
    > BTW, Mozna to jeszcze zbic (do 2L^/2) idac na zmiane jedno
    > pietro z wierzcholka 'a' - jedno pietro z wierzcholka 'b'
    > i czekac na spotkanie, ale algorytm robi sie ciut bardziej
    > skomplikowany.
    > pzodrawiam
    > bartekltg

    Bartku, Maćku,

    Dzięki za cenne uwagi. Poczytałem o BFS (a przy okazji innych algorytmach
    związanych z grafami) i przemyślałem wasze propozycje. W efekcie końcowym
    zdecydowałem się na uproszczone (ze względu na zasady łamigłówki)
    rozwiązanie. Poniżej pseudo algorytm:

    1.Ustaw koordynaty wierzchołka A jako początkowe, wierzchołka B jako
    końcowe. Wyklucz odcinek AB
    2.PETLA:
    - sprawdź wszystkie narysowane odcinki z początkowego wierzchołka.
    - wybierz pierwszy niewykluczony
    - jeśli nie ma niewykluczonego odcinka:
    - jeśli koordynaty bieżącego wierzchołka i wierzchołka B są zgodne to
    PETLA ZAMKNIĘTA,
    jeśli nie to PETLA OTWARTA. Wyjdź z funkcji.
    - w przeciwnym razie:
    - przejdź do nowego wierzchołka
    - wyklucz pokonany właśnie odcinek
    - ustaw nowe koordynaty początkowe
    - wróć na początek pętli

    Pozdrawiam,
    Kiełpiś




    --
    Był czas mrutszławy, ślibkie skrątwy Tomasz Kiełpiński
    Na wałzach wiercząc świrypły, a.k.a. "Kiełpiś"
    A mizgłe do cna borogłątwy Odpowiadając prywatnie,
    I zdomne świszczury zgrzypły. usuń: FALSZYWY z adresu

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: