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

0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
Adriann (22:49, 23.06.17):
Łoo, pszekonał :3
Nikas (22:03, 23.06.17):
chuj kurwa gem makr zarabiaj dorary
PatrykPlayingPOLSKA (21:33, 23.06.17):
Są wakacje więc postanawiam nie zmarnować tego czasu.
I am vader (20:55, 23.06.17):
C#
I am Lord (19:40, 23.06.17):
C#
PatrykPlayingPOLSKA (19:09, 23.06.17):
Właśnie,może ktoś powiedzieć w czym zacząć pisać w Unity czy w C# czy javascript.W czym lepiej ?
ANtY (17:42, 23.06.17):
w GMie możesz programować bardzo mieszaną składnią, także zależy jak to robisz, w Unity korzystasz z C# (wcześniej dużo ludzi jeszcze z JS korzystało ale unity juz go nie supportuje na rowni z c#)
I am vader (16:54, 23.06.17):
Anty
nowy_user (12:59, 23.06.17):
Rozumiem, a czy jest na forum ktoś kto się "przebranżowił" z GMa na Unity? Sam o tym myślę, ale wiecie, to jest całkiem inny język programowania i domyślam się że wymaga to ogromu pracy...
Wojo (10:35, 23.06.17):
O tym juz pisalem ze możliwości GMa są stanowczo zbyt małe jak na dzisiejsze czasy. GM nie nadazyl za skokiem technologicznyn
nowy_user (8:53, 23.06.17):
Rzeczywiście cena lekko przesadzona. Ja oczywiście rozumiem, że ostatnio powstało sporo komercyjnych gier na GMa i domyślam się też, że włodarze Yoyo aspirują do tego, aby GM był używany przez studia developerskie, i to wszystko fajnie. Ale bądźmy szczerzy, jeśli porównamy możliwości GMa do Unity to jednak nasz kochany program jeszcze musi sporo nadgonić, więc te wysokie ceny - na ten moment- są od czapy.
Danieo (8:17, 23.06.17):
W Unity też. Jedynie musisz być zarejestrowanym developerem Sony (mieć dostęp do Devkita PS4)
Wojo (7:45, 23.06.17):
W Unreal Engine za to nie doplacasz nic. Jedynie jakiś tam procent z zysku ale myślę że to i tak jest uczciwe biorąc pod uwagę możliwości
Ignatus (23:22, 22.06.17):
3000zł z roczną możliwość eksportu na PS4 solidna cena
Uzjel (21:27, 22.06.17):
Master chyba
I am vader (21:03, 22.06.17):
Errr...czym jest Ultimate?
Threef (19:32, 22.06.17):
gnysek na Ultimate, na X1 i PS4. 3 Moduły są teraz na subskrypcję
gnysek (19:16, 22.06.17):
Subskrypcja jest tylko na Ultimate, na resztę nie.
I am Lord (19:01, 22.06.17):
Vader no tutaj na głównej: i.imgur.com/SPrqXPK.png
Threef (17:42, 22.06.17):
Na razie to info że exporty na X1 i PS4 są ważne na 12 miesięcy
I am Lord (17:41, 22.06.17):
Teraz żałuję że kupiłem go :/
I am Lord (17:40, 22.06.17):
Najpierw baitują że nie będzie subskrypcji a teraz ją wprowadzają
Adriann (17:36, 22.06.17):
Cooooooooooooo?!
Threef (17:25, 22.06.17):
Przepraszam co...? GM:S2 ma mieć teraz moduły subskrypcyjnie? Na 12 miesięcy? lol
I am vader (13:39, 22.06.17):
Nie wiem jak dotrzeć do tego działu nawet
I am Lord (11:45, 22.06.17):
im vader moj jest w assorted top down
PatrykPlayingPOLSKA (10:00, 22.06.17):
Mi się wydaje że większość gości to boty ale może być też paru ludzi,trzeba jakoś zachęcić ludzi do zarejestrowania na tym forum,np można jakoś polepszyć tą polską dokumentajcę,coś do niej dodać,na steamworkshop gamemaker można jakoś popisać że jest takie ciekawe coś jak GMC,no sposobów może być wiele.
nowy_user (9:30, 22.06.17):
Chell , aktywnych userów może i dziesięciu, ale np. w tej chwili jest 133 gości! Unbelievable! Swoją drogą , ciekaw jestem dlaczego ludzie się tak ukrywają, zamiast po ludzku się zarejestrować.
Chell (22:56, 21.06.17):
niestety sprzedawanie assetow po zlotowke na ktore zbija sie po 5 osob jest malo oplacalne na forum na ktorym jest 10 aktywnych userow
nowy_user (22:52, 21.06.17):
A może powinniśmy stworzyć własny markietplace tu na gmclanie? Ja widzę same plusy: Po pierwsze - > ceny byłyby w złotówkach, więc więcej ludzi mogłoby sobie na nie pozwolić, Po drugie -> Nie wiem jak wy, ale ja wolałbym wspierać finansowo programistę od nas , ktoś kogo znam z forumowej aktywności zamiast jakiegoś anonimowego geeka z Californi lub Colorado. I po trzecie -> Zmotywowało by to nas wszystkich do twórczości.
I am vader (22:48, 21.06.17):
A który asset jest twój? Przegrzebałem showcase i top rated i nic podpisanego HuderLord nie znalazlem
I am Lord (19:06, 21.06.17):
Aha no super, nic się na głównej nic nie zmieniło pół toku już mój asset tam jest, yoygames zapomniało że ma ten MP że go nie moderują?
I am Lord (19:04, 21.06.17):
Dawno nie zaglądałem tam
nowy_user (12:47, 21.06.17):
Przepraszam , miało być Uzjel.
nowy_user (12:47, 21.06.17):
Ujzel: Właściwie jest cała masa świetnych assetów, wczoraj odkryłem marketplace i jestem pod wrażeniem co można zrobić w GMie, od razu chciałbym kupić wszystkie A tak całkiem serio to ten asset jest obłędny: marketplace.yoy...845/text-inputs Jest demo do ściągnięcia, no po prostu miodzio, bez porównania do darmowych , zbugowanych assetów
Chell (12:47, 21.06.17):
a 1 dolc a 5 ziko to, umowmy sie, nie jest az tak kolosalna roznica
Chell (12:46, 21.06.17):
user tobie to latwo bo w tych czasach warny sa tylko za bycie botem i dziecieca pornografie
Uzjel (12:42, 21.06.17):
Punkt 5 marketplace.yoy...games.com/terms
Uzjel (12:39, 21.06.17):
A jaki asset cię interesuje?
nowy_user (12:38, 21.06.17):
A z tymi zbiórkami to też chodziło mi bardziej o uczciwe rozwiązanie względem twórcy, żeby uszanować jego pracę, tzn . nie zbiórki po 20 osób na jeden asset, a raczej dwie lub 3 osoby max. Wtedy to miałoby sens imho.
nowy_user (12:35, 21.06.17):
Za free może nie, najrozsądniej byłoby zostawić wartość liczbową niezależnie od kraju natomiast zmieniać znak walutowy dla każdego kraju z osobna tzn dany extension kosztuje 19 $ dla mieszkańców USA, tym samym 19 GBP dla mieszkańców GB, 19zł dla mieszkańców Polski i 19 Juanów chińskich dla mieszkańców Państwa Środka.
Ignatus (12:29, 21.06.17):
Hmm to idąc tym tropem tacy mieszkańcy np Egipt powinni mieć wszystkie assety za free ?
nowy_user (11:35, 21.06.17):
Dlatego pora z tym skończyć, musimy tylko dostać zielone światło od góry na założenie takiego tematu, ponieważ rejestując się tutaj obiecałem sobie, że nigdy nie dostanę ani jednego warna.
Wojo (10:57, 21.06.17):
Ale po co mają sie dostosowywać do Polaków skoro Polacy dostosuja sie do innych
nowy_user (10:30, 21.06.17):
Wiesz w kwestii uczciwości to wydaje mi się, że wszystkie ceny w markecie w dolarach powinny być 4 razy tańsze dla Polaków , ponieważ dla Amerykanina 1$ to tak jak 1 zł dla Polaka. Zdaje jednak sobie sprawę z kontrowersji, i aby uniknąć warna wolę wcześniej zapytać zanim otworzę temat z propozycją zbiórki na różne extensiony.
Ignatus (10:12, 21.06.17):
Oczywiscie ze mozna, po zbiorce siana ten ktory kupil wyeksportuje asset z projektu i przesle rzeszcie ;p Uczciwe?Niekoniecznie- ale da się na pewno
nowy_user (9:45, 21.06.17):
Mam oczywiście na myśli marketplace z twórczością użytkowników GMa a nie sam sklep z głównymi produktami yoyo
nowy_user (9:02, 21.06.17):
Hej, czy można "złożyć się" w kilka osób i kupić jakąś rzecz w yoyo markecie? czy to jest dozwolone? Pytam, bo przez to, że ceny są w $, niektóre rzeczy są po prostu drogie.
Chell (22:16, 20.06.17):
prawda, rano padł mi dotyk w telefonie a aż tak mi nie zależy na alternatywnym wizerunku żeby korespondować mailami
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.01547 sekund ] [ Liczba zapytań MySQL: 15 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev