Fastbar
Powrót do strony głównej
Trzymaj pliki na gmclan.org!
Game Maker w pytaniach i odpowiedziach!
Polska dokumentacja
Tabela wyników ligi 24
Pobierz GM
Kategorie bazy artykułów
Artykuły -> Kąciki programowania -> Algorytmy i struktury danych
Treść artykułu
Wprowadzenie do teorii grafów - cz. 3
autor: Platyna (24.05.09)
Wstęp do teorii grafów - cz. 3

Podstawowe algorytmy grafowe
     Witam w ostatniej części tego artykułu. Opiszę działanie oraz sposoby implementacji dwóch podstawowych algorytmów operujących na grafach. Jest to DFS i BFS. Przyjemnej lektury. ;)

DFS (Przeszukiwanie w głąb)
     DFS to skrót od Depth-first search. Algorytm ten jest wykorzystywany w bardzo wielu problemach. Służy do przeglądania kolejnych wierzchołków grafu w taki sposób, że zaczynając od dowolnego wierzchołka (korzenia) poruszamy się w głąb grafu. Gdy znajdziemy się w wierzchołku, od którego nie możemy już dojść do żadnego nieodwiedzonego wcześniej, cofamy się o jeden poziom wyżej i przeglądamy kolejnych sąsiadów. Rysunek 5 przedstawia przebieg algorytmu zaczynając od wierzchołka 1. Na czerwono oznaczono wierzchołki odwiedzone, a na zielono wierzchołek, w którym aktualnie się znajdujemy. Kolejność odwiedzania poszczególnych sąsiadów nie ma znaczenia.

     Jak łatwo się domyśleć, w przypadku grafów niespójnych algorytm zakończy swoje działanie przed sprawdzeniem wszystkich wierzchołków. Jest to więc dobry sposób na sprawdzenie spójności grafu.

Implementacja
     Najprostszą metodą implementacji DFSa jest zastosowanie rekurencji, czyli wywołania algorytmu wewnątrz samego siebie. Stwórzmy sobie tablicę O, która dla każdego wierzchołka będzie przechowywała wartość 1 jeżeli był on już odwiedzony lub wartość 0 jeżeli nie. Następnie stwórzmy funkcję DFS przyjmującą jeden argument w (numer wierzchołka, od którego zaczynamy przeszukiwanie). Funkcja ta musi aktualnemu wierzchołkowi ustawić wartość w tablicy O na 1 oraz przejrzeć w pętli wszystkich sąsiadów wierzchołka w i wywołać samą siebie dla tych jeszcze nieodwiedzonych.
     Tutaj widzimy jak ważna jest odpowiednia reprezentacja grafu. Gdybyśmy wykorzystali macierz sąsiedztwa musielibyśmy za każdym razem przeglądać WSZYSTKIE wierzchołki i sprawdzać czy są połączone z wierzchołkiem w. Listy sąsiedztwa dają nam szybki dostęp do jego sąsiadów.

Złożoność czasowa i pamięciowa
     Algorytm wymaga od nas zapamiętania dla każdego wierzchołka czy był on odwiedzany czy nie. Nietrudno, więc zauważyć, że zapotrzebowanie na pamięć jest proporcjonalne do liczby wierzchołków grafu.
     Trochę inaczej ma się sprawa złożoności czasowej. Algorytm musi dla każdego wierzchołka grafu sprawdzić wszystkich jego sąsiadów (czy byli już odwiedzani czy nie). Przy reprezentacji grafu za pomocą list sąsiedztwa czas sprawdzania wszystkich sąsiadów będzie, więc proporcjonalny do liczby krawędzi wychodzących z wierzchołka. Widzimy więc, że całkowity czas działania algorytmu będzie proporcjonalny do liczby krawędzi grafu.

BFS (Przeszukiwanie wszerz)
     BFS (Breadth-first search) ma bardzo podobne zastosowania co DFS. Również służy do przejrzenia wszystkich wierzchołków grafu jednak obiera trochę inną strategię. DFS najpierw skupiał się na jednym rozgałęzieniu, po czym przechodził do przetwarzania kolejnych. BFS natomiast najpierw sprawdza wszystkich sąsiadów danego wierzchołka, a następnie sąsiadów tych sąsiadów itd. aż do przetworzenia całego grafu. W przykładzie z Rysunku 5 kolejność odwiedzania wierzchołków przy użyciu DFSa była następująca: 1, 2, 4, 3, 7, 5, 6. Przy zastosowaniu algorytmu BFS wierzchołki będą odwiedzane w takiej kolejności: 1, 2, 3, 4, 7, 6, 5. Dla lepszego zrozumienia przeanalizujmy może jeszcze jeden przykład. Rysunek 6 przedstawia przebieg algorytmu dla pewnego grafu.


