Traveling Salesman 2d/3d

Skrivet av RobinJacobsson:

Och "Ingetledigtnamn", det är nog som du säger att man åker ju egentligen inte rakt mot punkten, utan stannar på en axel och kör resterande sträcka längs med den andra axeln. Detta är ju omöjligt att beräkna och jag antar att man kan se den exakta beräkningen som en medelsträcka.

Det är precis det vi räknat på genom att använda max av |p1.x - p2.x| och |p1.y - p2.y|.

Det finns flera olika sätt att räkna avståndet/kostnad beroende på hur man kan röra sig.

Δx = punkt1.x - punkt2.x
Δy = punkt1.y - punkt2.y

L1-norm/manhattan-norm:
Man kan röra sig i antingen x-led eller y-led men inte båda samtidigt.
|Δx| + |Δy|

L2-norm/euklidisk-norm:
Man kan röra sig fritt i vilken riktning som helst som i en cirkel ut från startpunkten. (pytagoras på en 2d karta)
sqrt(Δx^2 + Δy^2)

L∞-norm/max-norm/Chebyshev.
Man kan röra sig i x-led och y-led och kan röra sig i båda samtidigt. Diagonalförflyttningar kostar inte extra. Det är så trucken i den här tråden rör sig och t.ex. kungen på ett schackbräde
max(|Δx|, |Δy|)

Det finns ett till ganska vanligt sätt man använder i datorspel som använder rutnät och tillåter x-led eller y-led eller 45 graders diagonal mellan två rutor. Diagonalförflyttningen kostar extra.
max(|Δx|, |Δy|) + (sqrt(2)-1) * min(|Δx|, |Δy|)

Skrivet av RobinJacobsson:

Tack för era svar, det visade sig att mjukvaran vi använder inte går att manipulera på så sätt att man kan anpassa plocklistorna, dom sorteras automatiskt och vi kan inte påverka det på något sätt. (say no more...)

Det går att lösa problemet manuellt utan programmering. Om du skrev ut plocklistorna som punkter och ritar rutterna för hand helt utan att räkna så kommer du hamna väldigt nära optimal rutt så länge rutten ser bra ut. Det svåra blir väl att på ett effektivt sätt välja din lista istället för den automatiska. Det skulle vara enbart för att mäta hur stor effekt en bättre sortering har i verkligheten. Ibland kan det vara lättare att få genom en förändring om man kan presentera siffror.
Hur stor del av totala tiden det tar att plocka en lista är förflyttning och hur stor del är att man står stilla vid en hylla och plockar? Om det är 50/50 så skulle en optimal lista ge 25% effektivisering. Om bara en liten del av tiden går åt till förflyttning så spelar det i princip ingen roll hur optimerad rutten är.

@Yoshman: Jag måste återigen tacka för den stora hjälpen att ta fram koden! Jag är inte alls bekant med Python eller Go, men jag har installerat Visual Studio Code och även Go-miljön och det verkar fungera så långt. Jag har även pressat in din kod i ett projekt, men jag förstår inte hur jag ska infoga koordinat-matrisen. Vore tacksam om du vill vägleda mig!

Får jag gissa att det ska in

func GetCostMatrix() CostMatrix { if len(os.Args) == 1 { return readMatrix(här?) } arg := os.Args[1] if strings.HasSuffix(arg, ".csv") { file, err := os.Open(arg) if err != nil { log.Fatalln(err) } return readMatrix(eller här?) } dim, err := strconv.ParseInt(arg, 10, 32) if err != nil { log.Fatalln(err) } return genMatrix(int(dim), 50, 9) }

Skrivet av RobinJacobsson:

@Yoshman: Jag måste återigen tacka för den stora hjälpen att ta fram koden! Jag är inte alls bekant med Python eller Go, men jag har installerat Visual Studio Code och även Go-miljön och det verkar fungera så långt. Jag har även pressat in din kod i ett projekt, men jag förstår inte hur jag ska infoga koordinat-matrisen. Vore tacksam om du vill vägleda mig!

Får jag gissa att det ska in

func GetCostMatrix() CostMatrix { if len(os.Args) == 1 { return readMatrix(här?) } arg := os.Args[1] if strings.HasSuffix(arg, ".csv") { file, err := os.Open(arg) if err != nil { log.Fatalln(err) } return readMatrix(eller här?) } dim, err := strconv.ParseInt(arg, 10, 32) if err != nil { log.Fatalln(err) } return genMatrix(int(dim), 50, 9) }

Konvertering från koordinater till kostnadsmatris är ju inte det minsta prestandakrävande. Så nog bäst att du skriver det i något som känns bekvämt.

I koden ovan går man in i första if-kroppen om det inte finns några argument. I det läget läser program in koordinaterna från stdin.

