一、项目介绍
项目介绍
公司有个项目，在城市里有80多个景点，用户任意选n个景点，我需要帮他算出最合适的路线
需求说明
从80个景点里面，选出n个景点，找到最短的路线
二、思路
最先想到的就是floyd算法，但是这个算法只能找到任意两点的最短路径和时间。不过找到这个数据后，再来解决旅行商问题就更方便了
准备资料
运营给了我一份85个景点的准确坐标，我用googlemap的测距接口，找到了任意点的距离
三、计算任意两点的最短距离和路径
这个就直接用floyd算法来解决了：
比如这个例子，已知4个点之间的相邻两点距离，求任意两点之间的最短距离：
1、先把距离数据看做一个矩阵，如下图
如果必须途径1号顶点，求任意两点之间的最短路程，应该如何求呢？
只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1到n循环，j也是1到n循环，代码实现如下。
for( i=1; i<=n; i++) {
for( j=1; j<=n; j++ ) {
if ( e[i][j] > e[i][1]+e[1][j] ) {
e[i][j] = e[i][1]+e[1][j];
}
}
}
在只允许经过1号顶点的情况下，任意两点之间的最短路程更新为：
通过上图我们发现：在只通过1号点中转的情况下，3号顶点到2号顶点（e[3][2]）、4号顶点到2号顶点（e[4][2]）以及4号顶点到3号顶点（e[4][3]）的路程都变短了。
接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小，代码实现为如下。
//经过1号顶点
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if (e[i][j] > e[i][1]+e[1][j]) {
e[i][j]=e[i][1]+e[1][j];
}
}
}
//经过2号顶点
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++){
if (e[i][j] > e[i][2]+e[2][j]) {
e[i][j]=e[i][2]+e[2][j];
}
}
}
在只允许经过1和2号顶点的情况下，任意两点之间的最短路程更新为：
通过上图得知，在相比只允许通过1号顶点进行中转的情况下，这里允许通过1和2号顶点进行中转，使得e[1][3]和e[4][3]的路程变得更短了。
同理，继续在只允许经过1、2和3号顶点进行中转的情况下，求任意两点之间的最短路程。任意两点之间的最短路程更新为：
最后允许通过所有顶点作为中转，任意两点之间最终的最短路程为：
整个算法过程虽然说起来很麻烦，但是代码实现却非常简单，核心代码只有五行：
for(k=1;k<=n;k++){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(e[i][j]>e[i][k]+e[k][j]){
e[i][j]=e[i][k]+e[k][j];
}
}
}
}
这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。其实这是一种“动态规划”的思想。
四、TSP和ATSP
计算完最短路径，开始了重点，就是tps问题。
谈到tsp有个最笨得办法就是穷举法，就是排列组合算出所有可能的路径，并找出最短的那条。这个方法实践后发现，当线路点超过8个点的时候，时间就满的不能忍受了，但是少于8个点的时候，这个方法无疑是最好最准确的答案
当大于8个点的时候，tsp问题就需要用技巧来解决了，超越了很多资料，目前人类还没有找到答案，只有在有限时间内找到最接近的精确答案。必经n个点的可能性就由n!种结果。10!就是300万种。目前解决算法有：遗传算法、神经网络算法、蚁群算法、退火堆算法等。我这次使用的时遗传算法不同的是我的路线是非对称的，也就是A到B点，去回的距离是不一样的，不过这个不影响
五、ATSP改进版，
ATSP都是回路的，一个点出发，最后回到这个点。对于不同的起点，终点其实就是算距离的时候，把起点，终点加上就行了在这里，我打算小于7个点的时候用穷举法，因为这样可以在最短时间得到100%准确的答案
下面说说遗传算法吧：
简单的理解就是：把经过的城市当DNA片段，随机造50个人，让他们交叉配对，并且加上一个变异几率，生成第后代，然后优胜劣汰把路线最短的选出来，再生后代，最后选出最优的。这里的重点就是 交叉配对、变异和遗传
遗传算法自身参数设定
遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
交叉配对：
部分匹配法（Partially Matching Crossover， PMX）
以两个父代个体为例：（1 2 3 4 5 6 7 8）和（2 4 6 8 7 5 3 1），随机选择两个交叉的点，假如第一个点为位置4，第二个交叉点为位置6，那么在两个点之间的位置将进行交叉，其它的位置进行复制或者用相匹配的数进行替换。在此实例中，第一个父代个体中4 5 6被选中，第二个父代个体中，8 7 5被选中。那么4 与8，5与7,6与5相匹配。匹配过程和如图2所示。
图2 PMX交叉操作
首先将4 5 6与8 7 5分别加入到子代2和子代1中相应的位置，然后将其他位置上的数字直接复制到相应的后代中，如果该数字已经在该子代中已经存在，则用相应的匹配法则进行替换，例如子代1中将7复制进去的时候，发现7已经存在在子代中，通过查找相应的匹配法则，发现，7与5匹配，然后复制5，又发现5也已经存在在该子代中，在此查找匹配法则，发现5与6匹配，将6复制，6不存在在该子代中，所以可以将6复制进去，如此反复，知道子代中城市的数目达到定义的长度，该子代创建完成。
变异：
简单倒位变异（Simple Inversion Mutation， SIM）
SIM先从父代个体中选择一个基因串，然后将这个基因串中所有的基因倒位放置，如图11所示。
其实交叉配对和变异有很多种，详细参见：
http://www.cnblogs.com/biaoyu/archive/2012/10/02/2710267.html
经过多次的进化，最后就得到了最适应的路线
六、代码实现 playground xcode6.3运行通过
import Foundation
import UIKit
/**
* TSP-遗传算法
* lizyyy@gmail.com
*/
class MGraph{
var vexs = [String]() //顶点数组
var arc = Dictionary< String,Dictionary<String,Int> >() //边邻接矩阵,即二维数组
var arcData = Dictionary<String,Int>() //边的数组信息
private var infinity = 9999999
init(vexs :[String] ,arcData: Dictionary<String,Int>){
self.vexs = vexs
self.arcData = arcData
self.initalizeArc()
self.createArc()
}
func floyed() -> (path:Dictionary<String,[String]>,distance: Dictionary<String,Int>, points:[String]) {
var path = Dictionary<String,Dictionary<String,String>>() //路径数组
var distance = Dictionary<String,Dictionary<String,Int>>() //距离数组
for (k,v) in arc{
var tmp1 = Dictionary<String,String>()
var tmp2 = Dictionary<String,Int>()
for (k0,v0) in v{
tmp1[k0] = k0
tmp2[k0] = v0
}
path[k] = tmp1
distance[k] = tmp2
}
for (k1,v1) in enumerate(vexs){
for (k2,v2) in enumerate(vexs){
for (k3,v3) in enumerate(vexs){
if( distance[ vexs[k2] ]![vexs[k3]]! > distance[ vexs[k2] ]![vexs[k1]]! + distance[ vexs[k1] ]![vexs[k3]]! ){
path[ vexs[k2] ]![vexs[k3]]! = path[ vexs[k2] ]![vexs[k1]]!
distance[ vexs[k2] ]![vexs[k3]]! = distance[ vexs[k2] ]![vexs[k1]]! + distance[ vexs[k1] ]![vexs[k3]]!
}
}
}
}
//计算路径
var rsPath = Dictionary<String,[String]>()
var rsDistance = Dictionary<String,Int>()
for (ka,va) in enumerate(vexs){
for (kb,vb) in enumerate(vexs){
var from = [va]
route(path, from: va, to: vb, o: &from)
rsPath["\(va),\(vb)"] = from
rsDistance["\(va),\(vb)"] = distance[va]?[vb]
}
}
return (path:rsPath,distance:rsDistance,points:vexs)
}
func route(s:Dictionary<String,Dictionary<String,String>>,from f:String,to t:String, inout o:[String]){
if s[f]![t]! != t {
o.append(s[f]![t]!)
route(s,from: s[f]![t]! ,to: t, o: &o)
}else{
if (f != t) { o.append(t)}
}
}
func initalizeArc(){
for (k,v) in enumerate(vexs){
var tmp = Dictionary<String,Int>()
for (k1,v1) in enumerate(vexs){
tmp[v1] = v == v1 ? 0 : infinity
}
arc[v] = tmp
}
}
func createArc(){
for (k,v) in arcData{
var arr = k.componentsSeparatedByString(",")
var from = arr[0]
var to = arr[1]
arc[from]?[to] = v
}
}
}
extension Array {
mutating func shuffle() {
for _ in 0..<self.count {
sort { (_,_) in arc4random() < arc4random() }
}
}
}
//==================
class TspGenetic{
var data = (path:Dictionary<String,[String]>(),distance: Dictionary<String,Int>(), points:[String]() )
var from = String()
var to = String()
var through = [String]()å
var solutions = Array<Array<String>>()
var initialPopulationSize = 30 //初始50人口数量,50条线路
var maxEvolutionSteps = 2 //进化次数
var roundPopulationSize = 10 //每次取进化最好的前10个
var mutationProbability :Double = 0.5 //突变几率
init(source : (path:Dictionary<String,[String]>,distance: Dictionary<String,Int>, points:[String] ) ){
self.data = source
for (k,v) in enumerate(source.points){
data.path["\(v),\(v)"] = ["\(v)","\(v)"]
data.distance["\(v),\(v)"] = 0
}
}
func routeThrough(from f:String,to t:String,through tr:[String]) -> (route:[String],distance:Int,path:[String]) {
self.from = f;self.to = t;self.through = tr
if( through.count < 4 ){//4个以下穷举
var out = (path:Array<[String]>(),distance:Array<Int>())
getAllPermutation(tr,index: 0,o: &out)
var index = find(out.distance, minElement(out.distance))
return (route:routes(out.path[index!]),distance:out.distance[index!],path:out.path[index!])
}else{//4个以上遗传算法
var rs = self.evolution() //进化
self.doSelection(1)
var route = [from] + solutions[0] + [to]
return (route:routes(route),distance:distance(route),path:route)
}
}
func getAllPermutation(var a:[String],index:Int,inout o:(path:Array<[String]>,distance:Array<Int>)){
if(index == a.count-1){
var r = [String]()
for i in 0 ..< a.count {
r.append(a[i])
}
o.path.append( [from] + r + [to] )
o.distance.append(distance([from] + r + [to]))
return
}
for i in index ..< a.count {
swap(&a[index], &a[i])
getAllPermutation(a, index: index+1,o: &o)
swap(&a[index], &a[i])
}
}
//进化
func evolution() -> (route:[String],distance:Int,path:[String]) {
initializePopulation() //初始50人，即随机选出50条线路
var iEvolutionStep = 0;
do {
// 选中10个优良的市民，即最短路线前十名
self.doSelection(roundPopulationSize)
// 对优良路线基因重组,即路线优化？
self.doRecombination()
// 基因突变，即路线改变
self.doMutation(mutationProbability);
iEvolutionStep++;
} while(iEvolutionStep < maxEvolutionSteps);
return (route:[""],distance:10,path:[""])
}
/**
* 获取一个点到另一个点的距离
* distance(distanceData, route:(outs1 + outs2))
*/
func distance(route:[String]) -> Int{
var m = 0
for i in 0 ..< route.count-1 {
if ((data.distance["\(route[i]),\(route[i+1])"] ) != nil) {
m += data.distance["\(route[i]),\(route[i+1])"]!
}else{ m += 999999 }
}
return m
}
//两点间的路径
func routes(pointRoute:[String]) -> [String]{
var route = [String]() //d,c,a
for i in 0 ..< pointRoute.count-1 {
var tmp = data.path["\(pointRoute[i]),\(pointRoute[i+1])"]
if(i < pointRoute.count-2){
tmp?.removeLast()
}
route += tmp!
}
return route
}
func randomInRange(range: Range<Int>) -> Int {
let count = UInt32(range.endIndex - range.startIndex)
return Int(arc4random_uniform(count)) + range.startIndex
}
func initializePopulation(){
for i in 0 ..< initialPopulationSize {
through.shuffle()
solutions.append(through)
}
}
//每次取进化最好的前n名，即线路最短的前n名
func doSelection(roundPopulationSize:Int) {
var rs = sorted(solutions, {(s1,s2) -> Bool in
var dis1 = self.distance([self.from] + s1 + [self.to])
var dis2 = self.distance([self.from] + s2 + [self.to])
return dis1<dis2
})
self.solutions = Array(rs[0 ..< roundPopulationSize])
}
// 对优良路交叉匹配（部分匹配法PMX)
func doRecombination() {
solutions
var children = Array<[String]>() //后代新线路
for (k,v) in enumerate(solutions){
for (k1,v1) in enumerate(solutions){
if(k != k1){
children.append(getChildWith(v,solutions1:v1))
}
}
}
self.solutions = children
}
func getChildWith(solutions:[String],var solutions1:[String]) -> [String]{
var b = randomInRange(0...solutions1.count-2)
var e = randomInRange(2...(solutions1.count-b))
var range = Range(b...(b+e-1))
var xx = solutions[range]
var xx1 = solutions1[range]
solutions1.replaceRange(range, with: Array(count: e, repeatedValue:""))
pmx(&solutions1,xx:Array(xx),xx1:Array(xx1))
solutions1.replaceRange(range, with: (xx))
return solutions1
}
func pmx(inout output:[String],xx:[String],xx1:[String]) {
for (k,v) in enumerate(xx){
if contains(output, v) {
var i = find(xx, v)
var ixx = find(output, v)
output[ixx!] = xx1[i!]
pmx(&output,xx:xx,xx1:xx1)
}
}
}
func doMutation(mutationProbability:Double){
for (k,v) in enumerate(solutions){
var random = Double(randomInRange(0...100))/100.00
if random < mutationProbability {
self.mutate(v)
}
}
}
//倒位变异（Inversion Mutation， IVM）
func mutate(var solution:[String])->[String] {
var b = randomInRange(0...solution.count-2)
var e = randomInRange(2...(solution.count-b))
var range = Range(b...(b+e-1))
solution.replaceRange(range, with: reverse(solution[range]))
return solution
}
}
var vexs = ["a","b","c","d","e","f","g"]
var arcData = ["a,b":4,"a,c":2,"a,d":3,"b,c":5,"b,e":3,"b,d":4,"c,d":1,"c,f":2,"d,e":6,"d,f":2,"e,f":4,"b,a":4,"c,a":2,"d,a":3,"c,b":5,"e,b":3,"d,b":4,"d,c":1,"f,c":2,"e,d":6,"f,d":2,"f,e":4]
var t = MGraph(vexs: vexs,arcData:arcData)
var rs = t.floyed()
//=======
var from = "a"
var to = "a"
var through = ["f","c","b","e","d"]
// "a到a 必须经过[c, b, e, f, d]的顺序是[a, c, d, f, e, b, a],距离为:16,路径:[a, c, d, f, e, b, a]"
var route = TspGenetic(source:rs)
var rsRoute = route.routeThrough(from: from, to: to, through:through)
println("\(from)到\(to) 必须经过\(through)的顺序是\(rsRoute.2),距离为:\(rsRoute.1),路径:\(rsRoute.0)")