Implementacja
     Tak jak w DFS będziemy potrzebowali pewnej tablicy O przechowującej dla każdego wierzchołka odpowiednią wartość zależnie od tego czy był on już odwiedzony. Dodatkowo utwórzmy sobie kolejkę K zawierającą wierzchołki do odwiedzenia. Na początku znajdować się będzie na niej jedynie wierzchołek początkowy w. Następnie dopóki w kolejce znajdują się jeszcze jakieś nieprzetworzone wierzchołki należy je kolejno zdejmować i przeszukiwać ich sąsiadów. Jeżeli znajdziemy takiego sąsiada, którego jeszcze nie wrzucaliśmy do kolejki (odpowiednia wartość tablicy O jest równa 0) należy to uczynić i zmienić wartość w tablicy O. Przeanalizujemy przebieg algorytmu dla przykładu z Rysunku 6. Na początku w kolejce znajduje się jedynie wierzchołek 1. Ściągamy go i wrzucamy do kolejki wierzchołki 7 i 3. Zdejmujemy 7 i wrzucamy 2 i 6. Nasz kolejka wygląda teraz tak: 3, 2, 6. Bierzemy 3 i wrzucamy do kolejki jej sąsiadów, czyli 4 i 5 (w kolejce mamy: 2, 6, 4, 5). Teraz zdejmujemy 2 itd. Podobnie jak w algorytmie DFS, tak i tutaj korzystna jest reprezentacja grafu przy pomocy list sąsiedztwa.

Złożoność czasowa i pamięciowa
     Algorytm BFS oprócz tablicy O wymaga od nas również zapamiętania kolejki nieodwiedzonych dotąd wierzchołków. Złożoność pamięciowa będzie więc istotnie większa niż w algorytmie DFS.
     Podobnie jak DFS, BFS musi dla każdego wierzchołka przejrzeć wszystkich jego sąsiadów. Będzie ich tyle ile krawędzi wychodzących z wierzchołka. Złożoność czasowa algorytmu BFS będzie więc również proporcjonalna do całkowitej liczby krawędzi grafu.
     Widzimy więc, że algorytm ten jest mniej praktyczny niż DFS. Zwykle wiec się go nie używa. Istnieje jednak klika przypadków, w których BFS może się okazać lepszym rozwiązaniem. Wyobraźmy sobie graf, w którym krawędzie układają się w długi ciąg bez żadnych rozgałęzień. W takim przypadku liczba wywołanych w sobie DFSów była by równa liczbie wszystkich wierzchołków. Dla bardzo dużych danych mogłoby to zaowocować brakiem pamięci.

Przykłady zastosowania
-Sprawdzenie spójności grafu
-Wyszukanie najkrótszej drogi od danego wierzchołka do wszystkich pozostałych (pomijając wagi krawędzi)
-Wyznaczenie silnie spójnych składowych grafu skierowanego (jedynie DFS)
-Sortowanie topologiczne (jedynie DFS)

To już jest koniec...
     ...niniejszego artykułu. Był to jedynie zalążek zagadnienia teorii grafów. Istnieje jeszcze wiele algorytmów wykorzystywanych w różnych problemach, czasami nawet takich, które na pozór nie mają nic wspólnego z grafami. Cieszę się, że dobrnąłeś do tego miejsca. Mam nadzieję, że coś z tej lektury wyniosłeś, że udało mi się przybliżyć ci mniej więcej zagadnienie grafów. Polecam teraz poćwiczyć w praktyce implementacje omówionych tutaj algorytmów. Dziękuję, za przeczytanie mych wypocin :)
głosów: 12 | ocena: 8.17 oceń zasób | dodał: Platyna
Komentarze
stron: 1

1


av

Dawidds (16:25, 24.05.2009)

Liczyłem, że pod koniec artykułu podasz praktyczny przykład zastosowania tego...
Tak czy siak, jestem teraz o te parę słów (albo i więcej... ^^) mądrzejszy.

10/10.

av

Makary155 (19:42, 24.05.2009)

Świetne!

stron: 1

1



Dodaj komentarz:
Treść:
Menu
Panel użytkownika
Jesteś niezalogowany!

