TSP не дает оптимальный тур, используя язык - PullRequest
Новая
       67

TSP не дает оптимальный тур, используя язык

0 голосов
/ 17 апреля 2020

Так что я работаю в Rstudio, чтобы решить TSP, предоставив edgelist в качестве входных данных. Вот мой код 

library("igraph")
library("TSP")

edgelist <- structure(list(V1 = c(1L, 1L, 1L, 2L, 2L, 2L, 3L, 3L, 4L, 4L,
4L, 5L, 5L, 5L, 6L, 6L, 6L, 7L, 7L, 7L, 8L, 8L, 9L, 9L, 10L,
10L, 10L, 11L, 11L, 11L, 12L, 12L, 12L, 13L, 13L, 14L, 14L, 14L,
15L, 15L, 15L, 16L, 16L, 17L, 17L, 18L, 19L, 19L, 20L, 20L, 21L,
22L, 22L, 22L, 23L, 23L, 24L, 24L, 24L, 25L, 25L, 26L, 26L, 26L,
27L, 27L, 28L, 28L, 28L, 29L, 29L, 29L, 30L, 30L, 32L, 32L, 33L,
33L, 33L, 34L, 34L, 37L, 38L, 38L, 39L, 40L, 41L, 41L, 42L, 43L,
46L, 47L, 48L, 48L, 49L, 53L, 54L, 58L, 64L), V2 = c(3L, 9L,
61L, 17L, 31L, 51L, 40L, 46L, 42L, 47L, 63L, 8L, 18L, 39L, 30L,
40L, 62L, 13L, 31L, 58L, 50L, 63L, 25L, 35L, 16L, 27L, 44L, 19L,
45L, 54L, 21L, 47L, 55L, 51L, 66L, 35L, 57L, 61L, 18L, 20L, 63L,
52L, 53L, 21L, 37L, 23L, 52L, 56L, 32L, 57L, 34L, 38L, 44L, 60L,
49L, 57L, 36L, 56L, 62L, 36L, 46L, 43L, 60L, 64L, 60L, 65L, 44L,
45L, 52L, 31L, 37L, 41L, 54L, 56L, 35L, 36L, 43L, 48L, 66L, 39L,
50L, 55L, 45L, 59L, 49L, 59L, 42L, 58L, 55L, 65L, 62L, 50L, 51L,
53L, 61L, 65L, 59L, 64L, 66L)), class = "data.frame", row.names = c("1",
"2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13",
"14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24",
"25", "26", "27", "28", "29", "30", "31", "32", "33", "34", "35",
"36", "37", "38", "39", "40", "41", "42", "43", "44", "45", "46",
"47", "48", "49", "50", "51", "52", "53", "54", "55", "56", "57",
"58", "59", "60", "61", "62", "63", "64", "65", "66", "67", "68",
"69", "70", "71", "72", "73", "74", "75", "76", "77", "78", "79",
"80", "81", "82", "83", "84", "85", "86", "87", "88", "89", "90",
"91", "92", "93", "94", "95", "96", "97", "98", "99"))

g <- graph_from_edgelist(as.matrix(edgelist))
plot(g)

adj_mat = as_adjacency_matrix(g, sparse = FALSE)

d <- as.dist(1/(1+adj_mat))

tsp <- TSP(d)

o <- solve_TSP(tsp)
o

o2 <- solve_TSP(tsp, method="concorde",rep=10, control = list(clo = "-V"))
o2

matrix_tour = as.matrix(o)
colnames(matrix_tour) = c("v1")
pred_tour = matrix_tour[order(data.frame(matrix_tour)$v1),]

new_edge_list = matrix(0,length(matrix_tour),2)
for(i in 1:length(matrix_tour)){
new_edge_list[i,1] = matrix_tour[i,1]
if(i!=length(matrix_tour))
{
new_edge_list[i,2] = matrix_tour[i+1,1]
}
else{
new_edge_list[i,2] = matrix_tour[1,1]
}
}
g2 <- graph_from_edgelist(as.matrix(new_edge_list))
plot(g2)

Если я нанесу g и g2, я вижу, что g2 не содержит ребер из исходного графа g. Я также проверил это вручную. Это означает, что оптимальный поиск тура по TSP не имеет этих ребер из исходного графа.

Мой вопрос заключается в том, как мы можем ограничить решатель TSP, чтобы дать мне тур, который содержит только ребра из исходного графика, в противном случае возвращаем, что тур не найден. Поскольку в графе 66 узлов, я хочу, чтобы TSP вернул оптимальный маршрут длиной 66 или вернул, что маршрут не найден

Примечание. Я попытался заменить 0 на более высокий вес в матрице смежности, однако, это все равно создает ту же проблему, что и описанную выше.

Кто-нибудь может подсказать мне, что я здесь делаю?

...