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
2 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 1, ukrytych: 0
Madness
Użytkownicy na czacie discord
I am Lord (15:10, 18.10.17):
a nie sorry nie jest
I am Lord (15:10, 18.10.17):
gms 1.4 w uploaderze moim jest
I am Lord (15:10, 18.10.17):
No ja
Sutikku (12:54, 18.10.17):
właśnie nie wiem czy gms 1.4 czy 2
PsichiX (10:59, 18.10.17):
a pamietasz do ktorej wersji GMa to bylo?
Sutikku (21:43, 17.10.17):
coś mi się pokićkało czy jakiś czas temu ktoś udostępniał tutaj przykład networkingu z TCP i UDP i chatem? Bo nie mogę znaleźć, a dałbym sobie rękę uciąć, że tak było
I am Lord (10:06, 15.10.17):
A dobra widzę teraz że ten drugi router w trybie acces point ma zablokowane opcje konfiguracji firewalla, czyli działa tylko ten pierwszego routera
I am Lord (10:04, 15.10.17):
Podłączyłem ze sobą 2 routery po kablu. Oba nadają Wifi pierwszy router funkcjonuje zwyczajnie jako router a ten drugi jako acces point i teraz pytanie czy mam 2 firewalle?
PsichiX (14:48, 11.10.17):
poprawilem
gnysek (12:50, 11.10.17):
gobarbra.com/hi...2e9735f81eacc5e dzika wixa !
gnysek (7:34, 11.10.17):
tam jest jakiś błąd javascriptowy, chyba spowodowany google analytics - po przeniesieniu serwera sie tym zajmę (czyli po weekendzie).
Ignatus (20:04, 10.10.17):
U mnie często też tak jest-i nie ładuje się w ogóle.Za którymś podejściem dopiero
PatrykPlayingPOLSKA (19:40, 10.10.17):
Czy tylko u mnie otwieranie poprzednich stron tematów trwa w nieskończoność.Nie wiem czym może być to spowodowane,ale wątpię że to przez internet,sprawdzałem na wielu urządzeniach i wszędzie się otwiera naprawdę długo.
I am Lord (15:39, 10.10.17):
DS mają swoje funkcje do zapisywania
Adriann (15:05, 10.10.17):
Nie mogę otworzyć poprzedniej strony na forum
Uzjel (12:55, 10.10.17):
Niestety, ale to jedna z tych rzeczy "o których trzeba było pomyśleć wcześniej"
Ignatus (11:40, 10.10.17):
Kurcze klapa bo nie zapisuje w ten sposob DS i wywala błedy a ze względu na dynamiczne oświetlenie nie ma w ogóle opcji żeby to ręcznie ogarnąć..Znacie jakiś dobry sytem save, nawet płatny?
Ignatus (9:21, 10.10.17):
Potrzebuje prosty save checkpoint przed spotkaniem z bossem.Powinienem wybrać game_save() ,game_save_buffer() czy coś zupełnie innego?? Zapisywanie 1000zmiennych w autorskim systemie nie wchodzi w grę bo to przerost formy.Czym się różnią te systemy?
gnysek (8:07, 10.10.17):
trzeba po prostu dać w grze opcję przekonfigurowania klawiszy na padzie
Threef (5:46, 10.10.17):
Czyli GM obsługuje to tak samo jak kierownice, drążki, joysticki i tanie pady
Threef (5:46, 10.10.17):
To jest DirectInput. Problem to tylko koniguracja klawiszy bo każda może mieć inne
PsichiX (20:38, 9.10.17):
ta mata uzywa standardowego protokolu HID z layoutem dla gamepadów - obsłużysz je tak samo, jak buttony byle pada
Ignatus (20:33, 9.10.17):
Threef: Minotour był naprawdę zabawny;p Jak ogarnąłeś matę w GM? Chyba że to nie GM..
ANtY (8:04, 9.10.17):
wybuch jak wybuch, szczegolnie jak Ignatus napisał na statycznym ssie. Ale trawa i ogólnie enviro cieniutko wygląda
Ignatus (6:13, 9.10.17):
i gdzie ta wersja do grania w zapowiedziach?
doctor (21:11, 8.10.17):
Możecie też "chore game makery znalezione przez ferviego"
doctor (21:00, 8.10.17):
Zróbcie subforum dla Enigmy, a nie
PsichiX (20:50, 7.10.17):
bedzie dzis wrzucona wersja do grania w zapowiedzi
Ignatus (20:46, 7.10.17):
ok,ale ponawiam poprzednią wypowiedź- particle można ocenić tylko w ruchu
PsichiX (18:22, 7.10.17):
nowe wybuchy media.discordap...-explosions.png
Chell (14:37, 7.10.17):
jeden z konkursow PGG nie działał to na szybko zrobiłem w gmie w 15 minut zamiennik, człowiek warga w nim udział, mój największy devowy sukces
Gibki Kaktus (20:58, 5.10.17):
Za rok
ANtY (20:15, 5.10.17):
gibki bedziesz na PGA?
Gibki Kaktus (14:33, 5.10.17):
Szkoda, że xp nie ma, jakoś najbardziej jego lubię
I am Lord (14:28, 5.10.17):
Kupiłem żeby sobie powspominać stare czasy przed game makerowe
Gibki Kaktus (14:10, 5.10.17):
O to jednak nawet funta nie wydam na to xD
gnysek (13:36, 5.10.17):
O, nowa wersja GMS2 wyszła.
gnysek (8:21, 5.10.17):
O, jednak grafiki z RTP maja licencję na użytek jedynie w RPG Makerze. Trochę sprawa
Gibki Kaktus (23:22, 4.10.17):
Aż chyba się wykosztuję i dam te niecałe 6 funtów, żeby mieć powyżej średniej xD
gnysek (21:55, 4.10.17):
Dobrze rozumiem, że skoro mam licencję na RPG Makera, to mogę jego grafiki w GM Studio użyć do własnej gry, bo mam licencję ?
I am Lord (21:45, 4.10.17):
W bundlu jest RPG maker
Chell (7:13, 4.10.17):
do uslug
Gibki Kaktus (6:58, 4.10.17):
Chell, poprawiłeś mi humor przed robotą
Chell (22:33, 3.10.17):
niewazne w sumie
Chell (22:32, 3.10.17):
niezwiazany ze wczesniejszym kontekstem
Chell (22:32, 3.10.17):
to byl tylko tescik, bo teraz mi sie przypomnialo ze bylo serduszko, ale nigdy nie pod intuicyjnym <3 tylko jakims wlasnie dziwnym
Chell (22:31, 3.10.17):
:heart:
Chell (22:31, 3.10.17):
zawsze mogłem, teraz mam większą siłę przebicia
Threef (22:00, 3.10.17):
Chell. To że jesteś w końcu częścią PGG to nie znaczy że możesz lizać tyłki innym userom gmclanu xD
Ankieta
» Jakie kursy najchętniej widziałbyś na stronie ?
GM Studio
GM Studio 2
Godot
Construct

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!
© 2002-2017 Ranmus, © 2017 {=|=} fable_inside();

[ Czas generowania strony: 0.01914 sekund ] [ Liczba zapytań MySQL: 13 ]