Skrivet av RobinJacobsson:
Jag upptäckte också att jag bara fick heltal i avstånd av din kod, vilket verkar lite konstigt när man borde åka raka vägen mellan punkterna, så jag skrev om din funktion, vänligen kolla så att jag har gjort rätt!
function cost($from, $to) {
list($row1, $col1) = $from;
list($row2, $col2) = $to;
//Min kod (Pythagoras)
return sqrt(pow(abs($row2 - $row1) * 2, 2) + pow(abs($col2 - $col1), 2));
//Din kod
return max(abs($row1 - $row2) * 2, abs($col1 - $col2));
}
Skillnaden mellan din och min formel är att min optimerar efter tid och din efter distans. Det är långt ifrån uppenbart vad det verkligen gör för skillnad men tar man tex punkterna (0,0), (4,6), (1,9), (6,6) (skrivna som x,y alltså omvänd ordning från row,col) så får man två olika förslag på bästa rutt.
Din formel ger:
(0,0)->(6,6)->(4,6)->(1,9)->(0,0)
(0,0)->(6,6) time: 12 dist: 13.416407864998739
(6,6)->(4,6) time: 2 dist: 2.0
(4,6)->(1,9) time: 6 dist: 6.708203932499369
(1,9)->(0,0) time: 18 dist: 18.027756377319946
total: 38 total: 40.15236817481805
Min formel ger:
(0,0)->(6,6)->(1,9)->(4,6)->(0,0)
(0,0)->(6,6) time: 12 dist: 13.416407864998739
(6,6)->(1,9) time: 6 dist: 7.810249675906654
(1,9)->(4,6) time: 6 dist: 6.708203932499369
(4,6)->(0,0) time: 12 dist: 12.649110640673518
total: 36 total: 40.58397211407828
Ett väldigt bra hjälpmedel när man programmerar är penna och papper (eller ritplatta och tex ms whiteboard). Rita upp punkterna och tänk hur du skulle kunna köra trucken i verkligheten och hur lång tid det tar.
Förflyttningen (0,0)->(6,6) tar 12 tidsenheter eftersom du måste upp 6 våningar. Om vi förutsätter att du kan köra i max hastighet både framåt och uppåt samtidigt är du framme vid hylla 6 efter halva tiden. Du skulle kunna vända där och köra tillbaka till hylla 3 och sen vända tillbaka till hylla 6 igen innan du kommer till våning 6 på samma 12 tidsenheter.
Skrivet av RobinJacobsson:
Jag kan köra 9 noder på 13 sekunder, 10 stycken funkar inte. Då överstiger det PHP's 120 sec max gräns.
Kan jag köra 20 stycken i Python då tro? Är det så stor skillnad?
Php är tyvärr väldigt långsamt för den här typen av problem. Tiderna stämmer iofs inte riktigt med en korrekt (optimerad) implementation av Held-Karp. De borde ligga närmare 2-2.5 längre tid för varje gång du ökar antalet noder O(2^n * n^2). Jag kan absolut inget om php men utifrån koden du postat ser det ut som att en array i php är en typ av hashtable. På flera ställen skapas det strängar från två variabler som sen används för att slå upp ett värde i arrayen vilket inte är speciellt effektivt.
Den rekursiva version jag skrev i scala tar ~2 sekunder för 20 noder. Du behöver nog använda ett effektivare språk (c/c#/Java...) för storleken på problemet du har eller byta algoritm. Branch and Bound löser tsp med något fler noder och det finns flera andra algoritmer att välja på som ger en rutt som ligger väldigt nära den optimala.
Om andra språk inte är ett alternativ så är en ide att testa från andra hållet istället med enklast möjliga algoritm.
Nearest Neighbour
Du kommer oftast inte få en optimal rutt men eftersom förflyttningar i y-led dominerar kostnaden borde du ändå få en klar förbättring jämfört med sortering i x-led. Fördelen är dessutom att algoritmen är väldigt enkel.
Antingen googlar du en php version av nearest neighbour eller så har du en kort beskrivning av hur den rekursiva versionen fungerar här:
Pseudokod:
CostFn(from, to)
som tidigare
NearestNeighbour(Points, start)
Recur(start, Points - start, (start))
Recur(current, Rest, Path)
Om Rest är tom
returnera Path + start
Annars
next <- x ∈ Rest | med lägst kostnad CostFn(current, x)
Recur(next, Rest - next, Path + next)
Du har din kostnadsfunktion som fungerar på samma sätt som tidigare. Funktionen NearestNeighbour tar två argument, start som är den positionen du vill utgå ifrån och Points som är en samling av positioner (hela listan du vill besöka). Points ska tillåta att man lägger till flera positioner som har samma värde och att man tar bort en position. Den typen av samling brukar ofta kallas MultiSet eller Bag. NearestNeighbour anropar hjälpfunktionen Recur som gör allt arbete.
Recur tar tre argument, current som är den position du befinner dig vid nu, Rest som innehåller alla positioner du har kvar att besöka och Path som är rutten du håller på att bygga upp.
Det första du gör i Recur är att kolla om det finns fler positioner kvar att besöka i Rest.
Om du har besökt alla positioner så ska du bara tillbaka till starten, returnera Path med start tillagd på slutet.
Om du har positioner kvar att besöka så jämför du kostnaden mellan current och alla positioner kvar i Rest, väljer den med minst kostnad som
next och anropar Recur(next som nuvarande, Rest utan next, Path med next tillagd på slutet).
Så här skulle koden kunna se ut i ett annat språk än php:
def nearestNeighbour(points: MultiSet[(Int, Int)], start: (Int, Int)) =
def costFn(p1: (Int, Int), p2: (Int, Int)) = (p1._1 - p2._1).abs max ((p1._2 - p2._2).abs * 2)
def recur(curr: (Int, Int), rest: MultiSet[(Int, Int)], total: Int, path: Vector[(Int, Int)]): (Int, Vector[(Int, Int)]) =
if (rest.isEmpty) then (total + costFn(curr, start), path :+ start)
else
val (cost, next) = rest.map(point => (costFn(curr, point), point)).minBy(_._1)
recur(next, rest - next, total + cost, path :+ next)
end recur
recur(start, points - start, 0, Vector(start))
end nearestNeighbour