바람둥이 석유재벌

당신은 러시아의 석유재벌이며, 유명한 희대의 바람둥이다.
크리스마스를 맞아 30명인 당신의 애인들에게 모두 선물을 주기로 했다.
헬기에 선물을 가득 싣고 당신의 집에서 출발하기로 했다.
하루안에 모두 방문해야 하므로 시간이 촉박하다.
당신의 집에서 30명 모두 방문하고 집에 돌아오기까지의 최단코스를 구해라.
당신의 집의 좌표는 50,50 이고 그 아래 30개의 좌표는 애인들의 집의 좌표이다.
헬기는 무조건 직선으로 이동한다고 가정한다.
출력은 당신집의 좌표를 먼저 출력하고 그 다음 이동할 지점의 좌표30개 출력하고
마지막으로 당신집의 좌표를 출력한다.
마지막으로 총 이동거리를 출력한다.(소수점이하 버림)
data는 화일로 저장해서 화일에서 읽어들여도 된다.
DATA

50 50
26 23
50 95
85 66
67 40
46 12
6 2
51 12
44 30
4 56
61 14
73 6
74 72
51 52
7 40
31 66
8 16
62 70
87 19
32 77
56 67
86 50
0 74
65 42
19 97
49 14
4 11
0 19
17 37
46 33
12 90

출력

출력예시(정답이 아님)

50 50
8 16
62 70
.
(중간생략)
.
46 33
12 90
50 50

Total Distance = 1000
TSP
외판원 문제네요. 다항식 시간내에 풀 수 있는 알고리즘이 없다는... 어려운 문제 입니다 ㅜㅜ.. 이리저리 머리를 굴려보아도 답이 안나옵니다.. 유전 알고리즘이나, 2-OPT 알고리즘으로 근사치를 구할 수 있다고 합니다만 저는 좀 더 공부해야 될것 같네요.. - 이 우람, 2016/01/26 01:19 M D
어찌어찌해서 500정도까지는 최소값이 나오는데.. 제가 낸 문제지만, 어려운 문제네요. 제가 푸는 방법을 알고서 낸건 아니고, 그냥 다 같이 고민해보고 배우려는 의도로 낸 문제입니다. - 상파, 2016/01/26 15:06 M D
으아 저는 주로 TSP문제풀때 시간복잡도 O((2^n)n^2)인 다이나믹 프로그래밍 알고리즘을 사용하는데 도시가 31개라서 이 방법으로는 어림도 없겠군요 ㅜㅜㅜ 책을 읽어보니 TSP를 최적으로 해결하기위해 integer programming 이라는 것을 사용한다던데 더 공부해봐야겠어요! - iljimae, 2016/06/04 23:17 M D
석유 재벌이니까 유전 알고리즘을 사용해 보라는 암시가 있다고 느껴서 유전 알고리즘을 사용해 보았습니다. - 이 종성, 2016/09/19 00:48 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

7개의 풀이가 있습니다.

50 50
31 66
32 77
50 95
19 97
12 90
0 74
4 56
7 40
17 37
0 19
4 11
6 2
8 16
26 23
44 30
46 33
46 12
49 14
51 12
61 14
73 6
87 19
67 40
65 42
86 50
85 66
74 72
62 70
56 67
51 52
Total Distance 457

TSP 실행파일 다운로드
개인적으로 풀어보고 싶은 문제라 오늘 종일 풀어봤습니다
머리속으로 이미징하는게 한계가 있어서 실제 진행상황을 보려고 실행파일로 만들어봤구요
급하게 제작하느라 오류가 있을수도 있습니다. 그래도 최대한 기능들을 넣어 봤습니다

이것은 가장 가까운 정확한 값을 찾기보다는 비교적 가까운값을 찾고, 빠르게 결과를 낼 수 있는 방법인것 같습니다
소스가 길기때문에 사용한 알고리즘을 적어보겠습니다

  1. Convex Hull(모든좌표를 감싸는 최소의 다각형)을 구성합니다. 저는 QuickHull 알고리즘으로 구성했습니다
    Convex Hull은 좌표들을 기둥이라고하고 생각하고 하나의 고무줄로 모든 기둥 바깥으로 타이트하게 감싼다고 생각하시면 될것 같구요
    이 고무줄을 최대한 적게 늘려가며 안쪽 기둥들과 걸쳐 가보자 하는 생각으로 진행했습니다

  2. Convex Hull을 구성하는 링크와, 나머지에 좌표에 대해 이어질 수 있는 가장 적은 증가거리와 이어줍니다
    [선분(p1,p2)에서 p3로 연결 시 : Min((Dis(p1,p3) + Dis(p2,p3)) - Dis(p1,p2)) ]

  3. 2를 반복하면서 현재까지 연결된 링크 중 더 적은 거리로 이어질 수 있는 링크로 수정합니다
    [선분(p1,p2)에서 p3로 연결 시 : (Dis(p3.Next,p3) + Dis(p3.Prev,p3) + Dis(p1,p2)) > (Dis(p3,p1) + Dis(p3,p2) + Dis(p3.Next,p3.Prev)) ]

  4. 2를 반복하면서 현재까지 연결된 링크 중 교차된 선분을 풀어줍니다

