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 (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
101 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 101, userów: 0, ukrytych: 0


0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
Chell (19:41, 22.03.17):
tez chetnie potestuje
owyn (14:12, 22.03.17):
Zrob aby tura zaczela sie w piatek to z checia cos zrobie
I am Lord (22:09, 21.03.17):
Co już chcecie kolejną turę?
Nikas (21:14, 21.03.17):
Nie fikaj za bardzo farfoclu!!!!
Threef (20:58, 21.03.17):
Jakieś bany trzeba dać? Bo mam dobry humor.
Threef (20:58, 21.03.17):
Oh damn! 2 tygodnie bez PC.
Wojo (20:50, 21.03.17):
za 12 godain
owyn (19:20, 21.03.17):
A kiedy kolejna tura ligi24???
Wojo (18:08, 21.03.17):
No to powodzenia tak czy inaczej
Gibki Kaktus (17:41, 21.03.17):
No ja mogę ograć XD
Nikas (16:28, 21.03.17):
Mam już grupkę testerów zawodowych z QA z mojej byłej pracy. Tutaj piszę, bo zawsze tu piszę.
Wojo (15:11, 21.03.17):
jak coś to też mogę pyknąć
Wojo (15:11, 21.03.17):
w sumie potrzebowałbyś więcej niż jednego typka z gmclanu do testów
Adriann (14:05, 21.03.17):
Ja chętnie przetestuję całość!
Ignatus (14:05, 21.03.17):
Stwierdzam własnie że nienawidze GM.Po raz n-ty w ostatnim miesiącu robie cos w grze i nagle przestaje dzialac cos co nie ma z tym żadnego zwiazku i robilem to miesiac temu.Zmieniam sobie parametry broni w grze i nagle BAM! Postac non stop kreci sie sama w kolko i nie wiem jak to zmienic.Piekny crap
Nikas (12:38, 21.03.17):
Nic nie płacę bo to są testy organizowane przeze mnie a nie AAG. Będzie miejsce w creditsach co może posłużyć jako normalny wpis do CV przy szukaniu pracy w QA. Chodzi tylko o ogranie gry, spisaniu odczuć (muszę zbalansować poziom trudności z samemu ciężko).
Gibki Kaktus (12:31, 21.03.17):
Ile płacisz? Jak >=0, to mogę ograć
Wojo (12:19, 21.03.17):
a co miałbym ci np tam spisać jakbym był chętny ?
Nikas (12:01, 21.03.17):
Szukam osoby chętnej na przetestowanie najthołxa. Tylko mówię tutaj o ograniu gry i spisaniu raportu, mam kluczyk do Steama. Ktoś chętny?
Nikas (23:14, 20.03.17):
Ale muszę przyznać, że dobra odpowiedź fervi. Szanuję.
Nikas (23:13, 20.03.17):
Tak, zobaczyłem tylko jakiś śmieszny cytat o wolności który wysłałeś i wyszedłem. xDDD ekstra gamedev
Fervi  (21:48, 20.03.17):
A co, dołączyłeś?
Nikas (11:30, 20.03.17):
Pewnie tam niezła stulejada. xDDD
Fervi  (20:39, 19.03.17):
#freegamer na freenode (dla wolnościowców, co zniechęca wiele osób )
owyn (14:05, 19.03.17):
jest jakis kanal irc nt. game-dev gdzie przesiadujecie?
Adriann (20:50, 18.03.17):
28-30 kwietnia
Wojo (20:34, 18.03.17):
a kiedy są te pyrkony ?
Gibki Kaktus (20:32, 18.03.17):
Jakim piwkiem, walimy wódę i moje urodziny oblewamy, każdy kto będzie na Pyrkonie!
I am Lord (19:55, 18.03.17):
Turmoil jest zrobiony w GMie :o
Adriann (19:41, 18.03.17):
to się skończy piwkiem, i to nie jednym:3
Ignatus (19:31, 18.03.17):
ja
Gibki Kaktus (19:25, 18.03.17):
Ja
ANtY (17:17, 18.03.17):
ja
Adriann (16:47, 18.03.17):
Miśki! Kto z was jedzie na Pyrkon?
PatrykPlayingPOLSKA (14:37, 18.03.17):
No elo Woju
Wojo (13:13, 18.03.17):
elo kuncu
Dester (15:33, 17.03.17):
Flashek (22:56, 16.03.17):
Dester robi wspaniałe gry
I am Lord (19:30, 16.03.17):
Słuchajcie bo mamy remis tutaj forum.gmclan.or...mp;#entry443228 i trzeba zrobić dogrywkę między Desterem a Chuckek, możecie napisać nowy post na kogo głosujecie? Poczekam na wyniki do północy z piątku na sobotę
Wojo (18:12, 16.03.17):
On nigdy nie odszedł. On zawsze mieszkał u nas w serduszkach
gnysek (16:43, 16.03.17):
On wrócił! Nawet nie pamietam już jaki miał nick... Paquo ?
Nikas (16:20, 16.03.17):
Jest klimat tamtych czasów, w sumie całkiem niezłe. na manieczkach, protektorze czy sunrisie by mogło wtedy hulać. xD
Ignatus (15:01, 16.03.17):
Ktos ma uszy odporne na techno-pierdy? Moje wypociny sprzed 10lat www.youtube.com...h?v=G5bWv-VBPUo
Wojo (13:42, 16.03.17):
www.youtube.com...h?v=t6PTzOClI5g kozackie rytmy. I pomyśleć, że mamy takich zdolnych userów
Wojo (13:36, 16.03.17):
Przecież tutaj rzadko kto pisze
Wojo (13:20, 16.03.17):
Szkoda, że już to forum umiera
gnysek (13:19, 16.03.17):
Ja miałem maskę admina ustawioną. Nikt więcej tak nie ma, bo Ranma zrobił porządki.
Wojo (13:17, 16.03.17):
Takich, którzy faktycznie mają rangę admina bo gnysek już jest userem a adminem był.
Ankieta
» Czy jesteś szczery odpowiadając w ankietach w Internecie?
Tak
Nie

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.01315 sekund ] [ Liczba zapytań MySQL: 15 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev