使用 Concorde 解决旅行商问题 (TSP) 时 R studio 中的问题
Problem in R studio while solving Traveling Salesman Problem (TSP) using Concorde
我正在与 Concorde 合作解决 TSP 问题。这是我的代码
library(TSP)
concordePath = "E:/Concorde_Code/"
concorde_path(concordePath)
concorde_help()
dataset_path = "E:/RA/"
name = "graph1.txt"
dataset = read.table(paste(dataset_path,name,sep = ""))
arr=dataset
nodelist = unique(as.vector(as.matrix(arr)))
arr_mat = matrix(0,length(nodelist),length(nodelist))
for (i in 1:length(arr[,1])){
arr_mat[arr[i,1],arr[i,2]] = 1
arr_mat[arr[i,2],arr[i,1]] = 1
}
arr_mat_new = arr_mat
for(i in 1:length(arr_mat[,1])){
arr_mat_new[i,which(arr_mat[i,]==0)] = 2 #replace all zero entries with 2
}
d <- as.dist(arr_mat_new)
tsp <- TSP(d)
tsp
o <- solve_TSP(tsp, method="concorde")
labels(o)
Concorde 已正确安装在我的系统上并且运行良好。当我 运行 concorde_help() 时，我得到以下输出
The following options can be specified in solve_TSP with method "concorde" using clo in control:
/Concorde_Code/concorde
Usage: /Concorde_Code/concorde [-see below-] [dat_file]
-B do not branch
-C # maximum chunk size in localcuts (default 16)
-d use dfs branching instead of bfs
-D f edgegen file for initial edge set
-e f initial edge file
-E f full edge file (must contain initial edge set)
-f write optimal tour as edge file (default is tour file)
-F f read extra cuts from file
-g h be a grunt for boss h
-h be a boss for the branching
-i just solve the blossom polytope
-I just solve the subtour polytope
-J # number of tentative branches
-k # number of nodes for random problem
-K h use cut server h
-M f master file
-m use multiple passes of cutting loop
-n s problem location (just a name or host:name, not a file name)
-o f output file name (for optimal tour)
-P f cutpool file
-q do not cut the root lp
-r # use #x# grid for random points, no dups if #<0
-R f restart file
-s # random seed
-S f problem file
-t f tour file (in node node node format)
-u v initial upperbound
-U do not permit branching on subtour inequalities
-v verbose (turn on lots of messages)
-V just run fast cuts
-w just subtours and trivial blossoms
-x delete files on completion (sav pul mas)
-X f write the last root fractional solution to f
-y use simple cutting and branching in DFS
-z # dump the #-lowest reduced cost edges to file xxx.rcn
-N # norm (must specify if dat file is not a TSPLIB file)
0=MAX, 1=L1, 2=L2, 3=3D, 4=USER, 5=ATT, 6=GEO, 7=MATRIX,
8=DSJRAND, 9=CRYSTAL, 10=SPARSE, 11-15=RH-norm 1-5, 16=TOROIDAL
17=GEOM, 18=JOHNSON
这说明Concorde安装正确。但是，当我尝试 运行 R 代码（在顶部给出）时，我有时会得到答案，而有时我的程序会卡住。当程序成功执行时，我得到以下输出
Used control parameters:
clo =
exe = E:\Concorde_Code\/concorde
precision = 6
verbose = TRUE
keep_files = FALSE
/Concorde_Code/concorde -x -o file18ec719b5412.sol file18ec719b5412.dat
Host: Pasha Current process id: 1165
Using random seed 1586633006
Problem Name: TSP
Generated by write_TSPLIB (R-package TSP)
Problem Type: TSP
Number of Nodes: 66
Explicit Lengths (CC_MATRIXNORM)
Set initial upperbound to 0 (from tour)
LP Value 1: 0.000000 (0.03 seconds)
New lower bound: 0.000000
WARNING: LK incremental counter was off by 4294967296
Final lower bound 0.000000, upper bound 0.000000
Exact lower bound: 0.000000
DIFF: 0.000000
Final LP has 71 rows, 129 columns, 345 nonzeros
Optimal Solution: 0.00
Number of bbnodes: 1
Total Running Time: 1.70 (seconds)
在上面的输出中，最优解是 0.00。谁能告诉我为什么这是零？有时代码不执行并给出以下输出
Used control parameters:
clo =
exe = E:\Concorde_Code\/concorde
precision = 6
verbose = TRUE
keep_files = FALSE
/Concorde_Code/concorde -x -o file18ec7f123355.sol file18ec7f123355.dat
Host: Pasha Current process id: 693
Using random seed 1586633314
FATAL ERROR - received signal SIGSEGV (11/11)
Problem Name: TSP
Generated by write_TSPLIB (R-package TSP)
Problem Type: TSP
Number of Nodes: 66
Explicit Lengths (CC_MATRIXNORM)
sleeping 1 more hours to permit debugger access
在这个输出之后，没有任何反应，程序似乎进入了无限循环。谁能告诉我我做错了什么？
这是我系统的问题吗？我正在使用 Windows 10 和 R-studio 64 位开发核心 i3 系统。
编辑：这是我正在使用的数据集
V1 V2
1 1 3
2 1 9
3 1 61
4 2 17
5 2 31
6 2 51
7 3 40
8 3 46
9 4 42
10 4 47
11 4 63
12 5 8
13 5 18
14 5 39
15 6 30
16 6 40
17 6 62
18 7 13
19 7 31
20 7 58
21 8 50
22 8 63
23 9 25
24 9 35
25 10 16
26 10 27
27 10 44
28 11 19
29 11 45
30 11 54
31 12 21
32 12 47
33 12 55
34 13 51
35 13 66
36 14 35
37 14 57
38 14 61
39 15 18
40 15 20
41 15 63
42 16 52
43 16 53
44 17 21
45 17 37
46 18 23
47 19 52
48 19 56
49 20 32
50 20 57
51 21 34
52 22 38
53 22 44
54 22 60
55 23 49
56 23 57
57 24 36
58 24 56
59 24 62
60 25 36
61 25 46
62 26 43
63 26 60
64 26 64
65 27 60
66 27 65
67 28 44
68 28 45
69 28 52
70 29 31
71 29 37
72 29 41
73 30 54
74 30 56
75 32 35
76 32 36
77 33 43
78 33 48
79 33 66
80 34 39
81 34 50
82 37 55
83 38 45
84 38 59
85 39 49
86 40 59
87 41 42
88 41 58
89 42 55
90 43 65
91 46 62
92 47 50
93 48 51
94 48 53
95 49 61
96 53 65
97 54 59
98 58 64
99 64 66
编辑 2：这是会话信息
R version 3.5.2 (2018-12-20)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows >= 8 x64 (build 9200)
Matrix products: default
locale:
[1] LC_COLLATE=English_United States.1252 LC_CTYPE=English_United States.1252
[3] LC_MONETARY=English_United States.1252 LC_NUMERIC=C
[5] LC_TIME=English_United States.1252
attached base packages:
[1] stats graphics grDevices utils datasets methods base
other attached packages:
[1] R.utils_2.9.2 R.oo_1.23.0 R.methodsS3_1.8.0 tspmeta_1.2 MASS_7.3-51.1
[6] ggplot2_3.1.1 TSP_1.1-9
loaded via a namespace (and not attached):
[1] modeltools_0.2-22 tidyselect_0.2.5 xfun_0.4 purrr_0.2.5 kernlab_0.9-27
[6] lattice_0.20-38 colorspace_1.4-1 stats4_3.5.2 mgcv_1.8-26 yaml_2.2.0
[11] rlang_0.3.4 pillar_1.4.1 glue_1.3.1 withr_2.1.2 prabclus_2.2-6
[16] sp_1.3-1 fpc_2.1-11.1 bindrcpp_0.2.2 foreach_1.4.4 bindr_0.1.1
[21] plyr_1.8.4 robustbase_0.93-3 stringr_1.4.0 munsell_0.5.0 gtable_0.3.0
[26] mvtnorm_1.0-8 codetools_0.2-15 knitr_1.21 permute_0.9-5 parallel_3.5.2
[31] flexmix_2.3-14 class_7.3-15 DEoptimR_1.0-8 trimcluster_0.1-2.1 Rcpp_1.0.1
[36] backports_1.1.4 scales_1.0.0 diptest_0.75-7 checkmate_1.9.0 vegan_2.5-6
[41] stringi_1.4.3 BBmisc_1.11 dplyr_0.7.8 splancs_2.01-40 grid_3.5.2
[46] tools_3.5.2 magrittr_1.5 lazyeval_0.2.2 tibble_2.1.3 cluster_2.0.7-1
[51] crayon_1.3.4 pkgconfig_2.0.2 Matrix_1.2-15 assertthat_0.2.1 rstudioapi_0.8
[56] iterators_1.0.10 R6_2.4.0 mclust_5.4.2 nlme_3.1-137 nnet_7.3-12
[61] compiler_3.5.2
您创建的距离矩阵是协和式飞机的问题。协和式飞机应该捕捉到并给出适当的错误消息。
下面是将表示为边列表的图转换为距离矩阵并求解 TSP（使用 TSP 1.1-10 或更高版本）的适当方法：
library("igraph")
library("TSP")
# Read edgelist (you can use read.csv or read.table)
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"))
# create graph
g <- graph_from_edgelist(as.matrix(edgelist), directed = FALSE)
plot(g)
# convert graph into a distance matrix
d <- as.dist((1/as_adjacency_matrix(g, sparse = FALSE))-1)
# solve TSP
tsp <- TSP(d)
# standard heuristic works, but uses a non-existing edge (path length is Inf)
o <- solve_TSP(tsp)
o
as.integer(o)
# Lin-Kernighan heuristic works, but also uses a non-existing edge (path length is Inf)
o <- solve_TSP(tsp, method="linkern")
o
as.integer(o)
# Concorde finds an optimal solution with path length 0
o <- solve_TSP(tsp, method="Concorde")
o
as.integer(o)
希望对您有所帮助。
所以我编译代码，发现高维邻接矩阵存在维数灾难问题。这是我处理这种情况的最终代码。
由于距离在高维中变得毫无意义，因此 as.dist 函数对于具有大量节点的图无法有效地工作。
这是我的最终工作代码，以防有人想检查它
dataset_path = "E:/RA/Pablo Moscato/dataset/FHCPCS/"
# name = "graph1.txt" #Found
# name = "graph2.txt" #Found
name = "graph3.txt"
# name = "graph4.txt"
# name = "graph5.txt"
# name = "graph6.txt" #Found
# name = "graph7.txt"
# name = "graph8.txt"
# name = "graph9.txt"
# name = "graph10.txt"
# name = "graph13.txt"
# name = "graph19.txt"
# name = "graph40.txt"
dataset = read.table(paste(dataset_path,name,sep = ""))
# main_function(dataset)
# create graph
# g <- graph_from_edgelist(as.matrix(dataset))
# plot(g)
final_edgelist = dataset
g <- graph_from_edgelist(as.matrix(final_edgelist))
# plot(g)
# convert graph into a distance matrix
adj_mat = as_adjacency_matrix(g, sparse = FALSE)
adj_mat_2 = adj_mat
nodelist = unique(as.vector(as.matrix(final_edgelist)))
adj_mat_sym = matrix(0,length(unique(nodelist)),length(unique(nodelist)))
for(i in 1:length(final_edgelist[,1])){
adj_mat_sym[final_edgelist[i,1],final_edgelist[i,2]] = 1
adj_mat_sym[final_edgelist[i,2],final_edgelist[i,1]] = 1
}
M = adj_mat_sym
lower_triangle = M[lower.tri(M)]
lower_triangle_2 = lower_triangle
lower_triangle_2[lower_triangle_2==0] = 2
lower_triangle_2[lower_triangle_2==1] = 0
lower_triangle_2[lower_triangle_2==2] = 100
d <- as.dist(1/(1+adj_mat_2))
d_5 = d
d_5[1:length(d_5)] = lower_triangle_2[1:length(lower_triangle_2)]
d_6 <- (1/(1+d_5))
d_7 = d_6
d_7[d_7==1] = 0
# tsp <- TSP(d_6)
tsp <- TSP(d_7)
# tsp_check <- TSP(d)
# o2 <- solve_TSP(tsp)
# o2
# as.integer(o2)
o2 <- solve_TSP(tsp, method="concorde",rep=10, control = list(clo = "-V"))
# o2 <- solve_TSP(tsp_check, method="concorde",rep=10, control = list(clo = "-V"))
o2
as.integer(o2)
我希望这能消除任何疑问。
我正在与 Concorde 合作解决 TSP 问题。这是我的代码
library(TSP)
concordePath = "E:/Concorde_Code/"
concorde_path(concordePath)
concorde_help()
dataset_path = "E:/RA/"
name = "graph1.txt"
dataset = read.table(paste(dataset_path,name,sep = ""))
arr=dataset
nodelist = unique(as.vector(as.matrix(arr)))
arr_mat = matrix(0,length(nodelist),length(nodelist))
for (i in 1:length(arr[,1])){
arr_mat[arr[i,1],arr[i,2]] = 1
arr_mat[arr[i,2],arr[i,1]] = 1
}
arr_mat_new = arr_mat
for(i in 1:length(arr_mat[,1])){
arr_mat_new[i,which(arr_mat[i,]==0)] = 2 #replace all zero entries with 2
}
d <- as.dist(arr_mat_new)
tsp <- TSP(d)
tsp
o <- solve_TSP(tsp, method="concorde")
labels(o)
Concorde 已正确安装在我的系统上并且运行良好。当我 运行 concorde_help() 时，我得到以下输出
The following options can be specified in solve_TSP with method "concorde" using clo in control:
/Concorde_Code/concorde
Usage: /Concorde_Code/concorde [-see below-] [dat_file]
-B do not branch
-C # maximum chunk size in localcuts (default 16)
-d use dfs branching instead of bfs
-D f edgegen file for initial edge set
-e f initial edge file
-E f full edge file (must contain initial edge set)
-f write optimal tour as edge file (default is tour file)
-F f read extra cuts from file
-g h be a grunt for boss h
-h be a boss for the branching
-i just solve the blossom polytope
-I just solve the subtour polytope
-J # number of tentative branches
-k # number of nodes for random problem
-K h use cut server h
-M f master file
-m use multiple passes of cutting loop
-n s problem location (just a name or host:name, not a file name)
-o f output file name (for optimal tour)
-P f cutpool file
-q do not cut the root lp
-r # use #x# grid for random points, no dups if #<0
-R f restart file
-s # random seed
-S f problem file
-t f tour file (in node node node format)
-u v initial upperbound
-U do not permit branching on subtour inequalities
-v verbose (turn on lots of messages)
-V just run fast cuts
-w just subtours and trivial blossoms
-x delete files on completion (sav pul mas)
-X f write the last root fractional solution to f
-y use simple cutting and branching in DFS
-z # dump the #-lowest reduced cost edges to file xxx.rcn
-N # norm (must specify if dat file is not a TSPLIB file)
0=MAX, 1=L1, 2=L2, 3=3D, 4=USER, 5=ATT, 6=GEO, 7=MATRIX,
8=DSJRAND, 9=CRYSTAL, 10=SPARSE, 11-15=RH-norm 1-5, 16=TOROIDAL
17=GEOM, 18=JOHNSON
这说明Concorde安装正确。但是，当我尝试 运行 R 代码（在顶部给出）时，我有时会得到答案，而有时我的程序会卡住。当程序成功执行时，我得到以下输出
Used control parameters:
clo =
exe = E:\Concorde_Code\/concorde
precision = 6
verbose = TRUE
keep_files = FALSE
/Concorde_Code/concorde -x -o file18ec719b5412.sol file18ec719b5412.dat
Host: Pasha Current process id: 1165
Using random seed 1586633006
Problem Name: TSP
Generated by write_TSPLIB (R-package TSP)
Problem Type: TSP
Number of Nodes: 66
Explicit Lengths (CC_MATRIXNORM)
Set initial upperbound to 0 (from tour)
LP Value 1: 0.000000 (0.03 seconds)
New lower bound: 0.000000
WARNING: LK incremental counter was off by 4294967296
Final lower bound 0.000000, upper bound 0.000000
Exact lower bound: 0.000000
DIFF: 0.000000
Final LP has 71 rows, 129 columns, 345 nonzeros
Optimal Solution: 0.00
Number of bbnodes: 1
Total Running Time: 1.70 (seconds)
在上面的输出中，最优解是 0.00。谁能告诉我为什么这是零？有时代码不执行并给出以下输出
Used control parameters:
clo =
exe = E:\Concorde_Code\/concorde
precision = 6
verbose = TRUE
keep_files = FALSE
/Concorde_Code/concorde -x -o file18ec7f123355.sol file18ec7f123355.dat
Host: Pasha Current process id: 693
Using random seed 1586633314
FATAL ERROR - received signal SIGSEGV (11/11)
Problem Name: TSP
Generated by write_TSPLIB (R-package TSP)
Problem Type: TSP
Number of Nodes: 66
Explicit Lengths (CC_MATRIXNORM)
sleeping 1 more hours to permit debugger access
在这个输出之后，没有任何反应，程序似乎进入了无限循环。谁能告诉我我做错了什么？
这是我系统的问题吗？我正在使用 Windows 10 和 R-studio 64 位开发核心 i3 系统。
编辑：这是我正在使用的数据集
V1 V2
1 1 3
2 1 9
3 1 61
4 2 17
5 2 31
6 2 51
7 3 40
8 3 46
9 4 42
10 4 47
11 4 63
12 5 8
13 5 18
14 5 39
15 6 30
16 6 40
17 6 62
18 7 13
19 7 31
20 7 58
21 8 50
22 8 63
23 9 25
24 9 35
25 10 16
26 10 27
27 10 44
28 11 19
29 11 45
30 11 54
31 12 21
32 12 47
33 12 55
34 13 51
35 13 66
36 14 35
37 14 57
38 14 61
39 15 18
40 15 20
41 15 63
42 16 52
43 16 53
44 17 21
45 17 37
46 18 23
47 19 52
48 19 56
49 20 32
50 20 57
51 21 34
52 22 38
53 22 44
54 22 60
55 23 49
56 23 57
57 24 36
58 24 56
59 24 62
60 25 36
61 25 46
62 26 43
63 26 60
64 26 64
65 27 60
66 27 65
67 28 44
68 28 45
69 28 52
70 29 31
71 29 37
72 29 41
73 30 54
74 30 56
75 32 35
76 32 36
77 33 43
78 33 48
79 33 66
80 34 39
81 34 50
82 37 55
83 38 45
84 38 59
85 39 49
86 40 59
87 41 42
88 41 58
89 42 55
90 43 65
91 46 62
92 47 50
93 48 51
94 48 53
95 49 61
96 53 65
97 54 59
98 58 64
99 64 66
编辑 2：这是会话信息
R version 3.5.2 (2018-12-20)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows >= 8 x64 (build 9200)
Matrix products: default
locale:
[1] LC_COLLATE=English_United States.1252 LC_CTYPE=English_United States.1252
[3] LC_MONETARY=English_United States.1252 LC_NUMERIC=C
[5] LC_TIME=English_United States.1252
attached base packages:
[1] stats graphics grDevices utils datasets methods base
other attached packages:
[1] R.utils_2.9.2 R.oo_1.23.0 R.methodsS3_1.8.0 tspmeta_1.2 MASS_7.3-51.1
[6] ggplot2_3.1.1 TSP_1.1-9
loaded via a namespace (and not attached):
[1] modeltools_0.2-22 tidyselect_0.2.5 xfun_0.4 purrr_0.2.5 kernlab_0.9-27
[6] lattice_0.20-38 colorspace_1.4-1 stats4_3.5.2 mgcv_1.8-26 yaml_2.2.0
[11] rlang_0.3.4 pillar_1.4.1 glue_1.3.1 withr_2.1.2 prabclus_2.2-6
[16] sp_1.3-1 fpc_2.1-11.1 bindrcpp_0.2.2 foreach_1.4.4 bindr_0.1.1
[21] plyr_1.8.4 robustbase_0.93-3 stringr_1.4.0 munsell_0.5.0 gtable_0.3.0
[26] mvtnorm_1.0-8 codetools_0.2-15 knitr_1.21 permute_0.9-5 parallel_3.5.2
[31] flexmix_2.3-14 class_7.3-15 DEoptimR_1.0-8 trimcluster_0.1-2.1 Rcpp_1.0.1
[36] backports_1.1.4 scales_1.0.0 diptest_0.75-7 checkmate_1.9.0 vegan_2.5-6
[41] stringi_1.4.3 BBmisc_1.11 dplyr_0.7.8 splancs_2.01-40 grid_3.5.2
[46] tools_3.5.2 magrittr_1.5 lazyeval_0.2.2 tibble_2.1.3 cluster_2.0.7-1
[51] crayon_1.3.4 pkgconfig_2.0.2 Matrix_1.2-15 assertthat_0.2.1 rstudioapi_0.8
[56] iterators_1.0.10 R6_2.4.0 mclust_5.4.2 nlme_3.1-137 nnet_7.3-12
[61] compiler_3.5.2
您创建的距离矩阵是协和式飞机的问题。协和式飞机应该捕捉到并给出适当的错误消息。
下面是将表示为边列表的图转换为距离矩阵并求解 TSP（使用 TSP 1.1-10 或更高版本）的适当方法：
library("igraph")
library("TSP")
# Read edgelist (you can use read.csv or read.table)
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"))
# create graph
g <- graph_from_edgelist(as.matrix(edgelist), directed = FALSE)
plot(g)
# convert graph into a distance matrix
d <- as.dist((1/as_adjacency_matrix(g, sparse = FALSE))-1)
# solve TSP
tsp <- TSP(d)
# standard heuristic works, but uses a non-existing edge (path length is Inf)
o <- solve_TSP(tsp)
o
as.integer(o)
# Lin-Kernighan heuristic works, but also uses a non-existing edge (path length is Inf)
o <- solve_TSP(tsp, method="linkern")
o
as.integer(o)
# Concorde finds an optimal solution with path length 0
o <- solve_TSP(tsp, method="Concorde")
o
as.integer(o)
希望对您有所帮助。
所以我编译代码，发现高维邻接矩阵存在维数灾难问题。这是我处理这种情况的最终代码。
由于距离在高维中变得毫无意义，因此 as.dist 函数对于具有大量节点的图无法有效地工作。
这是我的最终工作代码，以防有人想检查它
dataset_path = "E:/RA/Pablo Moscato/dataset/FHCPCS/"
# name = "graph1.txt" #Found
# name = "graph2.txt" #Found
name = "graph3.txt"
# name = "graph4.txt"
# name = "graph5.txt"
# name = "graph6.txt" #Found
# name = "graph7.txt"
# name = "graph8.txt"
# name = "graph9.txt"
# name = "graph10.txt"
# name = "graph13.txt"
# name = "graph19.txt"
# name = "graph40.txt"
dataset = read.table(paste(dataset_path,name,sep = ""))
# main_function(dataset)
# create graph
# g <- graph_from_edgelist(as.matrix(dataset))
# plot(g)
final_edgelist = dataset
g <- graph_from_edgelist(as.matrix(final_edgelist))
# plot(g)
# convert graph into a distance matrix
adj_mat = as_adjacency_matrix(g, sparse = FALSE)
adj_mat_2 = adj_mat
nodelist = unique(as.vector(as.matrix(final_edgelist)))
adj_mat_sym = matrix(0,length(unique(nodelist)),length(unique(nodelist)))
for(i in 1:length(final_edgelist[,1])){
adj_mat_sym[final_edgelist[i,1],final_edgelist[i,2]] = 1
adj_mat_sym[final_edgelist[i,2],final_edgelist[i,1]] = 1
}
M = adj_mat_sym
lower_triangle = M[lower.tri(M)]
lower_triangle_2 = lower_triangle
lower_triangle_2[lower_triangle_2==0] = 2
lower_triangle_2[lower_triangle_2==1] = 0
lower_triangle_2[lower_triangle_2==2] = 100
d <- as.dist(1/(1+adj_mat_2))
d_5 = d
d_5[1:length(d_5)] = lower_triangle_2[1:length(lower_triangle_2)]
d_6 <- (1/(1+d_5))
d_7 = d_6
d_7[d_7==1] = 0
# tsp <- TSP(d_6)
tsp <- TSP(d_7)
# tsp_check <- TSP(d)
# o2 <- solve_TSP(tsp)
# o2
# as.integer(o2)
o2 <- solve_TSP(tsp, method="concorde",rep=10, control = list(clo = "-V"))
# o2 <- solve_TSP(tsp_check, method="concorde",rep=10, control = list(clo = "-V"))
o2
as.integer(o2)
我希望这能消除任何疑问。