2,3,4번의 순서는 없습니다. 제 소스도 2,3,4번은 랜덤으로 돌아갑니다. 순서에 따라서 경로가 더 짧아질수도 길어질수도 있기때문입니다
실행 프로그램을 보시면 한단계씩 진행되는 부분을 볼 수 있도록 버튼을 따로 만들어놨는데, 직접 눌러보시면 더 빠른 이해가 가능합니다

실행파일은 .net framework 기반이기 때문에 이것이 없으면 실행 오류가 납니다.
마이크로소프트 공식 홈페이지 링크입니다. Framework 4.5

첫 풀이 축하드리고 감사해요! - 상파, 2016/01/31 20:13 M D
저는 가장 안쪽에 점점 늘어나는 고무줄(?)을 넣고 바깥쪽으로 늘려가는 방법으로 했었는데, 잘 안나오더라구요. 바깥쪽에서 하는 방법은 생각을 못했었네요. 이런방법이! - 상파, 2016/01/31 20:16 M D
네 이 문제는 정말 무수한 많은 방법들이 있을거 같습니다. 이것도 수 많은 방법중에 하나이구요. 실생활에서도 많이 적용된다고 합니다. 예를들어 택배 배달같은 수 많은 경로를 가야된다거나, 기판에 반도체를 꼽는 기계의 최적의 루트같은 것들입니다. 실생활에서는 훨씬더 복잡하고 정교한 기법들이 사용 되고 있다고 하고, 검색을 통하여 어렵지 않게 TSP에 많은 논문들도 볼 수 있었습니다(물론 이해하진 못했습니다 ㅎㅎ). 좋은 문제 올려주셔서 감사하구요. 다른분들의 다양한 풀이 방법도 보고 싶습니다. - 이 우람, 2016/02/01 00:33 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

유전알고리즘(Genetic Algorithms)을 이용해서 작성했습니다. 항상 결과가 같은것은 아니며, 돌릴때 마다 진화 해가면서 세대가 바뀌면 결과가 바뀝니다.

console 말고 winform으로 그래픽하게 만든 버전은 동영상으로 실행 화면을 볼수 있습니다.

