Swift で巡回セールスマン問題の対応 (クリストフィードアルゴリズム)

General, Swift

Swift での例がなかったので既存の焼き直しコードです・・・

だいぶ前の書きかけ記事が眠っていたので確認せず公開。多分動くとは思います。
使用方法コードなくてすみませんが、CLLocationCoordinate2Dの複数地点情報を christofidesTSP に渡せばそれっぽく動くとは思います。元記事を書いたのが昔すぎてちょっと記憶にない。

import Foundation
import CoreLocation

struct GraphEdge {
    let u: Int
    let v: Int
    let weight: Double
}

// クリストフィードのアルゴリズムによるTSP(Traveling Salesman Problem)解法
public func christofidesTSP(coordinates: [CLLocationCoordinate2D]) -> ([Int], Double) {
    // 1. 最小全域ツリーを構築
    let mst = minimumSpanningTree(coordinates: coordinates)
    
    // 2. 次が奇数の頂点を探す
    let oddVertices = oddDegreeVertices(mst: mst, count: coordinates.count)
    
    // 3. 次が奇数の頂点間の最小マッチングを行う
    let matching = minimumMatching(oddVertices: oddVertices, coordinates: coordinates)
    
    // 4. オイラー閉路を作成し、巡回セールスマン問題の解に変換
    let tspPath = eulerTourAndTSP(mst: mst, matching: matching, count: coordinates.count)
    
    // 5. 経路の合計距離を計算
    var totalDistance = 0.0
    for i in 0..<(tspPath.count - 1) {
        totalDistance += getStraightDistance(source: coordinates[tspPath[i]], destination: coordinates[tspPath[i + 1]])
    }
    totalDistance += getStraightDistance(source: coordinates[tspPath.last!], destination: coordinates[tspPath.first!])
    return (tspPath, totalDistance)
}

// クラスカル法による最小全域木の構築
private func minimumSpanningTree(coordinates: [CLLocationCoordinate2D]) -> [GraphEdge] {
    let count = coordinates.count
    var edges: [GraphEdge] = []
    var mst: [GraphEdge] = []
    var parent = Array(0..<count)

    for i in 0..<count {
        for j in (i + 1)..<count {
            let distance = getStraightDistance(source: coordinates[i], destination: coordinates[j])
            edges.append(GraphEdge(u: i, v: j, weight: distance))
        }
    }
    edges.sort(by: { $0.weight < $1.weight })
    
    for edge in edges {
        let u = edge.u
        let v = edge.v
        if cycleDetectionFind(u, &parent) != cycleDetectionFind(v, &parent) {
            mst.append(edge)
            cycleDetectionUnion(u, v, &parent)
        }
        if mst.count == count - 1 {
            break
        }
    }
    return mst
}

private func cycleDetectionFind(_ u: Int, _ parent: inout [Int]) -> Int {
    if parent[u] != u {
        parent[u] = cycleDetectionFind(parent[u], &parent)
    }
    return parent[u]
}

private func cycleDetectionUnion(_ u: Int, _ v: Int, _ parent: inout [Int]) {
    let rootU = cycleDetectionFind(parent[u], &parent)
    let rootV = cycleDetectionFind(parent[v], &parent)
    parent[rootU] = rootV
}

// 次数が奇数の頂点を見つける
private func oddDegreeVertices(mst: [GraphEdge], count: Int) -> [Int] {
    var degree = Array(repeating: 0, count: count)
    for edge in mst {
        degree[edge.u] += 1
        degree[edge.v] += 1
    }
    
    var oddVerices: [Int] = []
    for i in 0..<count {
        if degree[i] % 2 != 0 {
            oddVerices.append(i)
        }
    }
    return oddVerices
}

// 貪欲法による最小完全マッチング
private func minimumMatching(oddVertices: [Int], coordinates: [CLLocationCoordinate2D]) -> [GraphEdge] {
    var edges: [GraphEdge] = []
    var used = Array(repeating: false, count: coordinates.count)
    
    for i in 0..<oddVertices.count {
        if used[oddVertices[i]] { continue }
        var minDistance = Double.infinity
        var closest = -1
        for j in (i + 1)..<oddVertices.count {
            if used[oddVertices[j]] { continue }
            let distance = getStraightDistance(source: coordinates[oddVertices[i]], destination: coordinates[oddVertices[j]])
            if distance < minDistance {
                minDistance = distance
                closest = j
            }
        }
        edges.append(GraphEdge(u: oddVertices[i], v: oddVertices[closest], weight: minDistance))
        used[oddVertices[i]] = true
        used[oddVertices[closest]] = true
    }
    return edges
}

// オイラー閉路を作り、巡回セールスマン問題の解に変換する関数(Traveling Salesman Problem)
private func eulerTourAndTSP(mst: [GraphEdge], matching: [GraphEdge], count: Int) -> [Int] {
    var graph = Array(repeating: [Int](), count: count)
    for edge in (mst + matching) {
        graph[edge.u].append(edge.v)
        graph[edge.v].append(edge.u)
    }
    // オイラー閉路を作成
    var visited = Array(repeating: false, count: count)
    var path: [Int] = []
    dfs(u: 0, visited: &visited, path: &path, graph: &graph)
    
    var tspPath: [Int] = []
    var seen = Array(repeating: false, count: count)
    for vertex in path {
        if seen[vertex] == false {
            tspPath.append(vertex)
            seen[vertex] = true
        }
    }
    return tspPath
}

// 深さ優先探索(Depth-First Search)
private func dfs(u: Int, visited: inout [Bool], path: inout [Int], graph: inout [[Int]]) {
    visited[u] = true
    path.append(u)
    for v in graph[u] {
        if visited[v] == false {
            dfs(u: v, visited: &visited, path: &path, graph: &graph)
        }
    }
}

public func getStraightDistance(source: CLLocationCoordinate2D, destination: CLLocationCoordinate2D) -> Double {
    let RX: Double = 6378.137   // 回転楕円体の長半径 (赤道半径) [km]
    let RY: Double = 6356.752   // 回転楕円体の短半径 (極半径) [km]
    
    let s_x = deg2rad(source.longitude)
    let s_y = deg2rad(source.latitude)
    let d_x = deg2rad(destination.longitude)
    let d_y = deg2rad(destination.latitude)
    let p1 = atan(RY / RX * tan(s_y))
    let p2 = atan(RY / RX * tan(d_y))
    let X = acos(sin(p1) * sin(p2) + cos(p1) * cos(p2) * cos(s_x - d_x))
    let F = (RX - RY) / RX
    let dr = F / 8 * ((sin(X) - X) * pow(sin(p1) + sin(p2), 2.0) / pow(cos(X / 2), 2.0) - (sin(X) + X) * pow((sin(p1) - sin(p2)), 2.0) / pow(sin(X / 2), 2.0))
    return RX * (X + dr)
}

private func deg2rad(_ number: Double) -> Double {
    return number * .pi / 180
}

フォローする