Man går in i if strings.HasSuffix(arg, ".csv") { om argumentet är en sträng som slutar på .csv

Om inget av ovan är sant hamnar man i sista delen som genererar en slumpmässig matrix.

Ok, men hur skulle koden se ut om jag har en .csv fil med avstånd som jag vill implementera i din kod? Dvs hur skulle det se ut exakt att skicka med det argumentet? Har några timmar över ikväll, så det vore kul om jag kunde få igång det och skaffa en uppfattning om vilken skillnad det blir i förflyttning och om det är värt att göra om listorna

Så då kan jag göra avståndsmatrisen i PHP likaväl som jag gör nu, men ändra koden så att den sparas i .csv istället?

Kan du klargöra en annan sak, Python och Go är inte kompilerbar kod som skapar tex en .exe? Är det mer likt PHP som serverspråk riktat mot tex webbsidor? Hur kompilerar jag koden/får ut den från visual studio code? Många konstiga frågor kanske

Den listan jag skickade var ganska extrem, men de flesta listor går att förbättra. Jag tänkte kolla lite tider på jobbet också, bland annat hur stor del själva åkningen utgör av hela momentet.

Skickades från m.sweclockers.com

Senast redigerat 2019-11-01 08:46

@RobinJacobsson: python3 namnet_på_ditt_program.py namnet_på_din_csvfil.csv

Du menar att jag skriver detta i cmd och att den tar .csv som ett argument i programmet på detta vis?

Jag kan inte se att man anropar main() någonstans i koden..? Eller definerar den här koden funktionen OCH anropar den?

func main() { c := GetCostMatrix() fmt.Println(c) fmt.Println(c.ShortestPath()) }

Hur kör jag annars ett python/go program jag skrivit?
I PHP är jag van att presentera data via en hemsida/html och inte kompilera kod. Är python/go liknande PHP på så vis att man inte kompilerar koden? Och hur är lättast att presentera den data programmet output'ar? I en console miljö, eller hemsida osv?

Hoppas att jag gör mig förstådd i en frågeställning gällande något jag inte är familjär med.

Edit: Det blir nog lättast för mig om jag använder PHP. Jag hittade shell_exec() som borde kunna köra ett cmd-kommando om jag förstår dig rätt, skulle detta kunna funka då (om det är på detta sättet jag kör en .go kod)

shell_exec('$ go run heldkarp.go 2dmatrix.csv');

Isåfall behöver jag bara ha en fil med Yoshman's kod i en .go fil, generera 2d kartan i PHP och sedan presentera datan i PHP.
På så vis behöver jag egentligen inte ha så mycket med varken Go- eller Python att göra för tillfället.

Skickades från m.sweclockers.com

Senast redigerat 2019-11-01 13:00
Skrivet av RobinJacobsson:

Du menar att jag skriver detta i cmd och att den tar .csv som ett argument i programmet på detta vis?

Jag kan inte se att man anropar main() någonstans i koden..? Eller definerar den här koden funktionen OCH anropar den?

func main() { c := GetCostMatrix() fmt.Println(c) fmt.Println(c.ShortestPath()) }

Du man i praktiken förutsätta att om du ser programkod med en funktion med namnet main så anropas den funktionen "automagiskt" när programmet körs. Det gäller för bl.a. C/C++/Go/Rust. Samma saker gäller i princip även för C#/Java.

För skriptspråk som Python körs filen från toppen. I Python-program ser man ofta denna konstruktion som har motsvarande funktion som main

# Kan egentligen heta vad som helst def main(): print("Hello World!") # denna text blir sann om detta är Python-filen som körs av en användare if __name__== "__main__": # Kan egentligen vara vad som helst här, anrop till main() gör det likt t.ex. Go main()

Skrivet av RobinJacobsson:

Hur kör jag annars ett python/go program jag skrivit?
I PHP är jag van att presentera data via en hemsida/html och inte kompilera kod. Är python/go liknande PHP på så vis att man inte kompilerar koden? Och hur är lättast att presentera den data programmet output'ar? I en console miljö, eller hemsida osv?
Hoppas att jag gör mig förstådd i en frågeställning gällande något jag inte är familjär med.

Edit: Det blir nog lättast för mig om jag använder PHP. Jag hittade shell_exec() som borde kunna köra ett cmd-kommando om jag förstår dig rätt, skulle detta kunna funka då (om det är på detta sättet jag kör en .go kod)

shell_exec('$ go run heldkarp.go 2dmatrix.csv');

Isåfall behöver jag bara ha en fil med Yoshman's kod i en .go fil, generera 2d kartan i PHP och sedan presentera datan i PHP.
På så vis behöver jag egentligen inte ha så mycket med varken Go- eller Python att göra för tillfället.

Skickades från m.sweclockers.com

Nu är Go specifikt designat för kunna kompileras så fort att det upplevs som en skriptspråk som saknar kompileringssteg. Så går fint att köra programmet på det sättet du visar ovan.

Men egentligen är tanken att "go run" primärt är något som används vid utveckling av program, när man är nöjd kan skapar man en fil som är direkt körbar på detta sätt

go build heldkarp.go

om du kör Windows skapas då en heldkarp.exe

@Yoshman: Okej, tack för att du klargör det!

Låter det rimligt att jag gör en .exe av din kod och anropar filen i PHP och skickar med min avståndsmatris som ett argument? Är det ens möjligt? Som jag skrev innan tex

shell_exec('$ go run heldkarp.go argument');

där argumentet skulle kunna vara en avståndsmatris som jag genererar i PHP?
Eller en .csv som jag redigerar i PHP kanske vore smidigare?

shell_exec('$ go run heldkarp.go 2dmatrix.csv');

Hur skulle då din kod behöva se ut och hur skulle jag behöva formattera 'argument'?
Nu har jag testat att infoga din kod i en fil som heter heldkarp.go i Visual Studio Code, men när jag ska bygga det så händer det ingenting. Jag får inga errors vad jag kan se, det skapas heller inte någon .exe och jag får ingen output i consolen.

Jag har skapat en .exe av din kod men den visar ingenting när jag kör den. Testade även att lägga till print("hej") sist i main-funktionen men jag ser bara ett helsvart cmd-fönster.

Senast redigerat 2019-11-02 13:57

Nu har jag äntligen fått igång det. Informationen jag behövde var att jag måste skapa en .csv fil med avstånd avskiljt av komma (,).
Och att jag sedan förväntas anropa det i cmd: go run heldkarp.go map.csv

Jag har gjort det och får följande resultat med testsiffror:

{ { 1, 2, 3, 4, 8, 9, 6, 1, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 5, 6, 7, 8, 1, 5, 8, 9, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 9, 10, 11, 12, 2, 3, 4, 5, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 13, 14, 15, 16, 1, 5, 6, 7, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 1, 2, 3, 4, 7, 1, 2, 3, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 5, 6, 7, 8, 5, 20, 33, 41, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 9, 10, 11, 12, 9, 8, 7, 6, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 13, 14, 15, 16, 9, 8, 7, 6, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 1, 2, 3, 4, 8, 9, 6, 1, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 5, 6, 7, 8, 1, 5, 8, 9, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 9, 10, 11, 12, 2, 3, 4, 5, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 13, 14, 15, 16, 1, 5, 6, 7, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 1, 2, 3, 4, 7, 1, 2, 3, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 5, 6, 7, 8, 5, 20, 33, 41, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 9, 10, 11, 12, 9, 8, 7, 6, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 13, 14, 15, 16, 9, 8, 7, 6, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 1, 2, 3, 4, 7, 1, 2, 3, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 5, 6, 7, 8, 5, 20, 33, 41, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 9, 10, 11, 12, 9, 8, 7, 6, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 13, 14, 15, 16, 9, 8, 7, 6, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 13, 14, 15, 16, 9, 8, 7, 6, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, { 13, 14, 15, 16, 9, 8, 7, 6, 90, 10, 20, 30, 40, 50, 60, 70, 1, 2, 3, 4, 20, 20 }, } 439 [0 7 21 20 19 18 17 15 14 13 11 9 10 6 16 2 5 12 3 8 1 4 0] Processen tog 4.4438159s sekunder

Med 22 avstånd/noder får jag ovanstående tid. Kan det stämma, jag tycker att det borde ta längre tid att beräkna?
Har en i9 dock. Eller är det att räkna ut avstånden mellan noderna som tar mycket processorkraft?

Och förresten, när jag skriver "go run heldkarp.go" utan en .csv fil som argument så händer det ingenting.

@RobinJacobsson
Vad förväntar du dig ska hända om du inte ger argument?

Skrivet av Shimonu:

@RobinJacobsson
Vad förväntar du dig ska hända om du inte ger argument?

genMatrix()?

Skickades från m.sweclockers.com

Skrivet av RobinJacobsson:

Och förresten, när jag skriver "go run heldkarp.go" utan en .csv fil som argument så händer det ingenting.

Någon som kan förklara varför det blir så?

Sedan har jag ett annat problem. Jag kan köra koden i cmd, men jag kan inte anropa den i PHP exec('go run test.go map.csv');

<?php $output = []; exec('go run c:/Go/src/hello/test.go c:/Go/src/hello/map.csv', $output); var_dump($output); ?>

Jag har testat exec(), shell_exec(), system() och olika sökvägar till filerna, men jag får alltid 0 tillbaka, array empty.

Så, nu har vi löst ännu ett problem.

<?php $output = []; $cmd = 'C:/go/bin/go run c:/Go/src/hello/test.go map.csv 2>&1'; exec($cmd, $output, $return_var); var_dump($output); ?>

Det är alltså en "go.exe" man hänvisar till när man skriver "go run program.go", efter att ha lokaliserat och skrivit in rätt sökväg så funkar det och all data presenteras som den ska på min hemsida.

Nu har jag en annan fråga, @Yoshman.
Vad gör denna funktionen? Jag räknar ju själv ut avstånd i min PHP-kod (den tunga belastningen är väl i själva sökningen efter den billigaste vägen?).

func cost(from, to Location) int { dx := Abs(from.shelf - to.shelf) dy := Abs(from.level-to.level) * 2 return Max(dx, dy) }

Jag har gjort om avståndsmatrisen så att den räknar exakt avstånd med hjälp av Pythagoras sats, vilket innebär att avstånden helt plötsligt blir i decimaltal.

function genPoints($inputb) { $width = count($inputb[0]); $height = count($inputb); $points = []; $counter = 0; for($row=0; $row < $height; $row++) { for($col=0; $col < $width; $col++) { if($inputb[$row][$col] == 1) { $points[] = array($row, $col);//[$row, $col]; $counter++; } } } return $points; } function cost($from, $to) { list($row1, $col1) = $from; list($row2, $col2) = $to; return sqrt(pow(abs($row2 - $row1) * 2, 2) + pow(abs($col2 - $col1), 2)); //return max(abs($row1 - $row2) * 2, abs($col1 - $col2)); } function genGraph($points) { $sz = count($points); $matrix = []; for($from=0; $from < $sz; $from++) { for($to=0; $to < $sz; $to++) { $matrix[$from][$to] = cost($points[$from], $points[$to]); } } return $matrix; }

Är det fel att räkna såhär? Den klagar då såhär på din Go-kod iallafall:

C:\wamp64\www\hkgo.php:5: array (size=2) 0 => string '2019/11/04 20:49:30 strconv.ParseInt: parsing "2.2360679774998": invalid syntax' (length=79) 1 => string 'exit status 1' (length=13)

Senast redigerat 2019-11-04 20:54
Skrivet av RobinJacobsson:

Någon som kan förklara varför det blir så?

Sedan har jag ett annat problem. Jag kan köra koden i cmd, men jag kan inte anropa den i PHP exec('go run test.go map.csv');

<?php $output = []; exec('go run c:/Go/src/hello/test.go c:/Go/src/hello/map.csv', $output); var_dump($output); ?>

Jag har testat exec(), shell_exec(), system() och olika sökvägar till filerna, men jag får alltid 0 tillbaka, array empty.

Det händer "inget" när inga argument specificerad då programmet då förväntar sig att kostnadsmatrisen ska skrivas på stdin (d.v.s. skickas från ett annan program eller skrivas in manuellt i terminalen).

Skrivet av RobinJacobsson:

Så, nu har vi löst ännu ett problem.

<?php $output = []; $cmd = 'C:/go/bin/go run c:/Go/src/hello/test.go map.csv 2>&1'; exec($cmd, $output, $return_var); var_dump($output); ?>

Det är alltså en "go.exe" man hänvisar till när man skriver "go run program.go", efter att ha lokaliserat och skrivit in rätt sökväg så funkar det och all data presenteras som den ska på min hemsida.

Nu har jag en annan fråga, @Yoshman.
Vad gör denna funktionen? Jag räknar ju själv ut avstånd i min PHP-kod (den tunga belastningen är väl i själva sökningen efter den billigaste vägen?).

func cost(from, to Location) int { dx := Abs(from.shelf - to.shelf) dy := Abs(from.level-to.level) * 2 return Max(dx, dy) }

Jag har gjort om avståndsmatrisen så att den räknar exakt avstånd med hjälp av Pythagoras sats, vilket innebär att avstånden helt plötsligt blir i decimaltal.

function genPoints($inputb) { $width = count($inputb[0]); $height = count($inputb); $points = []; $counter = 0; for($row=0; $row < $height; $row++) { for($col=0; $col < $width; $col++) { if($inputb[$row][$col] == 1) { $points[] = array($row, $col);//[$row, $col]; $counter++; } } } return $points; } function cost($from, $to) { list($row1, $col1) = $from; list($row2, $col2) = $to; return sqrt(pow(abs($row2 - $row1) * 2, 2) + pow(abs($col2 - $col1), 2)); //return max(abs($row1 - $row2) * 2, abs($col1 - $col2)); } function genGraph($points) { $sz = count($points); $matrix = []; for($from=0; $from < $sz; $from++) { for($to=0; $to < $sz; $to++) { $matrix[$from][$to] = cost($points[$from], $points[$to]); } } return $matrix; }

Är det fel att räkna såhär? Den klagar då såhär på din Go-kod iallafall:

C:\wamp64\www\hkgo.php:5: array (size=2) 0 => string '2019/11/04 20:49:30 strconv.ParseInt: parsing "2.2360679774998": invalid syntax' (length=79) 1 => string 'exit status 1' (length=13)

Kostnadsfunktionen lade jag bara in för att kunna generera slumpmässigt skapade kostnadsmatriser, den har ingen funktion i ditt fall.

Felet du får i slutet kommer av att programmet just nu förväntar sig en kostnadsmatris som består av heltal. Behövs lite modifiering om det ska vara flyttal (dock ingen större manöver).

Kan jag i princip byta ut alla int mot float? Eller har du tid att göra den ändringen åt mig? Tack!

Skickades från m.sweclockers.com

@RobinJacobsson: Pröva? Fungerar det så fungerar det. Fungerar det inte så fungerar det inte. Du kan ju börja med att ändra på de ställen du själv tycker vore lämpligt. Man lär sig av att försöka själv.

Självklart, men vet man vad som behöver ändras och det inte är mer än ett par knapptryckningar bort för att informera mig så vore jag såklart tacksam för info.

Skickades från m.sweclockers.com

@RobinJacobsson:
Du har fortfarande inte helt förstått hur problemet du försöker lösa ser ut och fungerar. Resultat blir att du försöker få nån annan att slösa tid på en lösning som är felaktig.

Jag har förklarat flera gånger hur du ska räkna kostnaden och det finns flera kodexempel på kostnadsfunktioner, ändå envisas du med att skriva om fullt fungerande kod till att använda pytagoras vilket är fel sätt att räkna i det här fallet.

Om vi förenklar truckens rörelse till att ha samma hastighet åt båda hållen för att göra det lättare att tänka och visualisera. Du kan ta ett steg åt sidan eller ett steg upp/ner eller göra båda förflyttningarna samtidigt. Gör du båda förflyttningarna samtidigt så hamnar du en hylla och en rad bort på samma tid det tar att förflytta sig en hylla eller en rad. Det är lika långt att förflytta sig ett steg diagonalt som det är att ta ett steg åt sidan eller upp/ner.
Jämför med kungen på ett schackbräde. Det finns upp till åtta rutor runt nuvarande position. Det är lika långt till varje, 1 steg inte 1.414 steg. En diagonal förflyttning från hörn till hörn är 8 steg inte lite drygt 11 som du vill få det till.

Om du tycker att max(|Δx|, |Δ|) ser för enkelt ut och vill ha nåt som ser ut som pytagoras så kan du använda gränsvärdet (|Δx|^p + |Δy|^p)^1/p när p->∞ (gör det några gånger så förstår du var max(|Δx|, |Δ|) kommer ifrån)

Du har även nåt annat fel i koden för att räkna fram kostnadmatrisen eftersom matrisen du postade ser helt fel ut. Kostnadsfunktionen är kommutativ och positionernas avstånd till sig själva är 0. Alltså ska matrisen vara symmetrisk och ha 0 som diagonal.

Jag ber om ursäkt, men jag förstår inte riktigt helt tänket ändå. Om jag tar sträckan i X-led / hastigheten i X-led så får jag ju tidsåtgången det tar att förflytta sig en viss sträcka i X-led. Gör samma sak i Y-led och räkna ut Pythagoras på båda kateterna. Då får jag ju den absoluta förflyttningen från en punkt till en annan. Men jag kanske har stirrat mig för blind på detta så det gör det svårare för mig att förstå din förklaring.

Jag förstår ju att om jag rör mig 1 x och 1 y så blir förflyttningen i både x och y 1 givetvis, men sammanlagda sträckan jag har färdats är ju 1,414?

Skickades från m.sweclockers.com

Skrivet av RobinJacobsson:

Jag ber om ursäkt, men jag förstår inte riktigt helt tänket ändå. Om jag tar sträckan i X-led / hastigheten i X-led så får jag ju tidsåtgången det tar att förflytta sig en viss sträcka i X-led. Gör samma sak i Y-led och räkna ut Pythagoras på båda kateterna.
Skickades från m.sweclockers.com

Pythagoras ger avståndet för "fågelvägen". Vill du ha det, dvs om du kan flytta dig rakt igenom hyllor, etc. så kan du använda det.

Edit: Inte läst mig igenom hela tråden så jag kanske missförstått vad som är problemet.

Jo men det är ju så jag rör mig, jag rör mig inte i block.
Denna kartan simulerar ju en hylla ståendes. Jag rör mig i två led samtidigt och mellan hyllplatser. Jag behöver inte passera centrum för en plats utan jag rör mig ju "fågelvägen" men sett från sidan.

Skickades från m.sweclockers.com

@RobinJacobsson:
Försök att tänka bort absoluta avstånd i meter, pytagoras och hastigheter.

Se problemet som två helt oberoende förflyttningar i x-led och y-led som du kan göra samtidigt.

Citerar dig: "Och "Ingetledigtnamn", det är nog som du säger att man åker ju egentligen inte rakt mot punkten, utan stannar på en axel och kör resterande sträcka längs med den andra axeln."

Tänk dig att ni är tre personer i trucken.
Plockansvarig som får koordinater till en plockplats.
Radansvarig som bara ser till att ta sig till rätt rad.
Hyllansvarig som bara ser till att ta sig till rätt hylla.

Ni befinner er på position 0,0 och plockansvarig får i uppdrag att plocka från rad 8 och hylla 4.
Den som är hyllansvarig får bara informationen att ta sig till hylla 4 så snabbt som möjligt. Vilken rad man ska ta sig till påverkar inte alls och tvärtom för den som är radansvarig. Båda börjar göra sina förflyttningar samtidigt helt oberoende från varandra. Efter 4 sekunder meddelar hyllansvarig att nu är jag framme nu går det att plocka för min del. Den som är plockansvarig måste dock vänta på klartecken att man är framme vid både rätt hylla och rätt rad. Viket man är efter totalt 8 sekunder när den som är radansvarig också genomfört hela sin förflyttning.
Man gör alltså inte en förflyttning diagonalt utan två separata förflyttningar. En mellan rader och en mellan hyllor, men man gör de samtidigt.
Det är därför den förflyttning som tar längst tid styr helt och man inte behöver tänka på diagonaler.

Skrivet av RobinJacobsson:

Jag ber om ursäkt, men jag förstår inte riktigt helt tänket ändå. Om jag tar sträckan i X-led / hastigheten i X-led så får jag ju tidsåtgången det tar att förflytta sig en viss sträcka i X-led. Gör samma sak i Y-led och räkna ut Pythagoras på båda kateterna. Då får jag ju den absoluta förflyttningen från en punkt till en annan. Men jag kanske har stirrat mig för blind på detta så det gör det svårare för mig att förstå din förklaring.

Jag förstår ju att om jag rör mig 1 x och 1 y så blir förflyttningen i både x och y 1 givetvis, men sammanlagda sträckan jag har färdats är ju 1,414?

Skickades från m.sweclockers.com

Fast nu är ju förändringar i X-led och Y-led helt oberoende av varandra.

Om du tänker dig att du börjar på platsen som är längst ner till vänster (x=1 och y=1) i din gång och nästa plats du ska till är längst bort på andra sidan gången, och en våning upp (x=8 och y=2). Eftersom trucken kan färdas i båda leden samtidigt (och oberoende av varandra), så kan man helt bortse från tiden att förflytta sig i y-led (i detta exempel). Det är nämligen ingen tidsskillnad mellan att åka till (x=8, y=1) jämfört med (x=8, y=2) eftersom du alltså flyttar upp en våning på vägen fram till rätt x-plats. Diagonalen (alltså det du räknar fram med Pytagoras) blir ju endast applicerbar om hastigheten i x-led och y-led är beroende av varandra och den inte kan hålla maxhastighet i båda led samtidigt.

Skrivet av RobinJacobsson:

Självklart, men vet man vad som behöver ändras och det inte är mer än ett par knapptryckningar bort för att informera mig så vore jag såklart tacksam för info.

Skickades från m.sweclockers.com

Programmet var väldigt mycket ett "hack", så är inte helt trivial att ändra kostnadsmatrisen från heltal till flyttal. Go förbjuder i praktiken helt alla former av implicit konvertering mellan typer. Inte jättevanligt att implicit konvertering i den form som t.ex. C++, Java och C# gör, leder till buggar men när det händer kan det bli rätt elaka fel som är väldigt svåra att hitta.

package main import ( "bytes" "encoding/csv" "flag" "fmt" "io" "log" "math/bits" "os" "runtime" "strconv" "strings" "time" ) // Represent cost along a specific path or between two edges type Cost float64 // Represent a specific location in the graph type Edge int // EdgeSet type EdgeSet struct { Storage uint } func (set EdgeSet) Contains(value Edge) bool { return (set.Storage & (1 << uint(value))) != 0 } func (set EdgeSet) Count() int { return bits.OnesCount(set.Storage) } func (set *EdgeSet) Insert(value Edge) { set.Storage |= 1 << uint(value) } func (set *EdgeSet) Remove(value Edge) { set.Storage &= ^(1 << uint(value)) } func (set EdgeSet) Value() int { return int(set.Storage >> 1) } func (set EdgeSet) Iter() []Edge { n := set.Count() v := make([]Edge, n) for c, i := 0, 0; c < n; i++ { edge := Edge(i) if set.Contains(edge) { v[c] = edge c++ } } return v } func (set EdgeSet) String() string { buf := bytes.Buffer{} buf.WriteString("{") delim := "" for c, i := 0, 0; c < set.Count(); i++ { if set.Contains(Edge(i)) { buf.WriteString(fmt.Sprintf("%s%v", delim, i)) delim = "," c++ } } buf.WriteString("}") return buf.String() } // Combinations 'k' integers from a serie '1..n' type Combs []EdgeSet func combWithLen(n, k, first int, set EdgeSet, acc Combs) Combs { if k > set.Count() { for x := first; x <= n; x++ { s := set s.Insert(Edge(x)) acc = combWithLen(n, k, x + 1, s, acc) } } else { acc = append(acc, set) } return acc } func Comb(n, k int) Combs { return combWithLen(n, k, 1, EdgeSet{}, Combs{}) } // Held Karp type Path struct { AccCost Cost From Edge } func minPath(paths []Path) Path { m := paths[0] for i := 1; i < len(paths); i++ { if m.AccCost > paths[i].AccCost { m = paths[i] } } return m } func pathFromTo(from, to Edge, c [][]Path, dists CostMatrix, prev EdgeSet) Path { p := Path{} p.AccCost = c[prev.Value()][from-1].AccCost + dists[from][to] p.From = from return p } func reverse(a []Edge) []Edge { for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 { a[i], a[j] = a[j], a[i] } return a } // CostMatrix type CostMatrix [][]Cost func (dists CostMatrix) CalcCostToSubsets(c [][]Path, edges, subsetSz int) { workers := runtime.NumCPU() done := make(chan bool) combs := Comb(edges, subsetSz) batchSz := len(combs) / workers launched := 0 for w := 0; w < workers; w++ { i, l := w * batchSz, batchSz if w == workers - 1 { // Include any leftovers from integer division l = len(combs) - launched } launched += l go func(from, cnt int) { for i := from; i < from + cnt; i++ { vs := combs[i] subset := vs.Iter() // Find the lowest cost to get to this subset for _, k := range subset { prev := vs prev.Remove(k) res := []Path{} for _, m := range subset { if m != k { res = append(res, pathFromTo(m, k, c, dists, prev)) } } if len(res) > 0 { c[vs.Value()][k-1] = minPath(res) } } } done<- true }(i, l) } // Wait for all workers to finish for ;workers > 0; workers -= 1 { <-done } } func (dists CostMatrix) ShortestPath() (Cost, []Edge) { n := len(dists) c := make([][]Path, 1<<uint(n-1)) for i := 0; i < len(c); i++ { c[i] = make([]Path, n-1) } // Add paths from start to first steps for k := 1; k < n; k++ { c[1<<uint(k-1)][k-1] = Path{dists[0][k], 0} } for s := 2; s < n; s++ { dists.CalcCostToSubsets(c, n - 1, s) } visited := EdgeSet{} for k := 1; k < n; k++ { visited.Insert(Edge(k)) } // Add path back to start and calculate optimal cost res := []Path{} for k := 1; k < n; k++ { res = append(res, pathFromTo(Edge(k), 0, c, dists, visited)) } p := minPath(res) cost := p.AccCost // Backtrack to find path steps := make([]Edge, n+1) for i := 1; i < n; i++ { steps[i] = p.From from := p.From p = c[visited.Value()][p.From-1] visited.Remove(from) } return cost, reverse(steps) } func (c CostMatrix) String() string { buf := bytes.Buffer{} for row := 0; row < len(c); row++ { buf.WriteString(" ") for col := 0; col < len(c[row]); col++ { buf.WriteString(fmt.Sprintf("%4v", c[row][col])) if col != len(c[row])-1 { buf.WriteString(", ") } } buf.WriteString("\n") } return buf.String() } func zeroMatrix(dim int) CostMatrix { var c CostMatrix = make([][]Cost, dim) for i := range c { c[i] = make([]Cost, dim) } return c } func readMatrix(r io.Reader) CostMatrix { cr := csv.NewReader(r) rec, err := cr.ReadAll() if err != nil { log.Fatalln(err) } M := zeroMatrix(len(rec)) for row, line := range rec { for col, str := range line { v, err := strconv.ParseFloat(strings.TrimSpace(str), 64) if err != nil { log.Fatalln(err) } M[row][col] = Cost(v) } } return M } func GetCostMatrix() CostMatrix { args := flag.Args() if len(args) == 0 { return readMatrix(os.Stdin) } file, err := os.Open(args[0]) if err != nil { log.Fatalln(err) } return readMatrix(file) } // Program entrypoint func main() { var measure = flag.Bool("measure", false, "Print elapsed execution time") var verbose = flag.Bool("verbose", false, "Print internal state information") flag.Parse() start := time.Now() c := GetCostMatrix() if *verbose { fmt.Print("Cost matrix\n", c) } cost, path := c.ShortestPath() if *measure { fmt.Println("Elapsed:", time.Since(start)) } if *verbose { fmt.Println("Edges:", len(path) - 1) } fmt.Println(cost, path) }

En variant där du kan bestämma hur kostnaden representeras genom typen Cost, är satt till 64-bitars float nu men fungerar med 32-bitars float och heltal av olika bitbredd.

Nu skriver programmet bara ut svaret i normalfallet, skicka in "-verbose" för att printa saker som inläst kostnadsmatris och liknande. "-measure" mäter hur lång tid det tar att räkna ut kortaste vägen i "wall-clock-time".

Skrivet av Yoshman:

package main import ( "bytes" "encoding/csv" "flag" "fmt" "io" "log" "math/bits" "os" "runtime" "strconv" "strings" "time" ) // Represent cost along a specific path or between two edges type Cost float64 // Represent a specific location in the graph type Edge int // EdgeSet type EdgeSet struct { Storage uint } func (set EdgeSet) Contains(value Edge) bool { return (set.Storage & (1 << uint(value))) != 0 } func (set EdgeSet) Count() int { return bits.OnesCount(set.Storage) } func (set *EdgeSet) Insert(value Edge) { set.Storage |= 1 << uint(value) } func (set *EdgeSet) Remove(value Edge) { set.Storage &= ^(1 << uint(value)) } func (set EdgeSet) Value() int { return int(set.Storage >> 1) } func (set EdgeSet) Iter() []Edge { n := set.Count() v := make([]Edge, n) for c, i := 0, 0; c < n; i++ { edge := Edge(i) if set.Contains(edge) { v[c] = edge c++ } } return v } func (set EdgeSet) String() string { buf := bytes.Buffer{} buf.WriteString("{") delim := "" for c, i := 0, 0; c < set.Count(); i++ { if set.Contains(Edge(i)) { buf.WriteString(fmt.Sprintf("%s%v", delim, i)) delim = "," c++ } } buf.WriteString("}") return buf.String() } // Combinations 'k' integers from a serie '1..n' type Combs []EdgeSet func combWithLen(n, k, first int, set EdgeSet, acc Combs) Combs { if k > set.Count() { for x := first; x <= n; x++ { s := set s.Insert(Edge(x)) acc = combWithLen(n, k, x + 1, s, acc) } } else { acc = append(acc, set) } return acc } func Comb(n, k int) Combs { return combWithLen(n, k, 1, EdgeSet{}, Combs{}) } // Held Karp type Path struct { AccCost Cost From Edge } func minPath(paths []Path) Path { m := paths[0] for i := 1; i < len(paths); i++ { if m.AccCost > paths[i].AccCost { m = paths[i] } } return m } func pathFromTo(from, to Edge, c [][]Path, dists CostMatrix, prev EdgeSet) Path { p := Path{} p.AccCost = c[prev.Value()][from-1].AccCost + dists[from][to] p.From = from return p } func reverse(a []Edge) []Edge { for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 { a[i], a[j] = a[j], a[i] } return a } // CostMatrix type CostMatrix [][]Cost func (dists CostMatrix) CalcCostToSubsets(c [][]Path, edges, subsetSz int) { workers := runtime.NumCPU() done := make(chan bool) combs := Comb(edges, subsetSz) batchSz := len(combs) / workers launched := 0 for w := 0; w < workers; w++ { i, l := w * batchSz, batchSz if w == workers - 1 { // Include any leftovers from integer division l = len(combs) - launched } launched += l go func(from, cnt int) { for i := from; i < from + cnt; i++ { vs := combs[i] subset := vs.Iter() // Find the lowest cost to get to this subset for _, k := range subset { prev := vs prev.Remove(k) res := []Path{} for _, m := range subset { if m != k { res = append(res, pathFromTo(m, k, c, dists, prev)) } } if len(res) > 0 { c[vs.Value()][k-1] = minPath(res) } } } done<- true }(i, l) } // Wait for all workers to finish for ;workers > 0; workers -= 1 { <-done } } func (dists CostMatrix) ShortestPath() (Cost, []Edge) { n := len(dists) c := make([][]Path, 1<<uint(n-1)) for i := 0; i < len(c); i++ { c[i] = make([]Path, n-1) } // Add paths from start to first steps for k := 1; k < n; k++ { c[1<<uint(k-1)][k-1] = Path{dists[0][k], 0} } for s := 2; s < n; s++ { dists.CalcCostToSubsets(c, n - 1, s) } visited := EdgeSet{} for k := 1; k < n; k++ { visited.Insert(Edge(k)) } // Add path back to start and calculate optimal cost res := []Path{} for k := 1; k < n; k++ { res = append(res, pathFromTo(Edge(k), 0, c, dists, visited)) } p := minPath(res) cost := p.AccCost // Backtrack to find path steps := make([]Edge, n+1) for i := 1; i < n; i++ { steps[i] = p.From from := p.From p = c[visited.Value()][p.From-1] visited.Remove(from) } return cost, reverse(steps) } func (c CostMatrix) String() string { buf := bytes.Buffer{} for row := 0; row < len(c); row++ { buf.WriteString(" ") for col := 0; col < len(c[row]); col++ { buf.WriteString(fmt.Sprintf("%4v", c[row][col])) if col != len(c[row])-1 { buf.WriteString(", ") } } buf.WriteString("\n") } return buf.String() } func zeroMatrix(dim int) CostMatrix { var c CostMatrix = make([][]Cost, dim) for i := range c { c[i] = make([]Cost, dim) } return c } func readMatrix(r io.Reader) CostMatrix { cr := csv.NewReader(r) rec, err := cr.ReadAll() if err != nil { log.Fatalln(err) } M := zeroMatrix(len(rec)) for row, line := range rec { for col, str := range line { v, err := strconv.ParseFloat(strings.TrimSpace(str), 64) if err != nil { log.Fatalln(err) } M[row][col] = Cost(v) } } return M } func GetCostMatrix() CostMatrix { args := flag.Args() if len(args) == 0 { return readMatrix(os.Stdin) } file, err := os.Open(args[0]) if err != nil { log.Fatalln(err) } return readMatrix(file) } // Program entrypoint func main() { var measure = flag.Bool("measure", false, "Print elapsed execution time") var verbose = flag.Bool("verbose", false, "Print internal state information") flag.Parse() start := time.Now() c := GetCostMatrix() if *verbose { fmt.Print("Cost matrix\n", c) } cost, path := c.ShortestPath() if *measure { fmt.Println("Elapsed:", time.Since(start)) } if *verbose { fmt.Println("Edges:", len(path) - 1) } fmt.Println(cost, path) }

En variant där du kan bestämma hur kostnaden representeras genom typen Cost, är satt till 64-bitars float nu men fungerar med 32-bitars float och heltal av olika bitbredd.

När man programmerar med flyttal måste man ta hänsyn till avrundningsfel. I det här fallet behövs dessutom inte flyttal och därför är det bättre att hålla sig till heltal för att slippa buggar. Att använda samma kod och bara byta typ på Cost mellan int och float skulle jag inte rekommendera.

I heltalsversionen så är avståndet 1 + 2 samma sak som avståndet 3
I flyttalsversionen är 0.1 + 0.2 ett längre avstånd än 0.3 eller 0.15 + 0.15

Skrivet av jclr:

När man programmerar med flyttal måste man ta hänsyn till avrundningsfel. I det här fallet behövs dessutom inte flyttal och därför är det bättre att hålla sig till heltal för att slippa buggar. Att använda samma kod och bara byta typ på Cost mellan int och float skulle jag inte rekommendera.

I heltalsversionen så är avståndet 1 + 2 samma sak som avståndet 3
I flyttalsversionen är 0.1 + 0.2 ett längre avstånd än 0.3 eller 0.15 + 0.15

I det generella fallet: absolut!!! Har jobbat med både libc och libc++ och är smärtsamt medveten om alla tänkbara och otänkbara buggar som kan uppstå, flyttal ska undvikas om det är möjligt... Och det är ett (av flera) exempel på problem som kan uppstå i språk som tillåter implicit konvertering mellan heltal/flyttal.

I detta fall: om målet är att hitta den kortaste vägen lär det kvitta vilken man tar om det finns flera som bara skiljer i någon decimal långt långt bort. Enda risken här är fel från ackumulering, men då algoritmen begränsas det hela till <25-26 artiklar är det i praktiken bara ett relevant problem om det är en trave tiopotenser mellan två termer. I detta fall borde det aldrig hända då det handlar om ett lager.

Tack för era inputs, kodmässigt kan jag inte kommentera så mycket. Men efter att ha gett färd-problemet en tanke så förstår jag "problematiken". Det är ju faktiskt som ni säger bara det ledet där man når slutpunkten sist vars förflyttning tidsmässigt spelar någon roll, eftersom man ändå tvingas vänta in hela förflyttningen i andra ledet.

Skickades från m.sweclockers.com

Senast redigerat 2019-11-06 21:36
Liknande problem

https://people.sc.fsu.edu/~jburkardt/c_src/tsp_brute/tsp_brut...

Här testar man på 5x5 men det fungerar bra upp till 12x12 på Raspberry Pi

https://rosettacode.org/wiki/Transportation_problem#Java

Java ser ut att fungera bra här.