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. 1
autor: Platyna (24.05.09)
Wstęp do teorii grafów - cz. 1

Wprowadzenie
     Witam w pierwszej części artykułu mającego na celu wprowadzenie czytelnika do zagadnienia teorii grafów. Przedstawione tu zostaną podstawowe pojęcia dotyczące grafów, trochę teorii oraz kilka przykładów ich zastosowania. Czyli w skrócie: Z czym to się je. ;)
     Na początku należy powiedzieć, co to w ogóle jest teoria grafów? Według Wikipedii, jest to dział matematyki zajmujący się badaniem własności grafów. Ale w takim razie czym jest graf? W dużym uproszczeniu, jest to zbiór wierzchołków oraz łączących je krawędzi. Bardziej formalnie jest to pewna struktura danych, czyli sposób uporządkowania informacji w komputerze. Rysunek 1 przedstawia przykładowy spójny graf. Ma on 7 wierzchołków i 8 krawędzi.


Podstawowe pojęcia dotyczące grafów
     Wiem, że nikt nie lubi masy teorii no ale niestety trzeba się z tym zapoznać. Na szczęście nie będzie tu żadnych pogiętych, wymyślnych nazw tylko bardzo intuicyjne pojęcia. :)

Rodzaje grafów:
Graf spójny - jest to graf w którym poruszając się po krawędziach możemy znaleźć ścieżkę między dowolną parą wierzchołków.
Graf pełny - jest to taki graf w którym każda para wierzchołków jest połączona pojedynczą krawędzią.
Graf acykliczny - jest to graf w którym nie występują żadne cykle, tj. nie mamy żadnej możliwości chodzenia w kółko. :)
Graf skierowany - rodzaj grafu w którym każda krawędź ma swój określony kierunek w którym możemy się po niej poruszać. Przykładowo, jeśli krawędź prowadzi od wierzchołka 2 do wierzchołka 4 to nie możemy jej wykorzystać do podróży z wierzchołka 4 do 2. ;)

Mam nadzieję, że nie muszę wyjaśniać takich pojęć jak graf niespójny, graf cykliczny czy graf nieskierowany. Liczę na waszą wrodzoną inteligencję ;)
Istnieje jeszcze wiele rodzajów grafów jednak nie będę tu ich wszystkich wyjaśniał. Wymieniłem te najważniejsze.

Inne pojęcia:
Cykl - Już przy definicji grafu acyklicznego powiedziałem czym jest cykl, jednak tutaj podam bardziej sztywną definicję. Cykl to droga zamknięta, czyli taka której pierwszy wierzchołek jest jednocześnie ostatnim. Na grafie z rysunku 1 możemy odnaleźć dwa rozłączne cykle.
Waga krawędzi - Krawędziom grafu możemy przypisywać różne wagi. Jest to jakby koszt podróży tą krawędzią.
Stopień wierzchołka - Jest to liczba krawędzi sąsiadujących z wierzchołkiem. W grafach skierowanych możemy wyróżnić stopień wchodzący i wychodzący czyli odpowiednio liczbę krawędzi prowadzących do i wierzchołka z niego wychodzących.
Sąsiad wierzchołka - Jest to wierzchołek połączony z danym wierzchołkiem pojedynczą krawędzią.

