solve_TSP(TSP)
solve_TSP()所属R语言包：TSP
TSP solver interface
TSP求解器接口
译者：生物统计家园网 机器人LoveR
描述----------Description----------
Common interface to all TSP solvers in this package.
在此包中的所有TSP求解器的通用接口。
用法----------Usage----------
solve_TSP(x, method, control)
参数----------Arguments----------
参数：x
the TSP given as an object of class TSP or ATSP.
该TSP对象的类TSP或ATSP。
参数：method
method to solve the TSP (default: nearest insertion algorithm; see details).
的方法来解决TSP（默认：最近插入算法;见详情）。
参数：control
a list of arguments passed on to the TSP solver selected by method.
列表中的参数传递的TSP求解器选择method。
Details
详细信息----------Details----------
Currently the following methods are available:
目前可用以下方法：
Nearest, farthest, cheapest and arbitrary insertion algorithms for a symmetric and asymmetric TSP (Rosenkrantz et al. 1977).
最近，最远，最便宜的和任意插入算法，对称和非对称TSP（Rosenkrantz等人，1977）。
The distances between cities are stored in a distance matrix D with elements d(i,j). All insertion algorithms start with a tour consisting of an arbitrary city and choose in each step a city k not yet on the tour. This city is inserted into the existing tour between two
城市之间的距离被存储在距离矩阵D与元素d(i,j)。所有插入算法开始的任意一个城市的旅游咨询，并在每一步中选择一个城市k：“还没有在巡回赛上。这个城市被插入到现有的两个旅游
is minimized. The algorithms stops when all cities are on the tour.
被最小化。算法停止时，所有的城市都是在巡回赛上。
The nearest insertion algorithm chooses city k in each step as the city which is nearest to a city on the tour.
最近的插入算法选择城市k的每一步，这是离城市最近的旅游城市。
For farthest insertion, the city k is chosen in each step as the city which is farthest to any city on the tour.
最远的插入，城市k在每一个步骤中选择的最远的城市，是任何一个城市的旅游。
Cheapest insertion chooses the city k such that the cost of inserting the new city (i.e., the increase in the tour's length) is minimal.
最便宜的插入选择的城市k的，插入新城市（即增加游览的长度）的成本是最小的。
Arbitrary insertion chooses the city k randomly from all cities not yet on the tour.
任意插入选择的城市k随机从所有城市还没有在巡回赛上。
Nearest and cheapest insertion tries to build the tour using cities which fit well into the partial tour constructed so far. The idea behind behind farthest insertion is to link cities far away into the tour fist to establish an outline of the whole tour early.
最近，最便宜的插入试图建立使用很好地适应迄今为止共建造的部分旅游城市的旅游。后面最远的插入背后的想法是远离城市联系在一起的旅游拳头尽早建立一个轮廓，整个巡回赛。
Additional control options:
其他控制选项：
start index of the
start的索引
Nearest neighbor and repetitive nearest neighbor algorithms for symmetric and asymmetric TSPs (Rosenkrantz et al. 1977).
最近的邻居和重复最近邻居算法，对称和非对称的TSP（Rosenkrantz等。1977年）。
The algorithm starts with a tour containing a random city. Then the algorithm always adds to the last city on the tour the nearest not yet visited city. The algorithm stops when all cities are on the tour.
该算法从一个包含随机城市的旅游。算法总是在巡回赛上最近的尚未访问过的城市增加了最后一个城市。算法停止时，所有的城市都是在巡回赛上。
Repetitive nearest neighbor constructs a nearest neighbor tour for each city as the starting point and returns the shortest tour found.
重复最近的邻居参观每个城市为出发点构建了一个最近的邻居，并返回找到的最短旅游。
Additional control options:
其他控制选项：
start index of the
start的索引
"2-opt" Two edge exchange improvement procedure (Croes 1958).
"2-opt"两个边缘交换的改善过程（CROES 1958年）。
This procedure systematically exchanges two edges in the graph represented by the distance matrix till no improvements are possible. Exchanging two edges is equal to reversing part of the tour. The resulting tour is called 2-optimal.
此过程系统交流直到没有任何改进的距离矩阵表示的图中的两个边缘是可能的。交换两个边等于扭转的巡演的一部分。将所得游览被称为2 - 最优。
By default, improvement starts with a random tour.
默认情况下，改善启动一个随机的旅游。
Additional control options:
其他控制选项：
tour an existing tour which should be improved.
tour应改善现有的旅游。
rep number of times to try 2-opt with a different initial
rep的次数尝试2 - 选择具有不同的初始
"concorde" Concorde algorithm (Applegate et al. 2001).
"concorde"协和算法（Applegate等人，2001）。
Concorde is an advanced exact TSP solver for only symmetric TSPs based on branch-and-cut. The program is not included in this package and has to be obtained and installed separately (see Concorde).
协和是一种先进的精确的TSP求解器，为对称的TSP分支和切割的基础上。该方案不仅包含在这个套件，必须获得单独安装（见Concorde）。
Additional control options:
其他控制选项：
exe a character string containing the path to the executable
exe一个字符串包含可执行文件的路径
clo a character string containing command line options for Concorde, e.g., control = list(clo = "-B -v"). See concorde_help on how to obtain a complete list of available
clo一个字符串包含的命令行选项协和，例如，control = list(clo = "-B -v")。 concorde_help如何获得完整列表，
precision an integer which controls the number of decimal places used for the internal representation of distances in Concorde. The values given in x are multiplied by 10^{precision} before being passed on to Concorde. Note that therefore the results produced by Concorde (especially lower and upper bounds) need to be divided by 10^{precision} (i.e., the decimal point has to be shifted precision placed to the left). Note also, that Concorde cannot handle Inf which is therefore replaced by 2 times the maximum value in x (ignoring the infinity entries). The interface to Concorde uses write_TSPLIB (see there for more
precision整数的小数位数的内部表示在协和广场的距离控制。给出的值在x乘以10^{precision}之前被传递到协和。协和（尤其是上限和下限）所产生的结果，因此需要划分10^{precision}（即小数点将转移precision放在左边）。还请注意，，协和无法处理Inf因此，更换了2倍，最大值x（忽略了无穷项）。到协和广场的接口使用了write_TSPLIB（看到有更多的
"linkern" Concorde's Chained Lin-Kernighan heuristic (Applegate et al. 2003).
"linkern"协和的链式Lin-Kernighan启发式算法（Applegate等人，2003年）。
The Lin-Kernighan (Lin and Kernighan 1973) heuristic uses variable k edge exchanges to improve an initial tour. The program is not included in this package and has to be obtained and installed separately (see Concorde).
基于Lin-Kernighan启发式（林和Kernighan 1973年）使用变量k边交流，以提高初始游。该方案不仅包含在这个套件，必须获得单独安装（见Concorde）。
Additional control options: see Concorde above.
其他控制选项：协和以上。
值----------Value----------
An object of class TOUR.
对象的类TOUR。
参考文献----------References----------
which do not conform to the template paradigm, Computational Combinatorial Optimization, M. Junger and D. Naddef (editors), Springer.
Traveling Salesman Problems. INFORMS Journal on Computing, 15(1):82–92.
Operations Research, 6(6):791–812.
traveling-salesman problem. Operations Research, 21(2): 498–516.
procedures. In P.M. Pardalos and M.G.C. Resende, editors, Handbook of Applied Optimization, pp. 168–181.
several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563–581.
参见----------See Also----------
TOUR, TSP, ATSP, write_TSPLIB, Concorde.
TOUR，TSP，ATSP，write_TSPLIB，Concorde。
实例----------Examples----------
data("USCA50")
## create TSP[＃创建TSP]
tsp <- USCA50
## methods[＃方法]
methods <- c("nearest_insertion", "cheapest_insertion", "farthest_insertion",
"arbitrary_insertion", "nn", "repetitive_nn", "2-opt")
## calculate tours[＃计算之旅]
tours <- lapply(methods, FUN = function(m) solve_TSP(tsp, method = m))
names(tours) <- methods
## use the external solver which has to be installed separately[＃使用外部求解器单独安装]
## Not run: [＃不运行：]
tours$concorde <- solve_TSP(tsp, method = "concorde")
tours$linkern <- solve_TSP(tsp, method = "linkern")
## End(Not run)[＃（不执行）]
## show first tour[＃第一次巡回演出]
tours[[1]]
## compare tour lengths[＃比较旅游的长度。]
opt <- 14497 # optained by concorde[optained由协和]
tour_lengths <- c(sapply(tours, FUN = attr, "tour_length"), optimal = opt)
dotchart(tour_lengths/opt*100-100, xlab = "percent excess over optimum")
转载请注明:出自 生物统计家园网(http://www.biostatistic.net)。
注：
注1：为了方便大家学习，本文档为生物统计家园网机器人LoveR翻译而成，仅供个人R语言学习参考使用，生物统计家园保留版权。
注2：由于是机器人自动翻译，难免有不准确之处，使用时仔细对照中、英文内容进行反复理解，可以帮助R语言的学习。
注3：如遇到不准确之处，请在本贴的后面进行回帖，我们会逐渐进行修订。
|
发表于 2012-10-1 12:47:34
