[PHP] Problem komiwojażera Opcje

[kubap007]

Witam,

Muszę napisać program wyznaczający optymalną trasę pomiędzy miastami (star i koniec w tym samym mieście), czyli typowy problem komiwojażera.
Znalazłem kilka implementacji w C++, ale niestety bardzo ciężko jest to napisać w PHP (http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol027.php).
Jest to część programu dlatego nie bardzo mam ochotę bawić się tym problemem więc będę bardzo wdzięczny za pomoc i namiar na jakąś implementacje w PHP.

[thek]

A wiesz, że problem komiwojażera jest zależny od wielu czynników? Choćby typu, formatu i ilości danych wejściowych? Człowieku... O tym napisano książki w ilościach liczonych w ogromnej liczbie tytułów. Sam podchodziłem do tego tematu wielokrotnie na studiach w zależności od rodzaju danych. Możesz dostać bowiem graf, macierz odległości, macierz odległości i wag. Po prostu problem jaki nakreśliłeś jest tak ogólny jak stwierdzenie: "Chcę skrypt do obliczania wysokości", ale bez poweidzenia czego, w jaki sposób i co mamy jako dane.

[kubap007]

Jeżeli chodzi Ci o wagi to jest to odległość pomiędzy miastami, a o książkach to bym nie przesadzał. Napisałem podobny program jak w linku załączony ale w C++, jednak nie znam podobnych możliwości (operacje na stosie (liście)) w PHP, więc szukam pomocy. Można też wykorzystać alg. genetyczne albo simulated annealing, ale to wszystko jest proste w c++ a nie w PHP.

Reasumując, dane:

- lista miast
- miasto pocz, końcowe
- odległości pomiędzy miastami

Ten post edytował kubap007 9.12.2009, 20:27:57

[seth-kk]

stos i lista to w pewnym uproszczeniu zwykle tablice

[thek]

Zauważ jednak prostą rzecz. Są grafy, gdzie nie masz podanych odległości bezpośrednio do wszystkich miast... I tak choćby by z miasta 5 dostać się do 8 trzeba przejechać przez 3 bo innej drogi nie ma. Na dodatek niektórzy dorzucają warunek, że przez jedno miasto można tylko 1 lub inną ilość razy przejechać. Takich ograniczeń może być więcej i algorytm też to musi uwzględniać jako ewentualność. W najbanalniejszym przypadku jest zwykły graf 1 do n, gdzie każdy wybór ogranicza Ci wybór kolejnego miasta na zasadzie:
wyjechałem z 1 i mogę wybrać dowolne z 9 (oprócz oczywiście 1), choćby 5,
jestem w 5 i mogę pojechać wszędzie oprócz 1(i oczywiście 5), choćby 3,
jestem w 3 i mogę jechać wszędzie oprócz 1 i 5 (oraz oczywiście 3)
... i tak dalej. A gdy już nie ma możliwości do wyboru to z tego miasta jedzie się do 1.
Po każdym przebiegu porównujesz wynik z poprzednią wartością i jeśli jest mniejsza to jest ona zastępowana wyliczoną. Tak możesz przejść przez wszystkie możliwe kombinacje To oczywiście zadanie o dużej złożoności obliczeniowej ale bardzo proste w implementacji.
Tylko jak mówiłem... Niekoniecznie będzie tym czego oczekujesz A osobiście uważam, że jeśli zna się algorytm to napisanie go w dowolnym języku nie jest trudne. Ja też siedziałem w C++ długo i uważam, że PHP jest od niego o wiele prostsze w użyciu. Każdy niemal kod w C++ można dość szybko do php "przepisać" jeśli nie tyczy to aplikacji graficznych.

@bottom: wNogachspisz... Normalnie nie wiem czy się bać czy nie tego buziaka. Nie nawykłem do całowania kogokolwiek męskiej lub nieokreślonej płci

Ten post edytował thek 10.12.2009, 08:41:34

[wNogachSpisz]

Witam

Ahhh, matma, hate it!, Semantyka -> love.

Ja bym to zrobił tak:

- Podzielił wszystkie ulice na odcinki od skrzyżowania do skrzyżowania, czyli odcinki z których nie da się skręcić
- Zebrał informacje o tych odcinach, tj:
- natężenie ruchu w zaleznosci od: pora dnia / dzien tygodnia / świeta, dni powszednie / pora roku, zima lato
- stan nawierzchni, po tej kiepskiej jedzie sie wolniej i bardziej zuzywa podzespoly pojazdu
- szerokosc jezdni, bezpieczej poruszac sie szersza jezdnia, (w tym ilosc pasów)
- to co przy drodze, chodniki, parkingi, szkoly, przejscia dla pieszych, to moze wplynac na przymus zatrzymanai sie (przepuszczenia pieszego) i bezpieczenstwa, np. wtargniecie na jezdnie
- dlugosc odcinka
- ilosc zakretow i ich kąt

Potem ważąc te informacje okreslić jakimi odcinami ajwydajniej przebyć trase.
Akgorytm powinien też się uczyć, tj zbierać z czasem informacje jak szybko udało się danym odcinkiem przejechać.

Po co ja to pisze skoro nie o to pytał autor, a autor pytał tylko o implmentacje algorytmu w PHP?
Piszę to dalego, żę autor topicu napisał również "Muszę napisać program wyznaczający optymalną trasę".
IMO "Tępe" liczenie którędy będzie szybciej moze dobrze wyląda na grafie ale kompletnie nie sprawdzi się w środowisku produkcyjnym zwanym rzeczywistością
Właśnie dlatego

ps.
thek, dobrze gadasz :*




--------
http://homehost.pl - (prawie) darmowy hosting