[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

[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