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
41 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 37, userów: 4, ukrytych: 0
♔ Adriann ♔ , Suekii, ALT, I am vader

0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
Suekii (18:58, 26.04.17):
Spelunky kojarzycie?
Flashek (18:46, 26.04.17):
każdy pierwszy program będzie dobry jeżeli tylko użytkownik sobie z nim radzi
I am vader (18:41, 26.04.17):
Bywają dobre gry w rpgmakerze..na przyklad ten, no..... Ahriman's Prophecy!
I am Lord (18:16, 26.04.17):
i nie chodzi mi o tego: www.adventuremaker.com tamten program potrafił tylko wyświetlać tekst i odpowiedzi
I am Lord (18:15, 26.04.17):
a nie, wcześniej tknąłem jakiś adventure maker i to był edytor gier tekstowych.
I am Lord (18:14, 26.04.17):
no bardzo fajna zabawka była to w nim poznałem czym są zmienne :d
I am Lord (18:14, 26.04.17):
Ja zaczynałem w rpg makerze 2000
Uzjel (18:13, 26.04.17):
Ej, Ja zaczynałem w RPG Makerze i bardzo dobrze go wspominam To tylko narzędzie, jak każde inne.
Suekii (18:08, 26.04.17):
rpg maker to zabawka dla dzieci w podstawówce.
I am vader (16:41, 26.04.17):
Mam chyba 50 gównogierek z rpgmakera na koncie bo kazde kostowalo 10 centow. Zadne nie jest dobre.
Kotekhh (16:18, 26.04.17):
rpg maker rządzi chłopcy
Flashek (16:09, 26.04.17):
Pamiętam moją pierwszą grę na androida, to była istna masakra. Autko wypierdzielało mi w kosmos. Tekstury były zniekształcone jak w jakimś psychologicznym horrorze. Jak znajdę to ci wyślę gdzieś na chomikuju mam obok modyfikowanych biosów )
dxdiag (16:07, 26.04.17):
praktycznie wszystko współdziała z tym cackiem
dxdiag (16:06, 26.04.17):
ale plusem jest kompatybilność
dxdiag (16:05, 26.04.17):
Nie tylko
Flashek (16:05, 26.04.17):
Z tego co czytałem to Ue3 to zabawa światłem głównie
Flashek (16:04, 26.04.17):
Domyślam się
dxdiag (16:03, 26.04.17):
HDR jest genialne
dxdiag (16:03, 26.04.17):
ja na trójce robiłem bardzo długi czas
dxdiag (16:01, 26.04.17):
w unrealu tez masz wady poważne
dxdiag (16:00, 26.04.17):
powiem ci ze generalnie w unity nie ma na co narzekać tylko trzeba się przyzwyczaić do interfejsu
Flashek (15:59, 26.04.17):
niby ten silnik i ma wiele fajnych zastosowań ale szczerze mam dość pierdzielenia się z tą optymalizacją
Flashek (15:58, 26.04.17):
ja ostatnio robiłem w unity ale mi ręce opadły
I am Lord (15:55, 26.04.17):
Dester widzę że bardzo ci zależy na tej wygranej sprowadzając kolegów haha
dxdiag (15:31, 26.04.17):
robię nowy projekt w unreal
dxdiag (15:30, 26.04.17):
Siemka
Wojo (15:27, 26.04.17):
No tu ci przyznam rację
Kotekhh (15:12, 26.04.17):
nie ma to jak po 12 godzinach legnąć się w łożu
Wojo (15:04, 26.04.17):
Ja zaraz kończę
Suekii (13:20, 26.04.17):
Dzisiaj nockę walę więc jeszcze sporo luzu a tam ?
Kotekhh (13:13, 26.04.17):
Jak tam ludziska, w robocie co ?
Wojo (10:57, 26.04.17):
Zgadzam się
Flashek (8:17, 26.04.17):
Tche Witcher Tchree to jakaś porażka
Flashek (8:16, 26.04.17):
Danielos Monater Energy
Wojo (8:16, 26.04.17):
Zawsze był
PatrykPlayingPOLSKA (23:09, 25.04.17):
Witcher jest darmowy,arstechnica.co....mes-partnership
I am Lord (21:04, 25.04.17):
Jest dogrywka między Destem a Hamtarenem, będę liczył głosy napisane w postach w temacie głosowania do tury #158. Podliczam w czwartek jak będę przy kompie.
Gibki Kaktus (0:49, 25.04.17):
Ja będę!
I am Lord (18:41, 24.04.17):
Ok linki wrzucę
Threef (18:30, 24.04.17):
I wrzuć może linki w jeden post
I am Lord (18:24, 24.04.17):
Goście mogą głosować w ankiecie?
I am Lord (18:23, 24.04.17):
Trzeba zrobić regulamin albo jakieś zasady
Threef (17:53, 24.04.17):
Lord napisz może że głos liczony tylko jako komentarz
I am vader (16:48, 24.04.17):
Gnysek Kek
gnysek (16:21, 24.04.17):
@Wojo: Pyrkon chyba w ten weekend.
gnysek (16:20, 24.04.17):
nastąpiła frykcja między użytkownikami
Dester (16:09, 24.04.17):
ale poleciał offtopic w pytaniach początkujących
Wojo (8:27, 24.04.17):
A kiedy jest?
Adriann (8:19, 24.04.17):
Ja!
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.01939 sekund ] [ Liczba zapytań MySQL: 15 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev