[PHP]Najkrótsza droga Opcje

[daniel1302]

Witam, mam problem, chcę napisać skrypt kóry pokaże najkrótszą droge między punktem A(0,0) a punktem B(16, 4)
Niewiem jak się do tego zabrać
Z góry bardzo dziękuje

[piotrooo89]

długość odcinka na układzie współrzędnych się kłania i to bardzo nisko...

[daniel1302]

Tak, mogę spbie zrobić takie coś że liczy petla for ale co jesli chce ominac np pole
16,2 bo tam jest płot?

[piotrooo89]

jaki płot? co ty mówisz? długość odcinka to jedno a pole to drugie... wzór jest taki:

A(0,0) A(a,b )
B(16,4) B(x,y)
|AB| = sqrt((x-a)^2 + (y-b )^2)

tyle...

Ten post edytował piotrooo89 25.06.2008, 18:37:38

[Shili]

Poszukiwanie najkrótszej drogi jest algorytmem NP-trudnym, czyli ogólnie jednym z trudniejszych mozliwych do zrealizowania.

Jedyne co mi przychodzi na mysl, to uklad wspolrzednych zamienic na graf i wyznaczac to metodą wyszukiwania najkrótszej ścieżki w grafie. Między kolejnymi punktami musiałbyś nadać wagi jeden, tam gdzie pojawia się przeszkoda nie tworzyć punktu, ale do wszystkich następnych go łączących utworzyć ścieżkę z ilością "kroków" potrzebnych do obejścia.

Zawsze możesz wyszukać wszystkie ścieżki łączące dwa punkty i wybrać najszybszą, ale jest to tragicznie nieopłacalne, zajeździsz maszynę na śmierć przy większych układach.

@Piotrooo89
Ja zrozumiałam że mowa jest o poruszaniu się po liniach siatki. Tutaj autora też proszę o potwierdzenie bądź zaprzeczenie tej tezie.

Ten post edytował Shili 25.06.2008, 18:41:58

[mike]

~piotrooo89 przecież Ty nie masz zielonego pojącia o czym jest mowa.
~daniel1302 przeczytaj to Najkrótsza droga - Algorytm Mrówkowy. Znajdziesz sporo informacji, O więcej pytaj.

[daniel1302]

Tak poruszać miałbym się po układzie współrzędnych. Niechcę gotowych rozwiązań bo muszę przygotować się na konkurs informatyczny

[mike]

No to musisz poruszać się po takich zagadnieniach jak algorytm A* lub algorytm Dijkstry.
Pozostaje Ci "tylko" implementacja.

[daniel1302]

http://www.policyalmanac.org/games/aStarTutorial_pl.htm
Dziękuje za pomoc. U nas w szkole dosyć często organizowane są konkursy na wiedzę w głowie.
Mamy np 5 godzin i mamy sklecic jakis program dostęp do internetu mamy tylko do 5 mb transferu

[Shili]

Mamy np 5 godzin i mamy sklecic jakis program dostęp do internetu mamy tylko do 5 mb transferu

Przepraszam, to trochę nie na temat, ale moim zdaniem to czysta głupota - dzisiaj mamy taki dostęp do informacji, że nie ma sensu nadmiernie obciążać pamięci. Człowiek po to ma dostęp do informacji, żeby z niej korzystać. Jeśli potrafi, to ok (ale zawsze może w trakcie poszukiwań wpaść na jakąś genialnie napisaną stronę - bywają), jeśli nie - 5 mega i tak mu nie pomoże.

[daniel1302]

Ale właśnie chodzi oto iż na własną wiedzę. Jeśli chcesz możesz wnieśc do sali ile chcesz info ale na CD im chodzi oto aby uczen sam przygotowal sobie wiedze.
Teraz jest na najciekawszy skrypt konkurs w dowolnym języku 17 sob jest 4 z pozaszkoły.
Ja to posntanowiłem napisać bo widziałem w plemionach i to mnei zaciekawilo dzisiaj wiec postanowilem sie poduczyc do wrzesnia