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
42 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 39, userów: 3, ukrytych: 0
♔ Adriann ♔ , ANtY, ediepl

0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
Wojo (12:55, 25.05.17):
Ale i tak niektórzy żyją we własnym świecie w którym Windows jest złem numer jeden
Wojo (12:50, 25.05.17):
Mam na myśli te pseudo doskonałe sposoby którymi nabijacie kabze spryciarzowi
Wojo (12:49, 25.05.17):
Ale fakt faktem znaczna większość sposobów na zarabianie w necie jest poprostu mało opłacalna. No chyba że chcecie sobie dorobić mając te szesnaście lat. Na dłuższą metę śmiesznie jest oglądać dorosłego człowieka który z klikania pół dnia w reklamy dysponuje pieniędzmi pokoju 500zl i jeszcze się rzuca
Wojo (12:46, 25.05.17):
Nawet się o taką pracę nie starałem. Twoja stara zajęła etat
Fervi  (12:26, 25.05.17):
Wiem, że za tańczenie na rurze więcej ci płacą, ale nie każdy ma takie możliwości
Wojo (8:46, 25.05.17):
500zl przy solidnej pracy xD na 500zl to mi się nawet nie chce
Fervi  (22:39, 24.05.17):
Oczywiście nie mówię, by porzucić stare strony, tylko po prostu dołączyć do kolejnej
Fervi  (22:34, 24.05.17):
Oczywiście drugiej pensi na tym nie zbudujecie, ale z 500zł przy solidnej pracy
Fervi  (22:30, 24.05.17):
Moje bitcoiny nie zgadzają się z tobą xD
Wojo (22:13, 24.05.17):
To nie zadziała. Macie moje słowo
I am Lord (21:45, 24.05.17):
tak i dać nrgeekowi do zrecenzowania :p
Fervi  (21:00, 24.05.17):
Mógłbyś Kacz De Klałna w big box produkować
Fervi  (20:58, 24.05.17):
I admini GMClanu tańczą dla twojej przyjemności, a tak to lipa, po ptokach
Fervi  (20:58, 24.05.17):
Dziwactwo, ale gdyby kopać to wtedy, to dziś mieszkasz na karaibach
Fervi  (20:57, 24.05.17):
No wiesz, cała informatyka to dziwactwo. Ot taki Bitcoin
Fervi  (20:57, 24.05.17):
W zależności jak cię ludzie lubią
Fervi  (20:57, 24.05.17):
Dostajesz kryptowalutę Steem / Steem Dollars
I am Lord (20:26, 24.05.17):
Fervex zawsze jakieś dziwactwo wynajdziesz
I am Lord (20:24, 24.05.17):
O co z tym chodzi?
PatrykPlayingPOLSKA (18:19, 24.05.17):
@Fervi Gdy wpisałem sobie Steem do przeglądarki i poczytałem co nieco,wtedy się zczaiłem że nie chodzi o Steama (falcepalm)
Fervi  (17:45, 24.05.17):
Brzmi jak dobry Scam, ale działa
Fervi  (17:45, 24.05.17):
Portal a'la Reddit, w którym płacą ci za treści (w skrócie)
Fervi  (17:45, 24.05.17):
@PatrykPlayingPOLSKA: Chodzi o Steem, nie Steam
Fervi  (17:45, 24.05.17):
@Wojo - i dobrze, ja sobie odkładam hajs ze Steem
PatrykPlayingPOLSKA (15:37, 24.05.17):
Wydaje mi się że GMC na już grupę na steamie,a nawet dwie.
Wojo (15:25, 24.05.17):
Ten pomysł brzmi tak rozsądnie jak instalacja linuxa
Fervi  (15:05, 24.05.17):
Może powinniśmy przejść na Steem / (niebawem) Strimi? Można zarobić, a przy okazji zrobić grupę gejclanu
nowy_user (8:50, 23.05.17):
Dzięki już działa, rzeczywiscie umknęła mi opcja erase a colour , jest idealna do mojego problemu
I am Lord (18:10, 22.05.17):
A tak w ogóle to gumce też można rozmiar zwiększyć, tylko że ona ma miękkie krawędzie
I am Lord (18:08, 22.05.17):
aha Opacity na 0 jeszcze
I am Lord (18:08, 22.05.17):
Masz tak się to robi: i.imgur.com/IDtZODf.png
I am Lord (18:02, 22.05.17):
Nie wierzę co czytam
Uzjel (16:35, 22.05.17):
Aj ludzie, problemy se robicie
gnysek (16:34, 22.05.17):
GIMP ma przeźroczyste tła. GMS 1.x ma funkcję "make opaque", a GMS2 ma różdżkę która zaznacza na raz 1 kolor wszędzie (contignous).
Ignatus (16:16, 22.05.17):
Wlasnie GM ma funkcje ktorej mi w programach graficznych brakuje (albo nie wiem jak znalezc) "Erase a color"
nowy_user (15:46, 22.05.17):
Zaznaczanie róźdżką też jest strasznie toporne. No nie wierzę że w gm sudio nie ma innego sposobu. Przecież są ludzie, którxy tworzą grafiki np. w gimpie lub paincie, i nine chce mi się wierzyć że za każdym razem usuwają białe tło piksel po pikselu. Przecież to niedorzeczne.
nowy_user (15:26, 22.05.17):
gm studio 1 ; ehhh w gm 5.3 nie bylo problemu , tlo bylo lewym dolnym rogiem
gnysek (15:22, 22.05.17):
Ktory GM tak w ogóle?
gnysek (15:22, 22.05.17):
To zaznacz różdzką
nowy_user (15:07, 22.05.17):
Niestety przy 100% przezroczystosci, farba ,maluje na czarno, a zaznaczenie + delete owszem działa ale tylko na prostokątnych powierzzchniach. Dalej nie działa to tak jak trzeba
ANtY (13:05, 22.05.17):
spróbuj zaznaczenie + delete, jak pomoglem to daj okejke
gnysek (11:11, 22.05.17):
To weź farbę i ustaw 100% przeźroczystą
nowy_user (11:06, 22.05.17):
tak tylko że gumką muszę tak prezycyjnie piksel po pikselu, a ja chce cały obszar ograniczony konturami, tak samo jak farbą w paincie
ANtY (10:51, 22.05.17):
gumką
nowy_user (10:09, 22.05.17):
hej , jak zamalować tło na przezroczyste w edytorze spritow w game maker?
I am Lord (15:38, 21.05.17):
site:gmclan.org w google
BloodDzioch (14:39, 21.05.17):
Gdzie na community jest jakaś wyszukiwarka? Za cholery nie mogę znaleźć
Adriann (10:36, 21.05.17):
To odpada, potrzebuję czegoś animowanego pomiędzy
Threef (10:29, 21.05.17):
Nie da się. Możesz wstawić [1] pomiędzy [0] a [2], ale żadnych obiektów nie wsadzisz. Ona mają depth, ale silnik chyba rysuje je osobno. Możesz za to rysować draw_background()
Adriann (22:53, 20.05.17):
Tznnnn chcę umieścić jakiś obiekt między backgrond[0] a [1]
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.01865 sekund ] [ Liczba zapytań MySQL: 15 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev