Swift4 各座標点を通る最短経路っぽいモノの表示

# 最短経路っぽいモノの求め方
1. その時点での最小経路長に該当する巡回パターン（最小路）から少しの違う巡回パターン（d最小路）を発生させる．
2. 最小路とd最小路の大小を比較する．
3. １と２を１万回ほど試行し，　終了時点での最短経路長に該当する巡回パターンが最短経路．

上記で局所解に捕らわれにくくする為に，　あえて一定確率で最小ではない巡回パターンを最短路としている．

# 実装
```ViewController.swift
import UIKit

class ViewController: UIViewController {

    @IBOutlet weak var pathView: UIView!
    @IBOutlet weak var runBtn: UIButton!
    
    var points: [CGPoint] = [];
    
    override func viewDidLoad() {
        super.viewDidLoad();
    }

    func putPoint(location: CGPoint) {
        // UIImage インスタンスの生成
        let manImage:UIImage = UIImage(named:"yokokara_shitsurei")!;
        // UIImageView 初期化
        let imageView = UIImageView(image:manImage);
        // 画像の縦横サイズを取得
        let imgWidth:CGFloat = manImage.size.width/10;
        let imgHeight:CGFloat = manImage.size.height/10;
        let rect:CGRect =
            CGRect(x:0, y:0, width:imgWidth, height:imgHeight);
        // ImageView frame をCGRectで作った矩形に合わせる
        imageView.frame = rect;
        // 画像の中心を画面の中心に設定
        imageView.center = CGPoint(x:location.x, y:location.y);
        // UIImageViewのインスタンスをビューに追加
        self.pathView.addSubview(imageView);
    }
    
    override func touchesBegan(_ touches: Set<UITouch>, with event: UIEvent?) {
        for touch in touches {
            let location = touch.location(in: pathView);
            self.putPoint(location: location );
            self.points.append(location);
            self.runBtn.isEnabled = true;
            print(location);
        }
    }
    
    @IBAction func runBtn(_ sender: Any) {
        let travelingSalesman: TravelingSalesman = TravelingSalesman(points: self.points, superView: self.view, pathView: self.pathView);
        let resultPaths = travelingSalesman.execute();
        travelingSalesman.drawPathLines(resultPaths: resultPaths, superView: self.view, pathView: self.pathView);
    }
    
}

class Draw2D: UIView {
    
    private var resultPaths: [CGPoint] = [];
    
    func getResultPaths(resultPaths: [CGPoint] ) {
        self.resultPaths = resultPaths;
    }
    
    override func draw(_ rect: CGRect) {
        let context = UIGraphicsGetCurrentContext()
        context?.setLineWidth(2.0)
        let colorSpace = CGColorSpaceCreateDeviceRGB()
        let components: [CGFloat] = [0.0, 0.0, 1.0, 1.0]
        let color = CGColor(colorSpace: colorSpace, components: components)
        context?.setStrokeColor(color!)
        context?.move(to: resultPaths[0]);
        for i in 1..<resultPaths.count {
            context?.addLine(to: resultPaths[i]);
        }
        context?.strokePath()
    }
}

```

```TravelingSalesman.swift
import UIKit

class TravelingSalesman {
    private var points: [CGPoint] = [];
    private let exeCount: Int = 100000;
    private let tempreture: CGFloat = 10.0;
    private let cooler: CGFloat = 0.9;
    
    private let superView: UIView;
    private let pathView: UIView;
    
    init(points: [CGPoint], superView: UIView, pathView:UIView) {
        self.points = points;
        self.superView = superView;
        self.pathView = pathView;
    }
    
    public func execute() -> [CGPoint] {
        do {
            if self.points.isEmpty {
                throw NSError(domain: "in execute, points is empty.", code: -1, userInfo: nil)
            }
            var minPaths: [CGPoint] = self.points;
            for i in 0..<exeCount {
                var random1 = Int.random(in: 0..<self.points.count);
                var random2 = Int.random(in: 0..<self.points.count);
                if(random1 > random2){
                    swap(&random1, &random2)
                }
                let testPaths: [CGPoint] = self.reverseArray(array: minPaths, head: random1, tail: random2) as! [CGPoint];
                let dE = try self.sumDist(points: testPaths) - self.sumDist(points: minPaths);
                if(dE > 0) {
                    let exp_dE = exp(dE * -1 / tempreture);
                    let random_dE = CGFloat.random(in: 0..<1);
                    if(exp_dE > random_dE) {
//                        print("not minimum, but change paths.");
                        minPaths = testPaths;
                    }
                } else {
//                    print("change paths. \(i)");
                    minPaths = testPaths;
                }
            }
            print("sumDist is \(try self.sumDist(points: minPaths))");
            return minPaths;
        } catch {
            print("Error: in TravelingSalesman, execute().")
            return [];
        }
    }
    
    public func drawPathLines(resultPaths: [CGPoint], superView: UIView, pathView: UIView) {
        superView.viewWithTag(999)?.removeFromSuperview();
        let draw2D: Draw2D = Draw2D(frame: pathView.frame);
        draw2D.tag = 999;
        draw2D.isOpaque = false;
        draw2D.backgroundColor = UIColor.init(red: 0, green: 0, blue: 0, alpha: 0);
        draw2D.getResultPaths(resultPaths: resultPaths);
        superView.addSubview(draw2D);
    }
    
    private func reverseArray(array: Array<Any>, head: Int, tail: Int) -> Array<Any>{
        var results: Array<Any> = array;
        let swapCount: Float = (Float(tail) - Float(head))/2.0;
        for i in 0..<Int(swapCount.rounded()) {
            results.swapAt(head+i, tail-i);
        }
        return results;
    }
    
    private func dist(p1: CGPoint, p2: CGPoint) -> CGFloat {
        let dx = CGFloat(p1.x - p2.x);
        let dy = CGFloat(p1.y - p2.y);
        return sqrt(dx*dx + dy*dy);
    }
    
    private func sumDist(points: [CGPoint]) throws -> CGFloat {
        if points.isEmpty {
            throw NSError(domain: "in sumDist, points is empty.", code: -1, userInfo: nil)
        }
        var sum: CGFloat = 0.0;
        var lastPoint: CGPoint = points[0];
        for point in points {
            sum += self.dist(p1: lastPoint, p2: point);
            lastPoint = point;
        }
        return sum;
    }
}

```

# 解説
```ViewController.swift
func putPoint(location: CGPoint) {...}
```
引数で受け取った座標に画像を貼り付けます．

```ViewController.swift
override func touchesBegan(_ touches: Set<UITouch>, with event: UIEvent?) {...}
```
画面をタップした時の座標を座標配列pointsに格納．
画面をタップした時の座標に画像を貼り付ける．

```ViewController.swift
override func draw(_ rect: CGRect) {...}
```
座標配列の座標間を線でつなぐ．

TravelingSalesman.swiftに関しては以前掲載した記事のRuby版をSwift版で書き直しているだけです．
> https://qiita.com/takakikata/items/0939b92a483409b888ab

# 動作
![screen.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/241421/efb32f7c-cef0-ade0-0101-ef6c106aff33.gif)