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
Akademia GMCLANu
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 (14: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: 3, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
gnysek (10:07, 18.09.18):
to tylko 40zł miesięcznie, tyle co netflix albo spotify, a jak będzie naprawdę cieżko to wywalimy uploader i do 10-15zł zjedziemy
exp (0:07, 18.09.18):
ale mi będzie smutno, jak w końcu umrze ://
exp (0:06, 18.09.18):
jestem na gmclanie połowę swojego życia
gnysek (22:43, 17.09.18):
GMCLAN ma 16 lat. iPad ma raptem 8
Wojo (18:11, 17.09.18):
GTA 5 ma już 5 lat, Shrek ma 17 lat
Wojo (18:09, 17.09.18):
1994 jest tak samo odległy od roku obecnego co 2042
exp (17:40, 17.09.18):
pojutrze miną cztery lata od premiery wasteland 2
gnysek (16:22, 17.09.18):
w 2012 w YYG pracowałem, naprawdę epokę temu
Wojo (14:02, 17.09.18):
Nie pędź tak, proszę, daj odpocząć....
gnysek (11:13, 17.09.18):
grudzień 12 i styczeń 13 jak były, dawno temu
Wojo (10:55, 17.09.18):
ja najbardziej zadowolony byłem z mortal kombat 2011 na ps3 i psvite
gnysek (9:46, 17.09.18):
Np. ostatnioe 4 miesiące były Mafia 3, God of War 3 Remastered, Destiny 2, Bound by Flame, Heavy Rain, Beyond Two Souls, Call of Duty BlackOpsIII. Więc to nie są indyki i pierdółki. No i to tylko kilka gierek, co miesiac jest 6-7.
gnysek (9:45, 17.09.18):
Zazwyczaj są 1-2 gierki AAA, które np. rok wcześniej kosztowały 250zł.
I am Lord (17:39, 16.09.18):
czy to takie popierdółki jak w humblach
I am Lord (17:39, 16.09.18):
te gierki z plusa są coś warte?
gnysek (13:07, 16.09.18):
Te gry ktore są na ps-plus.pl mam z plusa, resztę kupiłem. Czyli tak z 30-40% kupuję.
Wojo (20:24, 14.09.18):
gnysek ty masz psplus czy te gry sobie kupowales kazda z osobna?
I am Lord (20:18, 14.09.18):
może się skuszę jednak na to ps4
I am Lord (20:18, 14.09.18):
Ale fajne statystyki
gnysek (17:49, 14.09.18):
ja mam na ps4 ograne takie rzeczy: psnprofiles.com/gnysek
Wojo (17:17, 14.09.18):
Ja się zastanawiam nad kupnem PS4 aby sobie pograć w jakieś UFC, mortal kombat, fighter night ale póki co priorytety mam inne na ten moment
gnysek (10:15, 14.09.18):
No panie, tam to są gierki, Nintendo to geniusze. Mam nadzieję, ze na gwiazdkę kupię sobie switcha.
exp (23:47, 13.09.18):
ostatnio przeszedłem się z ciekawości do działu z grami w sklepie i tam cały regał gier na jakieś nintendo switch, co to wgl xd
exp (23:44, 13.09.18):
tzn. ja jak najbardziej gram, ale z branżą nie jestem zaznajomiony w żadnym stopniu, nie mam pojęcia, co teraz wychodzi i jakie konsole obecnie królują
I am vader (17:54, 13.09.18):
Tydzien temu znajomy mi powiedzial o istnieniu gry Exapunks. Nigdy niczego nie kupilem tak szybko. I nie zaluje. Ale 2 dni temu przeszedlem koncowke i znowu sie nudze
gnysek (17:36, 13.09.18):
bo trzeba fajnych gier szukać. ja to gram w rzeczy z fajną fabułą, dlatego najczęsciej RPG albo przygodowe
Sutikku (17:12, 13.09.18):
też w nic nie gram już od jakiegoś czasu, czuję się wtedy, że strasznie tracę czas, wolę coś poczytać. Gamerzy i tak będą mówić, że granie poprawia refleks i takie pierdoły żeby im nie było smutno. Jak w coś gram to w jakiegoś spokojnego multika co można pogadać z kumplem w trakcie
Wojo (12:05, 13.09.18):
pierwszy link w google "pozytywne skutki depresji". Mimo to strony prowadzone przez panie lubiące egzotycznych łobuzów nie są dobrym źródłem wiedzy. Nie wiem o ile jest to prawdą ale wydaje mi się, że to co napisał anty to prawda
ANtY (11:36, 13.09.18):
depresja nie ma pozytywnych efektow
I am vader (10:43, 13.09.18):
Moje zainteresowanie grami wypalilo sie pare miesiecy temu i nie zauwazylem jeszcze zadnych pozytywnych efektow tego zjawiska.
Wojo (10:27, 13.09.18):
i żeby nie było, nie atakuję tutaj tworzenia gier tylko granie we wszystko co popadnie zamiast wziąć się do roboty
Wojo (10:26, 13.09.18):
jak przestajesz się interesować graniem to jest dobry znak (subiektywna opinia)
exp (10:17, 13.09.18):
no może skyrim to nie jest idealny przykład, ale właśnie zdałem sobie sprawę, że już dawno przestałem interesować się grami i nie potrafię podać lepszego
exp (10:16, 13.09.18):
co nie oznacza, że wzorowanie się na formułce jest czymś złym. jeśli formułka jest dobra, to czemu mielibyśmy nie mieć więcej dobrych gier
exp (10:15, 13.09.18):
pastiszem jest np. dusk, wzorowaniem się na formułce jest skyrim
exp (10:08, 13.09.18):
to też trochę co innego
I am vader (8:41, 13.09.18):
Cliche i Trope'y
Wojo (21:19, 12.09.18):
wzorowanie się na formułce
exp (21:09, 12.09.18):
wiele obecnych gier indie można nazwać pastiszami
exp (21:08, 12.09.18):
dokładnie, parodia to nabijanie się, a pastisz to dokładne przeciwieństwo
Wojo (19:33, 12.09.18):
nabijanie się to parodia
I am vader (18:48, 12.09.18):
fachowo jak artysta chce ujść z plagiatem, mówi że to inspiracja
gnysek (13:32, 12.09.18):
w akademii będzie tryb pełnoekranowy z szeryfową dużą czcionką
gnysek (13:31, 12.09.18):
pastisz to chyba bardziej nabijanie się ?
Wojo (13:13, 12.09.18):
Dobra już mam, to pastisz jakby ktoś był ciekawy
Wojo (13:11, 12.09.18):
Powiedzcie mi jak się nazywa w sztuce naśladowanie czyjegoś dzieła? Nie chodzi mi o plagiat ani replikę tylko to się jakoś fachowo nazywało
gnysek (16:46, 10.09.18):
3 pierwsze lekcje akademii już nawet napisałem, ale jeszcze nie dam ich na stronę, wrzucę całość i wtedy ocenicie
gnysek (20:21, 9.09.18):
A od połowy biorę się w końcu za akademię
gnysek (20:21, 9.09.18):
Kończę prace nad dodaniem sezonów do Ligi24, powinny trafić do połowy września na stronę
Uzjel (17:59, 9.09.18):
Odezwę się do Ciebie
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.
[ Polityka prywatności ]
Copyright © 2002-2018. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017-2018 {=|=} fable_inside();

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