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) | czas czytania: 4 minuty, 39 sekund
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
2 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 1, ukrytych: 0
Misiek999
Użytkownicy na czacie discord
gnysek (13:58, 18.02.19):
bo tam są głównie XMLe, wiec kazdy edytor do www się nada
gnysek (13:58, 18.02.19):
ja otwierałem w phpstormie i robiłem replace
nowy_user (13:45, 18.02.19):
BTW. Na forum YoYo coraz większe naciski ze strony użytkowników. Podoba mi się to, że użytkownicy wywierają presję na Yoyo, aby produkt i forum dalej się rozwijały. Nie podoba mi się natomiast to, że Yoyo samo nie wychodzi z inicjatywą :/
nowy_user (13:44, 18.02.19):
Dzięki za info, postaram się jeszcze pokombinować z GMEdit , może tam będzie ta opcja.
gnysek (13:28, 18.02.19):
a faktycznie, nie ma globalnego replace, to w GMS2 tylko, trzeba robić globalny find i ręcznie zmieniać
nowy_user (10:30, 18.02.19):
Niestety, w edit jest opcja Find a resource (Ctrl+R) ale to pozwala wyszukiwać np. całe obiekty sprity itd. Nie do końca mi o to chodziło. To, co ja bym chciał zrobić to np. podmienić nazwę jednej zmiennej, która jest dość nieintuicyjna, a pojawia się bardzo często, i jest porozsiewana po różnych obiektach i skryptach. Chciałbym móc podmienić nazwę tej zmiennej we wszystkich miejscach, za jednym zamachem...
gnysek (10:05, 18.02.19):
wejdź do menu "Edit" i tam chyba będzie, wraz ze skrótem.
nowy_user (9:24, 18.02.19):
Panowie, prosta sprawa, nie wiem czy czegoś nie widzę przez jakieś chwilowe zaćmienie umysłu, ale gdzie w GM1.4 jest opcja globalna 'search and replace' ? Lokalnie, dla danego obiektu pojawia sie po wciśnięciu ctrl+F , natomiast globalnie, jak wcisnę ctrl+shit+F to pojawia się sama wyszukiwarka, bez opcji replace... Chciałem zmienić nazwę jednej zmiennej, chyba nie będę musiał tego robić ręcznie?
Konrad-GM (0:12, 18.02.19):
Yup, dokładnie tak powinno chodzić, potem jest trochę więcej różnorodnych pułapek, więc robi się coraz trudniejsze
I am Lord (0:06, 18.02.19):
ale aż tak? www.youtube.com...eature=youtu.be
Konrad-GM (23:58, 17.02.19):
Ten kurczak szybko chodzi, więc to ficzer jest, żeby za łatwo nie dało się przejść gry
I am Lord (23:52, 17.02.19):
ok teraz 8, ale nie wiem czy u mnie czasem nie za szybko chodzi ten kurczak
I am Lord (23:50, 17.02.19):
5 jajaec zdobyłem
I am Lord (23:46, 17.02.19):
12 minut zostało a nie mam game playu jeszcze tylko sama grafika
I am Lord (23:46, 17.02.19):
ja nie zdąrze
Konrad-GM (23:41, 17.02.19):
Dodałem grę na ligę, ale zczaiłem się dopiero teraz, że czarny kolor to przecież też kolor kek, nie bijcie
gnysek (10:35, 15.02.19):
jak jeszcze gdzieś zostały, dawajcie znać
I am Lord (17:40, 14.02.19):
to się nie sprawdzi przy takiej małej ilości osób. Żadne posty się nie gubią tutaj w tłumie żeby je wyróżniać
I am Lord (17:40, 14.02.19):
wyłącz te oceny
gnysek (10:29, 14.02.19):
jeszcze wieczorem zajrzę w kod, jak nie znajdę żadnej opcji to wyłączę ocenianie w tych działach i tyle, i tak mało kto tego potrzebuje, to nie stackoverflow
gnysek (0:46, 14.02.19):
musiałbym chyba wyłączyć oceny
nowy_user (20:43, 13.02.19):
To prawda, jest to irytujące.
I am Lord (20:11, 13.02.19):
da się wymusić żeby to cholerne sortowanie po ocenie postu nie było domyślne? Straszliwie mnie wnerwia
gnysek (11:50, 13.02.19):
tzn. wcześniej też na forach się sporo działo, ale nie miałem internetu to nie widziałem
gnysek (11:49, 13.02.19):
Pamiętam, lata 2003-2008 to chyba takie najbujniejsze. Aż weszły facebooki i smartfony.
Temporal (17:18, 12.02.19):
jestem człowiekiem starej daty i żyje czasami, gdy wszystko działo się na forach internetowych
Temporal (17:17, 12.02.19):
wiem co to Discord, tak tylko głupoty wypisuje
I am Lord (17:12, 12.02.19):
discord to chat a nie portal społecznościowy
I am Lord (17:05, 12.02.19):
bo rozmowy się toczą na discordzie tylko
Temporal (16:51, 12.02.19):
boję się Discordów, Facebooków i Instagramów
SimianVirus7 (22:59, 11.02.19):
tu zwykle jest cicho z tego co wiem na discordzie więcej się dzieje
nowy_user (15:37, 11.02.19):
Wszyscy piszą gry, nik nie ma czasu na pogawędki
Temporal (15:33, 11.02.19):
co tu tak cicho?
nowy_user (17:20, 9.02.19):
Morał z tych historii: Róbcie backupy
Temporal (15:39, 9.02.19):
brzmi jak dobra copypasta
Konrad-GM (14:59, 9.02.19):
Kiedyś robiłem grę w Unity, crash co chwila, a potem ostatni crash usunął mi sporą część assetów w jakiś dziwny sposób, że nie mogłem odzyskać większości kodu czy modeli a kopia mocno była nieaktualna, usunąłem Unity i od tamtej pory nigdy nie wróciłem xD
I am Lord (13:52, 9.02.19):
miałem strzelankę topdown z generowanymi jaskiniami w planach
I am Lord (13:51, 9.02.19):
Ja nie oddałem na ligę bo mi crash GMS2 zepsuł projekt i się wkurzylem. Odinstalowałem go
Temporal (10:13, 9.02.19):
kiedy ten GM mi się znudzi? cały czas jestem pod wrażeniem jak dobry jest ten soft. Oczywiście ma jakieś swoje bolączki i są bardziej zaawansowane silniki, ale to wciąż doskonałe narzędzie zarówno dla początkujących twórców gier jak i zaawansowanych. Tworzenie gier w tym środowisku to sama przyjemność
gnysek (22:03, 8.02.19):
Nie wyjdzie. Jest plan na cały rok rozpisany i nie ma tam gms3. A zniżki były co roku.
nowy_user (18:22, 8.02.19):
Pojawiła się nowa promocja, Lunar Sale, nawet do 50% zniżki na GMS2 Mobile. Chyba niedługo wyjdzie GMS3, skoro co chwila nas zasypują promocjami
nowy_user (22:05, 5.02.19):
Dzięki, wyglada bardzo solidnie, chyba z niego skorzystam
gnysek (17:03, 5.02.19):
mydevil.net po tym jak hekko ceny podniosło
nowy_user (14:40, 5.02.19):
Hej, jaki niedrogi i dobry hosting polecacie do prostego landing Page’a, na którym mógłbym zaprezentować apkę zrobioną w GM? Najlepiej taki, który obsługuje WordPressa, bo bardzo do gustu przypadła mi wtyczka Elementor Page Builder
Sutikku (22:58, 4.02.19):
dziury w głowie
Sutikku (22:58, 4.02.19):
zapomniałem skończyć gierkę na lige .-.
SimianVirus7 (17:35, 4.02.19):
Myślę, że parę dobrych duszyczek by się znalazło i ufundowało nagrody. Jeśli pomysł się spodoba, ja również mogę dorzucić coś od siebie
SimianVirus7 (17:33, 4.02.19):
Można by zrobić jakiś worek gier (ale nie śmieciowych). Human: fall flat, Hollow Knight, Bioshock Inifite, Gothic Universe Edition. To wszystko dobre gry za małą cenę <20zł
Dester (17:13, 4.02.19):
nagrody na Steam na pewno były by bardzo motywujące
Dester (16:53, 4.02.19):
temat był za trudny
Ankieta
» Ile powinny trwać tury Ligi 24?
24h
48h
54h (piątek od 18:00)
7 dni
inna długość (podałem w komentarzu ankiety)

GMCLAN to serwis o programie Game Maker i nie tylko.
[ Polityka prywatności ]
Copyright © 2002-2019. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017-2019 {=|=} fable_inside();

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