Traveling Salesman
Εκφώνηση
Το παρακάτω γράφημα αναπαριστά την περιοχή που καλύπτει ένας πωλητής, με καταστήματα στα σημεία Α, Β, C, D, Ε και F (δεν είναι σε κλίμακα). Οι αριθμοί αντιπροσωπεύουν την απόσταση σε χιλιόμετρα ανάμεσα στα μέρη που πρέπει να επισκεφθεί o πωλητής κάθε μέρα. Ποια είναι η διαδρομή με την ελάχιστη συνολική απόσταση;
Το πρόβλημα έχει ληφθεί από αυτή τη σελίδα: http://nrich.maths.org/923
Εισαγωγή Δεδομένων
Το δοθέν σχήμα μπορεί να αναπαρασταθεί με τον παρακάτω πίνακα
suppressPackageStartupMessages(library(TSP))
suppressPackageStartupMessages(library(igraph))
suppressPackageStartupMessages(library(xtable))
nodes <- 6
df <- read.table(textConnection("
from to weight
A B 9
A E 8
A F 14
B C 14
B E 8
B F 7
C F 8
C D 15
D F 12
D E 12
E F 10
")->con, header=TRUE, stringsAsFactors=FALSE)
close(con)
print(xtable(df, align="lccc"), type="html", html.table.attributes='class="table table-striped table-hover center"')| from | to | weight | |
|---|---|---|---|
| 1 | A | B | 9 |
| 2 | A | E | 8 |
| 3 | A | F | 14 |
| 4 | B | C | 14 |
| 5 | B | E | 8 |
| 6 | B | F | 7 |
| 7 | C | F | 8 |
| 8 | C | D | 15 |
| 9 | D | F | 12 |
| 10 | D | E | 12 |
| 11 | E | F | 10 |
Πίνακας Αποστάσεων
Το πρόβλημα θα επιλυθεί κάνοντας χρήση του πακέτου TSP. Αρχικά θα κατασκευαστεί ο πίνακας αποστάσεων που απαιτείται ως παράμετρος στη συνάρτηση κατασκευής (constructor). Μεταξύ κόμβων που δεν συνδέονται, χρησιμοποιείται άπειρη απόσταση.
my_dist <- matrix(rep(Inf,nodes^2),nrow=nodes)
colnames(my_dist)<-LETTERS[1:6]
rownames(my_dist)<-LETTERS[1:6]
my_dist[seq(1,nodes^2,by=nodes+1)] <- 0
invisible(apply(df,1,function(x) {
my_dist[x[1],x[2]]<<-as.numeric(x[3])
my_dist[x[2],x[1]]<<-as.numeric(x[3])
}))
print(xtable(my_dist, align="lcccccc"), type="html", html.table.attributes='class="table table-striped table-hover center"')| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0.00 | 9.00 | Inf | Inf | 8.00 | 14.00 |
| B | 9.00 | 0.00 | 14.00 | Inf | 8.00 | 7.00 |
| C | Inf | 14.00 | 0.00 | 15.00 | Inf | 8.00 |
| D | Inf | Inf | 15.00 | 0.00 | 12.00 | 12.00 |
| E | 8.00 | 8.00 | Inf | 12.00 | 0.00 | 10.00 |
| F | 14.00 | 7.00 | 8.00 | 12.00 | 10.00 | 0.00 |
Επίλυση με χρήση του πακέτου TSP
my_tsp <- TSP(my_dist, labels =rownames(my_dist))
tsp <- insert_dummy(my_tsp, label = "cut")
tour <- solve_TSP(tsp, method="farthest_insertion")
path <- cut_tour(tour, "cut")
res <- labels(path)
Από τα παραπάνω προκύπτει ότι η ελάχιστη διαδρομή είναι 44χλμ, ενώ η διαδρομή είναι η C, F, B, A, E, D.
Εμφάνιση του γράφου με τη λύση
adjm <- my_dist
adjm[adjm==Inf]<-0
colnames(adjm) <- LETTERS[1:6]
g2 <- graph.adjacency(adjm, mode="undirected", weighted=TRUE)
E(g2)$color <- "lightblue"
for (i in 1:(length(res)-1)){
E(g2) [ res[i] %--% res[i+1] ]$color <- "red"
}
plot(g2, edge.label = E(g2)$weight)
title(paste0("Ελάχιστη διαδρομή: ",attributes(tour)["tour_length"],"χλμ"))