https://www.youtube.com/watch?v=cpCWRJzgSb8

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            GA GA = new GA();
            for (int i = 0; i < 500; i++)
            {
                GA.Next();
                string next = GA.PathList[0].ToString();
                Console.WriteLine(GA.Generation + "세대:" + next + "(거리:" + GA.PathList[0].Sum + ")");
            }
            Console.ReadKey();
        }
    }

    public class GA
    {
        public int Generation = 0;
        public List<Lover> Lovers { get; set; } = new List<Lover>();
        public List<Path> PathList { get; set; } = new List<Path>();
        private Random Rnd;
        public GA()
        {
            int seed = (int)DateTime.Now.Ticks;
            this.Rnd = new Random(seed);

            #region Lovers.Add
            Lovers.Add(new Lover(0, 50, 50));
            Lovers.Add(new Lover(1, 26, 23));
            Lovers.Add(new Lover(2, 50, 95));
            Lovers.Add(new Lover(3, 85, 66));
            Lovers.Add(new Lover(4, 67, 40));
            Lovers.Add(new Lover(5, 46, 12));
            Lovers.Add(new Lover(6, 6, 2));
            Lovers.Add(new Lover(7, 51, 12));
            Lovers.Add(new Lover(8, 44, 30));
            Lovers.Add(new Lover(9, 4, 56));
            Lovers.Add(new Lover(10, 61, 14));
            Lovers.Add(new Lover(11, 73, 6));
            Lovers.Add(new Lover(12, 74, 72));
            Lovers.Add(new Lover(13, 51, 52));
            Lovers.Add(new Lover(14, 7, 40));
            Lovers.Add(new Lover(15, 31, 66));
            Lovers.Add(new Lover(16, 8, 16));
            Lovers.Add(new Lover(17, 62, 70));
            Lovers.Add(new Lover(18, 87, 19));
            Lovers.Add(new Lover(19, 32, 77));
            Lovers.Add(new Lover(20, 56, 67));
            Lovers.Add(new Lover(21, 86, 50));
            Lovers.Add(new Lover(22, 0, 74));
            Lovers.Add(new Lover(23, 65, 42));
            Lovers.Add(new Lover(24, 19, 97));
            Lovers.Add(new Lover(25, 49, 14));
            Lovers.Add(new Lover(26, 4, 11));
            Lovers.Add(new Lover(27, 0, 19));
            Lovers.Add(new Lover(28, 17, 37));
            Lovers.Add(new Lover(29, 46, 33));
            Lovers.Add(new Lover(30, 12, 90));

            #endregion

            for (int i = 0; i < 1000; i++)
            {
                this.AddRandomPath();
            }

            this.PathList = this.PathList.OrderBy(x => x.Sum).ToList<Path>();

        }
        private void AddRandomPath()
        {
            var list = new List<Lover>();

            for (int i = 1; i < this.Lovers.Count; i++)
            {
                list.Add(this.Lovers[i]);
            }

            for (int i = 1; i < list.Count; i++)
            {
                int rndV = Rnd.Next(0, list.Count - i);

                var temp = list[list.Count - i];
                list[list.Count - i] = list[rndV];
                list[rndV] = temp;
            }

            list.Insert(0, this.Lovers[0]);
            list.Add(this.Lovers[0]);

            this.PathList.Add(new Path() { List = list }.SetSum());
        }
        public Path CombinePath(Path a, Path b, int MutationLevel)
        {

            Path c = new Path();

            List<Lover> al = a.List.ToList<Lover>();
            List<Lover> bl = b.List.ToList<Lover>();

            for (int i = 1; i < al.Count / 2; i++)
            {
                c.List.Add(al[i]);
                Swap(bl, al[i].key, i);
            }

            for (int i = 0; i < bl.Count / 2 - 1; i++)
            {
                c.List.Add(bl[bl.Count / 2 + i]);
            }

            if (MutationLevel > 0)
            {
                for (int i = 0; i <= MutationLevel; i++)
                {
                    Swap(c.List, c.List[(Rnd.Next() % 30)].key, (Rnd.Next() % 30));
                }
            }

            c.List.Insert(0, this.Lovers[0]);
            c.List.Add(this.Lovers[0]);

            return c.SetSum();

        }
        public void Swap(List<Lover> list, int key, int idx)
        {
            int keyIdx = 0;
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i].key == key)
                {
                    keyIdx = i;
                    break;
                }
            }

            Lover t = list[keyIdx];
            list[keyIdx] = list[idx];
            list[idx] = t;
        }
        public void Next()
        {
            Generation++;

            List<Path> nextPathList = new List<Path>();

            List<Path> bestList = new List<Path>();

            for (int i = 0; i < 2; i++)
            {
                bestList.Add(PathList[i]);
            }

            for (int i = 0; i < bestList.Count; i++)
            {
                for (int j = 0; j < bestList.Count; j++)
                {
                    if (i == j)
                    {
                        continue;
                    }
                    {
                        Path c = CombinePath(bestList[i], bestList[j], 0);
                        nextPathList.Add(c);
                    }
                    for (int k = 0; k < 1000; k++)
                    {
                        Path c = CombinePath(bestList[i], bestList[j], (Rnd.Next() % 10));
                        nextPathList.Add(c);
                    }
                }
            }

            nextPathList.Add(bestList[0]);
            nextPathList.Add(bestList[1]);

            this.PathList = nextPathList;

            this.PathList = this.PathList.OrderBy(x => x.Sum).ToList<Path>();
        }
    }

    public class Lover
    {
        public int key { get; set; }
        public int x { get; set; }
        public int y { get; set; }
        public Lover(int key, int x, int y)
        {
            this.key = key;
            this.x = x;
            this.y = y;
        }
        public override string ToString()
        {
            return key.ToString("00");
        }
    }

    public class Path
    {
        public List<Lover> List { get; set; } = new List<Lover>();
        public int Sum = 0;

        public Path SetSum()
        {
            int result = 0;
            for (int i = 0; i < List.Count - 1; i++)
            {
                int dist = (int)Math.Sqrt(
                    Math.Pow(List[i].x - List[i + 1].x, 2)
                    + Math.Pow(List[i].y - List[i + 1].y, 2)
                );
                result += dist;
            }
            this.Sum = result;
            return this;
        }

        public override string ToString()
        {
            return string.Join(">", this.List);
        }
    }
}
00>21>03>12>17>20>15>19>02>24>30>22>09>14>28>16>27>26>06>01>29>08>05>25>07>10>11>18>04>23>13>00 
여러번 돌렸는데 464 거리짜리 조합이 있네요.
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

일단 각 좌표를 순서 없이 2개를 선택해서 각 좌표 사이의 거리를 구하구요, (465가지 데이터 나옴) 가까이 있는 좌표로 옮겨가는 방식으로 움직이는 길이를 구하면 될 듯 하지 않을까요? 컴퓨터는 계산 잘 하니깐 1~31번째 좌표까지 전부 넣어보면서 시뮬레이션을 해보는 거죠 ㅎㅎ

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

2-opt를 이용한 근사 값

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <windows.h>
#define MAX_COLS 100000
#pragma warning(disable:4996)


struct Node {
    int x;
    int y;
    bool b;
}n[31];
struct Path {
    int value;
    Path* next;
    Path* prev;
}*p, *head;
int d[31][31];

void init();
void two_opt();
int getSum();
int getDistance(Node n1, Node n2);
void printPath(Path* p);
void insertPath(int value);
bool subcycle(Path* p);

void main() {
    system("mode con:cols=150 lines=50");
    head = NULL;
    p = NULL;
    init(); 

    for(int i = 0 ;i<10;i++)
        two_opt();
    printf("=============== 경 로 ===========\n");
    printPath(p);
    printf("=============== SUM =============\n");
    printf("\n\n%d", getSum());
}

void init() {
    FILE *f = fopen("data.txt", "r");
    char s[MAX_COLS];
    char s2[] = " ";
    char* token = NULL;
    int i = 0;

    while(fgets(s, MAX_COLS, f) != NULL) {
        int temp;
        token = strtok(s, s2);
        temp = atoi(token);
        n[i].x = temp;
        token = strtok(NULL, s2);
        temp = atoi(token);
        n[i].y = temp;

        n[i].b = true;
        i++;
    }

    for(int i = 0; i<31 ;i++) {
        for(int j = 0; j<31 ;j++) {
            d[i][j] = getDistance(n[i], n[j]);
        }
    }
    insertPath(0);
    int cur = 0;
    int index = 0;
    for(int i = 1; i<31 ;i++) {
        int min = 1000;
        for(int j = 0; j<31 ;j++) {
            if(n[j].b == false) continue;
            if(cur!=j && min > d[cur][j]) {
                min = d[cur][j];
                index = j;
            }
        }
        n[cur].b = false;
        cur = index;
        insertPath(cur);
    }
    head->next = p;
    p->prev = head;
    _fcloseall();
}

int getDistance(Node n1, Node n2) {
    return (int)sqrt(pow((double)abs(n1.x-n2.x), 2) + pow((double)abs(n1.y-n2.y),2));
}

int getSum() {
    Path* temp = p;
    int sum = 0;
    for(int i = 0; i<31 ;i++) {
        sum = sum + d[temp->value][temp->next->value];
        temp = temp->next;
    }
    return sum;
}

void two_opt() {
    Path* t1 = p; 
    Path* t2 = t1->next;
    Path* replace1 = (Path*) malloc (sizeof(Path));
    Path* replace2 = (Path*) malloc (sizeof(Path));
    for(int i = 0; i<30 ;i++) {
        for(int j = i+1; j<30 ;j++) {
            if(d[t1->value][t1->next->value] + d[t2->value][t2->next->value] > d[t2->value][t1->value] + d[t1->next->value][t2->next->value]) 
            {
                if(!(t1->value == t2->value && t1->next->value == t2->next->value)) {
                    Path* cur = t2;
                    replace1 = t1->next;

                    t1->next->prev = t1->next->next;
                    t2->next->prev = t1->next;

                    t1->next->next = t2->next;
                    while(replace1->value != cur->value) {
                        replace2 = cur->next;
                        cur->next = cur->prev;
                        cur->prev = replace2;
                        cur=cur->next;
                    }
                    t2->prev = t1;
                    t1->next = t2;
                }
            }

            t2 = t2->next;
        }
        t1 = t1->next;
    }
}

void insertPath(int value) {
    Path* temp = (Path*) malloc (sizeof(Path));
    temp->value = value;
    temp->next = NULL;
    temp->prev = NULL;

    if(head != NULL) {
        head->next = temp;
        temp->prev = head;
    }
    if(head == NULL) {
        p = temp;
    }
    head = temp;
}

void printPath(Path* p) {
    int i = 1;
    while(p != NULL && i < 33) {
        printf("%2d %2d\n", n[p->value].x, n[p->value].y);
        p = p->next;
        i++;
    }
    printf("\n");
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.DefaultTreeModel;
import javax.swing.tree.TreeNode;
import java.util.ArrayList;


public class Quine {
     public static void main(String args[]) throws Exception  
    {
         oilWind ow = new oilWind();
         ow.init();
         ow.getEveryCase1();
         ow.getEveryCase2();
         ow.getEveryCase3();
         ow.getEveryCase4();

    }   
}

public class oilWind { // | |
    private static final TreeNode TreeNode = null;
    List<Point> pList = new ArrayList<Point>(); // | 1,2 |2,2
                                                // |----------
    List<Point> pList1 = new ArrayList<Point>();// 1,1 // | 1,1 |2,1
    List<Point> pList2 = new ArrayList<Point>();// 1,2 //-------------
    List<Point> pList3 = new ArrayList<Point>();// 2,1
    List<Point> pList4 = new ArrayList<Point>();// 2,2

    // result
    List<Point> pListRet = new ArrayList<Point>();
    int nSum = 0;

    // gap for distance
    List<Integer> pListGap1 = new ArrayList<Integer>();// 1,1
    List<Integer> pListGap2 = new ArrayList<Integer>();// 1,2
    List<Integer> pListGap3 = new ArrayList<Integer>();// 2,1
    List<Integer> pListGap4 = new ArrayList<Integer>();// 2,2

    Point mPoint = new Point(50, 50);

    public int getMinIndex(List<Integer> plist) {
        int val = 99;
        int ret = 0;
        for (int tmp : plist) {
            val = Math.min(val, tmp);

        }
        ret = plist.indexOf(val);
        return ret;
    }

    public Point getShortIndex(Point pt, List<Point> plist) {
        double val = 999999;
        Point prePoint = new Point(0,0);
        Point retPoint = new Point(0,0);
        for (Point tmp : plist) {
            if(pt.distance(new Point(tmp.x, tmp.y))<val)
            {
                retPoint = new Point(tmp.x, tmp.y);
                prePoint = new Point(tmp.x, tmp.y);
            }else
            {
                retPoint = new Point(prePoint.x, prePoint.y);
            }
            val = Math.min(pt.distance(new Point(tmp.x, tmp.y)), val);

        }       
        return retPoint;
    }
    double distanceRet = 999999999;
    TreeNode[] shotList= null;
    public DefaultMutableTreeNode insertChild(DefaultMutableTreeNode parent,List<Point> plist,Point nEndPointIdx)
    {
        DefaultMutableTreeNode child = null;
        DefaultMutableTreeNode lastChild = null;
        if(plist.size()==0)
        {
            child = new DefaultMutableTreeNode(nEndPointIdx);

            parent.add(child);
            TreeNode[] tnlist = child.getPath();
            Point PrePoint = null;
            double distance = 0;
            for(TreeNode tn:tnlist)
            {
                DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
                Point pt =(Point)dmt.getUserObject();
                if(PrePoint==null)
                {
                    PrePoint = new Point(pt.x,pt.y);
                }else
                {
                    distance += pt.distance(PrePoint);
                    PrePoint = new Point(pt.x,pt.y);
                }
            }
            if(distanceRet>distance)
            {
                shotList = null;
                shotList = tnlist;
                distanceRet =distance ;
            }else
            {

            }
            return child;
        }
        List<Point> clonelist = new ArrayList<Point>();
        clonelist.addAll(plist);


        for( Point pt:clonelist)
        {
            child = new DefaultMutableTreeNode(pt);
            parent.add(child);
        }
        for(int i=0;i<parent.getChildCount();i++)
        {
            List<Point> clonelist2 = new ArrayList<Point>();
            clonelist2.addAll(clonelist);
            DefaultMutableTreeNode tn = (DefaultMutableTreeNode)parent.getChildAt(i);
            Point pt = (Point)tn.getUserObject();
            clonelist2.remove(pt);
            child = new DefaultMutableTreeNode(pt);
            lastChild = insertChild(tn,clonelist2,nEndPointIdx);            
        }
        return lastChild;
    }
    double distanceRet1 = 999999999;
    TreeNode[] shotList1= null;
    double distanceRet2 = 999999999;
    TreeNode[] shotList2= null;
    double distanceRet3 = 999999999;
    TreeNode[] shotList3= null;
    double distanceRet4 = 999999999;
    TreeNode[] shotList4 = null;
    public void getEveryCase1() {               
        List<Point> list = new ArrayList<Point>();
        list.addAll(pList1);
        Point nStartPointIdx = new Point(50,50);//getShortIndex(new Point(25,50), list);
        Point nEndPointIdx = getShortIndex(new Point(50,25), pList3);

        Point nStartPointIdx2 = getShortIndex(nStartPointIdx, list);
        Point nEndPointIdx2 = getShortIndex(nEndPointIdx, list);
        DefaultMutableTreeNode top = new DefaultMutableTreeNode(nStartPointIdx2);
        list.remove(nStartPointIdx);
        list.remove(nEndPointIdx2);
        DefaultMutableTreeNode second = null;

        List<Point> originlist = new ArrayList<Point>();
        originlist.addAll(list);
        originlist.remove(nStartPointIdx);
        if(originlist.size()>10)
        {
            System.out.print("Not Ready. \r\n");
        }
        DefaultMutableTreeNode lastChild = insertChild(top,originlist,nEndPointIdx2);

        distanceRet1 = distanceRet ;
        distanceRet1 += nStartPointIdx.distance(nStartPointIdx2);
        distanceRet1 += nEndPointIdx.distance(nEndPointIdx2);
        shotList1 = shotList ;
        shotList = null;
        distanceRet = 999999999;
        System.out.print(nStartPointIdx.x + " " + nStartPointIdx.y + "\r\n");

        for (TreeNode tn : shotList1) {
            DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
            Point pt =(Point)dmt.getUserObject();
            System.out.print(pt.x + " " + pt.y + "\r\n");
        }
        System.out.print(nEndPointIdx.x + " " + nEndPointIdx.y + "\r\n");

        //System.out.print("Total Distance1 = " + distanceRet1 + "\r\n");
    }
    public void getEveryCase2() {               
        List<Point> list = new ArrayList<Point>();
        list.addAll(pList3);
        Point nStartPointIdx = getShortIndex(new Point(50,25), pList3);
        Point nEndPointIdx = getShortIndex(new Point(75,50), pList4);
        DefaultMutableTreeNode top = new DefaultMutableTreeNode(nStartPointIdx);
        list.remove(nStartPointIdx);
        DefaultMutableTreeNode second = null;

        List<Point> originlist = new ArrayList<Point>();
        originlist.addAll(list);
        if(originlist.size()>10)
        {
            System.out.print("Not Ready. \r\n");
        }
        DefaultMutableTreeNode lastChild = insertChild(top,originlist,nEndPointIdx);
        distanceRet2 = distanceRet ;
        shotList2 = shotList ;
        shotList = null;
        distanceRet = 999999999;
        //System.out.print(nStartPointIdx.x + " " + nStartPointIdx.y + "\r\n");
        for (TreeNode tn : shotList2) {
            DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
            Point pt =(Point)dmt.getUserObject();

            System.out.print(pt.x + " " + pt.y + "\r\n");

        }
        //System.out.print(nEndPointIdx.x + " " + nEndPointIdx.y + "\r\n");
        //System.out.print("Total Distance2 = " + distanceRet2 + "\r\n");
    }
    public void getEveryCase3() {               
        List<Point> list = new ArrayList<Point>();
        list.addAll(pList4);
        Point nStartPointIdx = getShortIndex(new Point(75,50), pList4);
        Point nEndPointIdx = getShortIndex(new Point(50,75), pList2);
        DefaultMutableTreeNode top = new DefaultMutableTreeNode(nStartPointIdx);
        list.remove(nStartPointIdx);
        DefaultMutableTreeNode second = null;

        List<Point> originlist = new ArrayList<Point>();
        originlist.addAll(list);
        DefaultMutableTreeNode lastChild = insertChild(top,originlist,nEndPointIdx);
        distanceRet3 = distanceRet ;
        shotList3 = shotList ;
        shotList = null;
        distanceRet = 999999999;
        //System.out.print(nStartPointIdx.x + " " + nStartPointIdx.y + "\r\n");
                for (TreeNode tn : shotList3) {
                    DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
                    Point pt =(Point)dmt.getUserObject();

                    System.out.print(pt.x + " " + pt.y + "\r\n");

                }
                //System.out.print(nEndPointIdx.x + " " + nEndPointIdx.y + "\r\n");
    //          System.out.print("Total Distance3 = " + distanceRet3 + "\r\n");
    }

    public void getEveryCase4() {               
        List<Point> list = new ArrayList<Point>();
        list.addAll(pList2);
        Point nStartPointIdx = getShortIndex(new Point(50,75), pList2);
        Point nEndPointIdx = new Point(50,50);//getShortIndex(new Point(75,50), pList4);
        DefaultMutableTreeNode top = new DefaultMutableTreeNode(nStartPointIdx);
        list.remove(nStartPointIdx);
        DefaultMutableTreeNode second = null;

        List<Point> originlist = new ArrayList<Point>();
        originlist.addAll(list);
        DefaultMutableTreeNode lastChild = insertChild(top,originlist,nEndPointIdx);
        distanceRet4 = distanceRet ;
        shotList4 = shotList ;
        shotList = null;
        distanceRet = 999999999;
        for (TreeNode tn : shotList4) {
            DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
            Point pt =(Point)dmt.getUserObject();
            System.out.print(pt.x + " " + pt.y + "\r\n");
        }
        //System.out.print(nEndPointIdx.x + " " + nEndPointIdx.y + "\r\n");
        distanceRet4 +=distanceRet1;
        distanceRet4 +=distanceRet2;
        distanceRet4 +=distanceRet3;

        System.out.print("Total Distance = " + distanceRet4 + "\r\n");
        //printResult();
    }
    public void printResult()
    {
        for (TreeNode tn : shotList1) {
            DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
            Point pt =(Point)dmt.getUserObject();
            System.out.print(pt.x + " " + pt.y + "\r\n");
        }
        System.out.print("Total Distance1 = " + distanceRet1 + "\r\n");
        for (TreeNode tn : shotList2) {
            DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
            Point pt =(Point)dmt.getUserObject();
            System.out.print(pt.x + " " + pt.y + "\r\n");
        }
        System.out.print("Total Distance2 = " + distanceRet2 + "\r\n");
        for (TreeNode tn : shotList3) {
            DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
            Point pt =(Point)dmt.getUserObject();
            System.out.print(pt.x + " " + pt.y + "\r\n");
        }
        System.out.print("Total Distance3 = " + distanceRet3 + "\r\n");
        for (TreeNode tn : shotList4) {
            DefaultMutableTreeNode dmt = (DefaultMutableTreeNode)tn;
            Point pt =(Point)dmt.getUserObject();
            System.out.print(pt.x + " " + pt.y + "\r\n");
        }
        System.out.print("Total Distance4 = " + distanceRet4 + "\r\n");

    }
    public int calc() {
        int ret = 0;
        Point startPoint = new Point(mPoint.x, mPoint.y);
        pListRet.add(new Point(mPoint.x, mPoint.y));

//      List<List<Integer>> tmpList =  getEveryCase(5);
//      if(tmpList.size()>0)
//      {
//          return tmpList.size();
//      }
        while (pList1.size() > 0) {
            int idx = getMinIndex(pListGap1);
            Point some = new Point(pList1.get(idx).x, pList1.get(idx).y);
            pList1.remove(idx);
            pListGap1.remove(idx);
            pListRet.add(new Point(some.x, some.y));
            nSum += startPoint.distance(some.x, some.y);
            startPoint = new Point(some.x, some.y);
        }
        while (pList3.size() > 0) {
            int idx = getMinIndex(pListGap3);
            Point some = new Point(pList3.get(idx).x, pList3.get(idx).y);
            pList3.remove(idx);
            pListGap3.remove(idx);
            pListRet.add(new Point(some.x, some.y));
            nSum += startPoint.distance(some.x, some.y);
            startPoint = new Point(some.x, some.y);
        }
        while (pList4.size() > 0) {
            int idx = getMinIndex(pListGap4);
            Point some = new Point(pList4.get(idx).x, pList4.get(idx).y);
            pList4.remove(idx);
            pListGap4.remove(idx);
            pListRet.add(new Point(some.x, some.y));
            nSum += startPoint.distance(some.x, some.y);
            startPoint = new Point(some.x, some.y);
        }
        while (pList2.size() > 0) {
            int idx = getMinIndex(pListGap2);
            Point some = new Point(pList2.get(idx).x, pList2.get(idx).y);
            pList2.remove(idx);
            pListGap2.remove(idx);
            pListRet.add(new Point(some.x, some.y));
            nSum += startPoint.distance(some.x, some.y);
            startPoint = new Point(some.x, some.y);
        }
        nSum += startPoint.distance(mPoint);
        pListRet.add(new Point(mPoint.x, mPoint.y));
        PrintMiddle(pListRet);
        System.out.print("Total Distance = " + nSum + "\r\n");

        return ret;
    }

    public void PrintMiddle(List<Point> plist) {
        for (Point tmp : plist) {
            System.out.print(tmp.x + " " + tmp.y + "\r\n");
        }

    }

    public void init() {
        int ret = 0;
        // pList.add(new Point(50,50));
        pList.add(new Point(26, 23));
        pList.add(new Point(50, 95));
        pList.add(new Point(85, 66));
        pList.add(new Point(67, 40));
        pList.add(new Point(46, 12));
        pList.add(new Point(6, 2));
        pList.add(new Point(51, 12));
        pList.add(new Point(44, 30));
        pList.add(new Point(4, 56));
        pList.add(new Point(61, 14));
        pList.add(new Point(73, 6));
        pList.add(new Point(74, 72));
        pList.add(new Point(51, 52));
        pList.add(new Point(7, 40));
        pList.add(new Point(31, 66));
        pList.add(new Point(8, 16));
        pList.add(new Point(62, 70));
        pList.add(new Point(87, 19));
        pList.add(new Point(32, 77));
        pList.add(new Point(56, 67));
        pList.add(new Point(86, 50));
        pList.add(new Point(0, 74));
        pList.add(new Point(65, 42));
        pList.add(new Point(19, 97));
        pList.add(new Point(49, 14));
        pList.add(new Point(4, 11));
        pList.add(new Point(0, 19));
        pList.add(new Point(17, 37));
        pList.add(new Point(46, 33));
        pList.add(new Point(12, 90));
        for (Point pt : pList) {
            if (pt.x < 50) {
                if (pt.y < 50) {
                    pList1.add(pt);
                } else {
                    pList2.add(pt);
                }
            } else {
                if (pt.y < 50) {
                    pList3.add(pt);
                } else {
                    pList4.add(pt);
                }
            }
        }
        for (Point pt : pList1) {
            int i = pList1.indexOf(pt);
            int val = 50 - pt.y;
            pListGap1.add(i, val);
        }
        for (Point pt : pList2) {
            int i = pList2.indexOf(pt);
            int val = 100 - pt.y;
            pListGap2.add(i, val);
        }
        for (Point pt : pList3) {
            int i = pList3.indexOf(pt);
            int val = pt.y;
            pListGap3.add(i, val);
        }
        for (Point pt : pList4) {
            int i = pList4.indexOf(pt);
            int val = pt.y - 50;
            pListGap4.add(i, val);
        }
    }
}

일단 중심을 기준으로 1사분면~4사분면으로 나누고 각 분면 별로 모든 점을 트리로 구현한뒤 모든 경우에 대해 최소값을 구하고 이것을 1~4사분면으로 하는 코드인데.. 1사분면에서 점이 하도 많아서 메모리가 안받쳐주네요..일단 트리가 10!넘어가면 아웃오브메모리.. 1사분면은 3개 점을 뺀상태에서 돌렸는데.. 어쨋든 값이 516이네요.. 음.. 윗 알고리즘보다 효율성이 매우 떨어지는 코드지만 일단 참고 삼아 올림요.. - Leehyosin, 2016/10/31 11:17 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

//정말 간단하게 만들어 봤습니다. 거리 계산할 때 소숫점을 안해서 그런가 다른 해답과는 다른 결과가 나오네요 //총 비행 거리는 577이 나왔습니다.

#include <iostream>
#include <math.h>
using namespace std;

int main(void) {
    int xy[99][99];
    for (int i = 0;i < 99;i++) {
        for (int j = 0;j < 99;j++) {
            xy[i][j] = 0;
        }
    }
    //변수 초기화
    xy[50][50] = 9;
    xy[26][23] = 1;
    xy[50][95] = 1;
    xy[85][66] = 1;
    xy[67][40] = 1;
    xy[46][12] = 1;
    xy[6][2] = 1;
    xy[51][12] = 1;
    xy[44][30] = 1;
    xy[4][56] = 1;
    xy[61][14] = 1;
    xy[73][6] = 1;
    xy[74][72] = 1;
    xy[51][52] = 1;
    xy[7][40] = 1;
    xy[31][66] = 1;
    xy[8][16] = 1;
    xy[62][70] = 1;
    xy[87][19] = 1;
    xy[32][77] = 1;
    xy[56][67] = 1;
    xy[86][50] = 1;
    xy[0][74] = 1;
    xy[65][42] = 1;
    xy[19][97] = 1;
    xy[49][14] = 1;
    xy[4][11] = 1;
    xy[0][19] = 1;
    xy[17][37] = 1;
    xy[46][33] = 1;
    xy[12][90] = 1;
    //좌표 입력

    int now[4] = { 50,50,0,0 };
    //머무르고있는 x좌표,y좌표,비행횟수,비행누적거리
    int cost[3] = { 0,0,9999 };
    //이동할 x좌표,y좌표,비행거리

    cout << now[2] << " : " << now[0] << ", " << now[1] << endl;
    //자기집 출력
    while (1) {
        if (now[2] >= 30)break;
        //30회 이동했으면 집가자
        for (int i = 0;i < 99;i++) {
            for (int j = 0;j < 99;j++) {
                if (xy[i][j] == 1) {
                    //여친집?
                    if(i == now[0]){
                        //x좌표가 같다면 세로의 길이가 직선 거리
                        if (abs(now[1] - j) < cost[2]) {
                            cost[0] = i;
                            cost[1] = j;
                            cost[2] = abs(now[1] - j);
                        }
                    }
                    else if(j==now[1]){
                        //y좌표가 같다면 가로의 길이가 직선 거리
                        if (abs(now[0] - i) < cost[2]) {
                            cost[0] = i;
                            cost[1] = j;
                            cost[2] = abs(now[0] - j);
                        }
                    }
                    else {
                        //둘다 다르다면 빗변이 직선거리
                        int a = abs(now[0] - i);
                        int b = abs(now[1] - j);
                        int c = abs(sqrt((a*a) + (b*b)));
                        if (c < cost[2]) {
                            cost[0] = i;
                            cost[1] = j;
                            cost[2] = c;
                        }
                    }
                }
            }
        }
        now[0] = cost[0];
        now[1] = cost[1];
        //좌표 이동
        now[2]++;
        //비행 횟수 증가
        now[3] += cost[2];
        //비행거리 누적

        cost[0] = 0;
        cost[1] = 0;
        cost[2] = 9999;
        //초기화

        cout << now[2] << " : " << now[0] << ", " << now[1] << endl;
        //비행횟수 : x좌표, y좌표

        xy[now[0]][now[1]] = 9;
        //간곳 체크
    }

    //여기서 부터는 마지막 여친집 -> 자기집
    now[2]++;
    if (now[0] == 50) {
        if (abs(now[1] - 50) < cost[2]) {
            cost[0] = 50;
            cost[1] = 50;
            cost[2] = abs(now[1] - 50);
        }
    }
    else if (now[1] == 50) {
        if (abs(now[0] - 50) < cost[2]) {
            cost[0] = 50;
            cost[1] = 50;
            cost[2] = abs(now[0] - 50);
        }
    }
    else {
        int a = abs(now[0] - 50);
        int b = abs(now[1] - 50);
        int c = abs(sqrt((a*a) + (b*b)));
        if (c < cost[2]) {
            cost[0] = 50;
            cost[1] = 50;
            cost[2] = c;
        }
    }

    now[3] += cost[2];
    now[1] = 50;
    now[0] = 50;
    cout << now[2] << " : " << now[0] << ", " << now[1] << endl;
    cout << "누적 비행 거리 : " << now[3] << endl;

    return 0;
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
clear all; close all; clc;

posi=load('shortest_route.txt'); 
nop=length(posi);
dis=distant(posi,nop);
bignum=100000000;

mindis=10000*nop;
for coef=0.01:0.01:0.2
    for ind=1.4:0.01:1.5
        weighting=ones(nop,1)*(sum(dis.^ind)/nop)*coef;
        way=[1 zeros(1,nop-2) nop];
        diswei=dis-weighting; diswei(:,nop)=bignum*ones(nop,1);
        for j=2:nop-1
            diswei(:,way(1,j-1))=bignum*ones(nop,1);
            [temp1,temp2] = min(diswei(way(1,j-1),:)); 
            way(1,j)=temp2;
        end
        way=firstorderopti(way,dis,nop);
        sumdis=w2d(way,dis,nop)
        if mindis > sumdis
        mindis=sumdis; minway=way; effcoef=coef; effind=ind;
        end
    end
end
way=minway; 
mindis;
figure; drawing(posi,way,nop);
function output=firstorderopti(way,dis,nop)
mindis=w2d(way,dis,nop);
for k=1:5
    mindisold=mindis;
    for i=1:nop-1
        for j=i+2:nop-1
            subway=way;
            subway(i+1:j)=fliplr(way(i+1:j));
            if w2d(subway,dis,nop)<w2d(way,dis,nop)
                way=subway;
            end
        end
    end
end
output = way;

주어진 하나의 경로에 대해서 1 step짜리 경로를 서로 치환했을 때 길이가 줄어드는지 확인하는 방법으로 만들어보았습니다. 이런 저런 시도가 코드에 남아있긴 한데 큰 의미는 없는 것 같습니다. 1 14 21 18 13 4 22 24 5 19 12 11 8 26 6 30 9 2 17 7 27 28 29 15 10 23 31 25 3 20 16 32 제가 찾은 경로는 위와 같고, 길이는 457입니다. 점의 갯수가 더 많으면 좋겠다는 아쉬움이 있네요.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

TSP x 1

언어별 풀이 현황
전 체 x 7
cs x 1
cpp x 1
기 타 x 3
java x 1
matlab x 1