Typisches Problem und Ausführungsmethode
Ein Graph, der aus einer Menge von n Punkten (Stadt) $ V $ $ G = (V, E) $ und einer Schaltung besteht, die alle Punkte einmal durchläuft, wenn die Kosten für jede Seite angegeben sind. Finden Sie diejenige, die die Summe der Kosten (z. B. Entfernung) an den Seiten minimiert.
usage
Signature: tsp(nodes, dist=None, method=None)
Docstring:
Patrouillenverkäufer Problem
Eingang
nodes:Punkt(Wenn dist nicht angegeben ist, werden die Koordinaten angegeben)Liste von
dist: (i,j)Ein Wörterbuch mit dem Schlüssel und der Entfernung als Wert
method:Berechnungsmethode(ex. 'ortools')
Ausgabe
Liste der Entfernungs- und Punktnummern
python
from ortoolpy import tsp
tsp([(2, 0), (1, 2), (0, 1), (3, 1), (2, 2)])[1]
Ergebnis
[0, 2, 1, 4, 3]
python
# pandas.DataFrame
from ortoolpy.optimization import Tsp
Tsp('data/node1.csv')[1]
| id | x | y | demand | |
|---|---|---|---|---|
| 0 | 0 | 5 | 1 | 0 |
| 3 | 3 | 1 | 0 | 1 |
| 5 | 5 | 0 | 4 | 1 |
| 2 | 2 | 1 | 5 | 1 |
| 1 | 1 | 8 | 5 | 1 |
| 4 | 4 | 8 | 0 | 1 |
Wenn Sie " method = 'ortools' "hinzufügen, wird der Solver (ungefähre Lösung) von Google OR-Tools verwendet.
--Installieren Sie Google OR-Tools mit "pip install or tools".
dist) sollte eine ganze Zahl sein.python
import numpy as np
from scipy.spatial import distance
from ortoolpy import tsp
np.random.seed(0)
nodes = np.random.rand(20, 2) * 1000 #20 Städte
dist = distance.cdist(nodes, nodes).astype(int) #Distanzmatrix
print(tsp(nodes, dist, method='ortools')) #Ungefähre Lösung
print(tsp(nodes, dist)) #Genaue Lösung (Referenz)
Die Gesamtkosten (4099) sind höher als die exakte Lösung (4072.0) in der zweiten Zeile.
Ergebnis (Summe der Kosten und Liste der Punktnummern)
(4099, [0, 11, 3, 6, 9, 10, 19, 4, 5, 18, 1, 14, 7, 17, 12, 8, 13, 15, 2, 16])
(4072.0, [0, 2, 16, 14, 7, 17, 12, 8, 13, 15, 11, 3, 6, 9, 10, 19, 4, 5, 1, 18])
Recommended Posts