Przykłady zastosowania grafów
     No dobrze, wszystko pięknie, ale po co nam to? Rozważmy następujący problem: Jaś wraca ze szkoły. Jest bardzo zmęczony po ciężkim dniu i chciałby jak najszybciej położyć się w wygodnym łóżku. Chciałby więc dowiedzieć się jaka jest najkrótsza droga ze szkoły do domu prowadząca jedynie po wyznaczonych ścieżkach. Możemy mu powiedzieć, żeby nie marudził i zdrzemną się na jakimś kamieniu, albo możemy przedstawić ten problem w postaci grafu i w ten sposób pomóc Jasiowi w znalezieniu najkrótszej drogi do domu. ;)
     Gdybyśmy wszystkie skrzyżowania dróg w miasteczku Jasia potraktowali jako jakieś punkty, natomiast drogi jako krawędzie wychodzące z tych punktów, o wagach równych długości odpowiadających im dróg, uzyskali byśmy graf przedstawiający system dróg w miasteczku. Istnieje tzw. algorytm Dijkstry znajdujący najkrótszą drogę od dowolnego wierzchołka do wszystkich pozostałych.
     No, ale co nas obchodzi jakiś Jaś i jego problemy? Jakie korzyści nam dostarczają grafy? Otóż okazuje się, że algorytmy oparte na grafach znajdują wiele praktycznych zastosowań. Przykładowo, możliwość szybkiego wyliczenia najkrótszej drogi przez komputer jest zastosowana w samochodowych GPSach. Wiem, że większość osób czytających ten artykuł to amatorzy programowania gier. Również w tej dziedzinie grafy są nam niezwykle pomocne. Wyobraźmy sobie, że piszemy sztuczną inteligencję postaci sterowanej przez komputer i chcemy by postać ta była w stanie odnaleźć najkrótszą drogę między jakimiś punktami nie wpadając po drodze na ściany, czy inne przeszkody. Wystarczy w odpowiedni sposób przedstawić mapę gry jako graf. Analogicznie możemy zaprogramować inteligentny pocisk omijający przeszkody, albo komputerowego przeciwnika w jakiejś samochodówce.

I to by było na tyle...
     ...w tej części artykułu. Być może trochę cię zanudziłem, ale wydaje mi się, że to była ta nudniejsza część. Dalej będzie ciekawiej. W następnych częściach opiszę sposoby reprezentacji grafów w programowaniu, oraz kilka podstawowych algorytmów operujących na grafach. Czyli trochę więcej praktyki (oczywiście teorii też nie zabraknie). ;)


Przejdź do następnej części
głosów: 4 | ocena: 7.75 oceń zasób | dodał: Platyna
Komentarze
stron: 1

1


av

propaganja (12:25, 4.06.2009)

kim był dijkstra?

stron: 1

1



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

Nie masz konta? Zarejestruj się
Użytkownicy on-line
3 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 0, userów: 3, ukrytych: 0
Uzjel, I am Lord, Korodzik

3 użytkownik(ów) na gmczacie discord.com
Shoutbox
gnysek (5:57, 21.08.17):
aaaa, chodziło o mikroblog
Uzjel (19:35, 20.08.17):
Hej, statusy na razie dodałem do sekcji Aktywność forum.gmclan.or...x.php?/discover
I am Lord (15:34, 20.08.17):
Chyba że będzie to na stronie głównej zintegorowane to by było nawet lepiej
I am Lord (15:33, 20.08.17):
No mi też się to podobało
Wojo (15:14, 20.08.17):
Gmclan ma możliwość dodawania tweetów bezpośrednio na forum. Tylko, że teraz nie widać ostatnich wpisów na stronie forum, a szkoda bo to była bardzo ciekawa funkcja
Uzjel (20:54, 19.08.17):
To Twitter nie ma GMClanu!
gnysek (17:19, 19.08.17):
gmclan nie ma twittera
Threef (13:53, 19.08.17):
Nie, ty było okropne
Wojo (13:36, 19.08.17):
Oddajcie po prawej gmclanowe tweety
Chell (13:14, 19.08.17):
a symulator familiady kazdy bedzie miec w autostarcie
Korodzik (11:44, 19.08.17):
Za 5 lat obciachem w środowisku gamedevu będzie nie mieć konta na gmclanie, a jeśli ktoś nie będzie umiał wymienić z pamięci wszystkich dzieł dyzmka i rozpoznać powiedzonek bigsharka, nikt się nie będzie z nim liczył.
Korodzik (11:41, 19.08.17):
O, tak. To początek wielkiego revivalu GMClanu. Wchodzimy w nową złotą erę.
Pootkov (21:01, 18.08.17):
Czyli mam rozumieć, że akurat wchodzę w wielkie zmiany i 15 lat GMClanu?
gnysek (6:14, 18.08.17):
Stary stary? Nie. Ten sprzed 2-3 dni? tak, w stopce forum
Pootkov (21:57, 17.08.17):
wygląd forum
Pootkov (21:56, 17.08.17):
Da się jakoś zmienić wygląd na stary? Ten nowy razi w oczy
I am Lord (21:52, 17.08.17):
Ale nie działa system ligi więc będzie to w temacie tylko
I am Lord (21:52, 17.08.17):
Właściwie ligę moge zrobić
Pootkov (21:31, 17.08.17):
dawno tutaj nie byłem. Jak się tu wysyła PW, czy są jeszcze Ligi Weekendowe?
I am Lord (16:41, 17.08.17):
Powiadomienia powinny być jakoś zintegrowane ze stroną główną
Penguin (8:59, 17.08.17):
emot_poo.gif
I am Lord (19:22, 16.08.17):
Chell (16:19, 16.08.17):
Patryk, w shoutboxie jest inny zestaw emotek niz na forum
Chell (16:19, 16.08.17):
no nie, a juz sie nastawilem na okragly avatar
PatrykPlayingPOLSKA (15:17, 16.08.17):
:gnysek:
gnysek (14:25, 16.08.17):
emotki wróciły. No, sukces
gnysek (14:00, 16.08.17):
naprawiłem kodowanie forum kurde, a sie bawiłem już w wyświetlanie hexów
I am Lord (13:03, 15.08.17):
można w nim zrobić taki model i potem wyexportować warstwy spritów
I am Lord (13:03, 15.08.17):
Dobre do tej techniki są takie programy do trójwymiarowego pixel artu, zrobione ma potrzeby minecrafta
I am Lord (13:02, 15.08.17):
nakładanych na siebie ale przesuniętych w osi Y każda nowa warstwa
I am Lord (13:02, 15.08.17):
Takie udawane 3D modele składające się z warstw spritów
I am Lord (13:02, 15.08.17):
O kiedyś coś takiego robiłem
Ignatus (12:08, 15.08.17):
Jak sobie pomyśle że to jest zrobione w GM www.youtube.com...h?v=_BztMPC5Kk4 i porównam ze swoimi możliwościami to chce się płakać
I am Lord (9:23, 15.08.17):
Coś dziwnego mam. Jak odpalam zakładkę z gmc to jestem wylogowany ale po odświeżeniu strony jestem już zalogowany
gnysek (14:15, 14.08.17):
Early Access Preview ?
Ignatus (13:15, 14.08.17):
Co to jest to "GameMakerStudio 1.4.x EAP " ???
gnysek (17:33, 13.08.17):
Nie wiem czemu tematy się z UTF-8 nie konwertują :/
gnysek (17:31, 13.08.17):
@I am Lord - naprawione
Wojo (17:13, 13.08.17):
Cieszę się, że ktoś tu posłuchał słusznych rad
I am Lord (14:42, 13.08.17):
Oj klikniecie w link z Nowości w forum nie przenosi do nowego posta
Borek (12:18, 13.08.17):
*się starzeje
Borek (12:18, 13.08.17):
Uff.. bo już myślałem, że sięstarzeje
Threef (11:54, 13.08.17):
Skórka się zmieni. Najpierw wszystko musiało być przywrócone do życia
Borek (11:51, 13.08.17):
Forum zostanie w obecnej ( nowej ) wersji wizualnej?
Uzjel (11:33, 13.08.17):
Co tu się!
gnysek (9:48, 13.08.17):
ew. problemy zgłaszajcie na czacie discrodowym - link na górze
gnysek (9:32, 13.08.17):
Jeśli komuś nie działa, niech skasuje ciasteczka
gnysek (9:31, 13.08.17):
Witamy ponownie
Ranmus (18:25, 6.08.17):
Parę razy zaczynałem, i kończyło się na paru backendowych skryptach w gitlabie.
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.02482 sekund ] [ Liczba zapytań MySQL: 13 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev