-
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
Najnowsze wątki z tej grupy
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
Najnowsze wątki
- 2024-11-29 Dławik CM
- 2024-11-29 [OT] Lewe oprogramowanie
- 2024-11-29 Błonie => Sales Specialist <=
- 2024-11-29 Warszawa => IT Expert (Network Systems area) <=
- 2024-11-29 Warszawa => Ekspert IT (obszar systemów sieciowych) <=
- 2024-11-29 Warszawa => Head of International Freight Forwarding Department <=
- 2024-11-29 Białystok => Inżynier Serwisu Sprzętu Medycznego <=
- 2024-11-29 Pómpy ciepła darmo rozdajoo
- 2024-11-29 Białystok => Application Security Engineer <=
- 2024-11-29 Białystok => Programista Full Stack (.Net Core) <=
- 2024-11-29 Gdańsk => Software .Net Developer <=
- 2024-11-29 Wrocław => Key Account Manager <=
- 2024-11-29 Gdańsk => Specjalista ds. Sprzedaży <=
- 2024-11-29 Chrzanów => Specjalista ds. public relations <=
- 2024-11-27 Re: UseGalileo -- PRODUKTY I APLIKACJE UŻYWAJĄ JUŻ DZIŚ SYSTEMU GALILEO