Nie masz konta? Zarejestruj się
Użytkownicy on-line
130 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 125, userów: 5, ukrytych: 0
opeginoczodun, eyizuukuciqo, lew_leo, gimagiogoa, Chell

0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
ANtY (8:51, 25.07.17):
bodajze 1500 pln
Ignatus (21:53, 24.07.17):
orientuje sie ktos jaki jest koszt mini stoiska indie na PGA?
Chell (21:19, 24.07.17):
zbilbym fortune na tym twoim jednorekim bandycie
ΨΧΞ (20:56, 24.07.17):
i jak nieznosze JSa, tak uwazam, ze niestety bedzie on przyszloscia gier i apek mobilnych :<
ΨΧΞ (20:56, 24.07.17):
a ja pochwale sie zrobieniem przykladowej gry w jednorekiego bandyte w 3 dni w JavaScriptcie od zera - silnik powstal wraz z gra github.com/Psic...slots-in-3-days
tramur (12:28, 24.07.17):
Powiedziałem z niską barierą wejścia, bo stworzenie shoot em upa jest troszke trudniejsze niż w GM'ie na kodach, a co do optymalizacji to nie wiem co masz na myśli.
tramur (12:26, 24.07.17):
;P powiedzoałem
Threef (6:02, 24.07.17):
Nie ma niskiego poziomu wejścia. I wymaga masy optymalizacji
tramur (21:33, 23.07.17):
Ja bym optował za czymś zgoła odwrotnym: PICO-8. Ciekawy koncept mitycznej retro konsolki z niską barierą wejścia, ale jak najbardziej z programowaniem.
Ignatus (17:13, 23.07.17):
Raczej nie
exp (16:21, 23.07.17):
a klocki w game makerze traktujecie jako programowanie?
Fervi  (11:29, 23.07.17):
Jasne, że najlepiej jest nauczyć się ich języka itd. Natomiast coś na kształt uproszczonego Dooma (powiedzmy - w skrócie) można zrobić (teoretycznie) bez żadnej linijki kodu dodatkowej. Bardziej to nie tyle Game Maker typowy co edytor map z językiem programowania
Danielus (10:37, 23.07.17):
Prawda ale chodzi raczej o coś innego. Chodzi o prostotę, im coś prościej zrobić tym łatwiej estymować pracę i tym łatwiej to potem utrzymać. Dlatego firmy ciągnie do języków takie jak C# czy Java. Pamiętaj że to tylko narzędzia i zawsze trzeba wybierać odpowiednie narzędzia jeśli możesz zrobić coś w rok w c# to wybierasz c# niż 5 lat w C nawet kosztem 50% spadku wydajności. Chyba że wydajność jest punktem krytycznym projektu.
Wojo (10:22, 23.07.17):
Aż mnie krew zalewa ale to jest nowe pokolenie programistów - idiotów
Wojo (10:22, 23.07.17):
Czytałem blog jakiegoś barana, który pisał, że C# pomimo, że jest mało wydajny to i tak warto się go uczyć bo teraz RAM bez problemu można dokupić
Wojo (10:21, 23.07.17):
No mniej więcej o to mi chodziło. O uproszczenie, co wiąże się z tym, że ludzie nawet nie myślą o optymalizacji
Danielus (10:19, 23.07.17):
W sensie mam na myśli że na początku taki człowiek dostaje gotowce i jest zadowolny a potem mówi "a mam pomysł żeby tu była taka mechanika" i nagle ludzie się uśmiechają "a to sobie napisz bo na to nie ma gotowca" no i projekt upadł.
Danielus (10:17, 23.07.17):
Zawsze wolałem 2d, jakoś przyjemniej się gra i trochę mi szkoda że nie ma już tak potężnych produkcji 2d jak np homm3 ale cuż :f Programować nadal musisz umieć, zmienia się zakres tego co trzeba umieć bo języki się uproszczają i powstają języki vizualne ale ja to wciąż będę nazywał porgoramowaniem bo wymaga takiego samego myślenia jak zwykłe programowanie. Natomiast ludzi przychodzą robić gry myśląc że to ot tak zrobią i potem płacz że miało być bez programowania
Wojo (10:14, 23.07.17):
No bo 3D to skok technologiczny i daje większe możliwości, a miłośników 2D jest znacznie mniej
Ignatus (10:12, 23.07.17):
Nie wiem co ludzie widzą w tym żę coś jest 3D, jak jest słaby pomysł i mechanika to jeden pies jaki masz widok.Wszyscy amatorzy zakładają że 3D od razu daje grze 3punkty do oceny
Wojo (10:06, 23.07.17):
Na tym forum żaden z działów poza GM się nie sprawdza. Hmmm ciekawe dlaczego
Wojo (10:05, 23.07.17):
A jeśli chodzi o tego sandbox game maker to równie dobrze można dodać dział "GAME MAKER 3D" bo program i tak reprezentuje trochę niższy poziom
Wojo (10:01, 23.07.17):
Ale w dzisiejszych czasach serio się nie musisz znać na programowaniu ( a przynajmniej tak bardzo jak kiedyś ).
Danielus (9:49, 23.07.17):
:Nie trzeba znać się na programowaniu" najbardziej idiotyczna fraza jaka pojawiła się w naszym środowisku. Jak nie trzeba programować to znacyz że nie zrobisz nic innego jak klony istniejących rzeczy.
Fervi  (1:39, 23.07.17):
Może admin niech się zastanowi nad dodaniem subforum "Sandbox Game Maker". To taki Game Maker, który napierdziela gry w 3D i nie trzeba znać się na programowaniu (chyba, że coś lepszego chcemy) - jak w GMie xd
MaxGaming (19:00, 22.07.17):
Na AM i nie automatycznie bo trzeba do jakiegoś urzędu zamienić ale nie wiem dokładnie
Wojo (18:13, 22.07.17):
A to nie jest tak, że karta motorowerowa automatycznie zamienia się w a1 ?
MaxGaming (17:41, 22.07.17):
Ja mam A1, a właściwie jeszcze nie mam bo muszę praktykę zdać. Zaczałem jakoś dwa lata temu i nigdy nie skończyłem to doszedłem do wniosku że kiedyś trzeba(chociaż gdybym teraz zaczął mógłbym a2 nie a1) xD
Wojo (15:25, 22.07.17):
A tak na poważnie chciałem sobie kupić 125ke ale niedawno zauważyłem, że trzeba mieć B 3 lata a nie 2 tak jak myślałem :/
Wojo (15:21, 22.07.17):
hehe lewa w górę
MaxGaming (15:14, 22.07.17):
Motor masz pod maska w samochodzie
MaxGaming (15:14, 22.07.17):
Motocykl*
Wojo (11:35, 22.07.17):
Motor
ANtY (10:59, 22.07.17):
co to cbrka
MaxGaming (2:38, 22.07.17):
Po prostu nigdy nie sprawdzajcie vmaxa gdy jest po deszczu a za 200 metrów jest zakręt 90 stopni xd
MaxGaming (2:37, 22.07.17):
Za 5000zł bym nie zaszalał jeżeli chodzi o muscle cara xd
Chell (2:36, 22.07.17):
wniosek trzeba bylo kupic muscle cara
MaxGaming (2:35, 22.07.17):
Wniosek? Nie opłaca się wychodzić z domu XD
MaxGaming (2:35, 22.07.17):
Kupiłem CBRkę i pierwszego dnia ją rozbiłem <facepalm> Koszt naprawy jakieś 2000zł(a kupiłem za 5000zł) XDDDD
I am vader (23:26, 21.07.17):
Kodze projegd
Wojo (21:42, 21.07.17):
a siedze se w domu jak zawsze i podróżnikowałem sobie po mieście wcześniej i generalnie jestem nawet zadowolony
Ignatus (20:53, 21.07.17):
Słyszałem że taka gorzka czekolada
Threef (20:47, 21.07.17):
A nie piłem. Jak ta jelitówka smakuje? Lepsza od wiśniówki?
Chell (19:52, 21.07.17):
siedze w chacie z jelitowka, elo
Nikas (19:47, 21.07.17):
alkololo
ANtY (18:41, 21.07.17):
PRZYZNAWAĆ SIĘ, NIC NIE UKRYWAĆ
ANtY (18:41, 21.07.17):
NO ELO CO TAM
Wojo (5:23, 20.07.17):
O dzięki, doceniam starania
Danieo (0:13, 20.07.17):
Wszystkiego najlepszego!
Gibki Kaktus (21:02, 19.07.17):
Btw zalogowałem się specjalnie, żeby Ci życzenia złożyć xD
Ankieta
» Jakiej wersji GameMakera głównie Używasz?
GameMaker: Studio 2
GameMaker: Studio
GameMaker 8.1 i starsze
Żadnej

GMCLAN to serwis o programie Game Maker i nie tylko.
Copyright © 2002-2017. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!

[ Czas generowania strony: 0.01245 sekund ] [ Liczba zapytań MySQL: 15 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev