[휴리스틱] GSHS 우주 탐사대 (3D TSP)

https://koistudy.net/prob_page?NO=4319

---

아이디어

이번에는 초기해를 찾을 때 Farthest Insertion을 사용하였다. 이는 부분경로가 정해졌을 때 그 부분경로와 가장 멀리 떨어진, 즉 가장 가까운 점까지의 거리가 가장 먼 점을 경로에 추가하는것을 반복한다.

또한 2-opt를 수행하는 시간이 특정 시간을 넘어가면 크게 의미가 없음을 알게되었다.

시간(ms)	점수(점)
2500	1083
1500	1083
1000	1081
600	1079

---

소스코드

#include <iostream>
#include <vector>
#include <array>
#include <cmath>
#include <algorithm>
#include <chrono>
#include <random>
#define ll long long
using namespace std;
using namespace chrono;

vector <array <ll,3> > Dots;

ll Dis2(array <ll,3> A,array <ll,3> B)
{
    ll dx=A[0]-B[0],dy=A[1]-B[1],dz=A[2]-B[2];
    return dx*dx+dy*dy+dz*dz;
}
double Dis(array <ll,3> A,array <ll,3> B)
{
    double dx=A[0]-B[0],dy=A[1]-B[1],dz=A[2]-B[2];
    return sqrt(dx*dx+dy*dy+dz*dz);
}

double Route(vector <ll> &Order)
{
    double res=0;
    ll N=Order.size();

    for (ll i=0;i<N;i++)
        res+=Dis(Dots[Order[i]],Dots[Order[(i+1)%N]]);
    return res;
}

void OPT2(vector <ll> &Order)
{
    ll N=Order.size(),i,j;

    for (i=0;i<N;i++)
    {
        for (j=i+1;j<N;j++)
        {
            if (Dis(Dots[Order[i]],Dots[Order[(i+1)%N]])+Dis(Dots[Order[j]],Dots[Order[(j+1)%N]])>Dis(Dots[Order[i]],Dots[Order[j]])+Dis(Dots[Order[(i+1)%N]],Dots[Order[(j+1)%N]]))
                reverse(Order.begin()+(i+1),Order.begin()+(j+1));
        }
    }
}


steady_clock::time_point Start;
mt19937 rng(steady_clock::now().time_since_epoch().count());

void InitialSolution(vector <ll> &Order)
{
    // Farthest Insertion

    ll N=Order.size(),i,j,a,b,dis=0;
    for (i=1;i<=N;i++)
    {
        for (j=i+1;j<=N;j++)
        {
            if (dis<Dis2(Dots[i],Dots[j]))
            {
                dis=Dis2(Dots[i],Dots[j]);
                a=i,b=j;
            }
        }
    }

    Order.clear();
    Order.push_back(a),Order.push_back(b);
    vector <double> Nearest(N+1);
    for (i=1;i<=N;i++)
        Nearest[i]=min(Dis(Dots[i],Dots[a]),Dis(Dots[i],Dots[b]));

    while (Order.size()<N)
    {
        ll idx,mx=0;
        for (i=1;i<=N;i++)
        {
            if (Nearest[i]>mx)
            {
                mx=Nearest[i];
                idx=i;
            }
        }

        double mn=1e18;
        ll idx2=0;
        for (i=0;i<Order.size();i++)
        {
            if (-Dis(Dots[Order[i]],Dots[Order[(i+1)%Order.size()]])+Dis(Dots[Order[i]],Dots[idx])+Dis(Dots[Order[(i+1)%Order.size()]],Dots[idx])<mn)
            {
                mn=-Dis(Dots[Order[i]],Dots[Order[(i+1)%Order.size()]])+Dis(Dots[Order[i]],Dots[idx])+Dis(Dots[Order[(i+1)%Order.size()]],Dots[idx]);
                idx2=i;
            }
        }
        Order.insert(Order.begin()+idx2+1,idx);

        for (i=1;i<=N;i++)
            Nearest[i]=min(Nearest[i],Dis(Dots[i],Dots[idx]));
    }
}

void LocalSearch(vector <ll> &Order)
{
    while (true)
    {
        OPT2(Order);

        auto End=steady_clock::now();

        ll duration=duration_cast<milliseconds>(End-Start).count();

        if (duration>1500) return;
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,x,y,z;
    vector <ll> Order;

    cin>>N;

    Start=steady_clock::now();

    Dots.push_back({0,0,0});
    for (i=1;i<=N;i++)
    {
        cin>>x>>y>>z;
        Dots.push_back({x,y,z});
        Order.push_back(i);
    }

    InitialSolution(Order);
    LocalSearch(Order);

    ll idx=0;
    for (i=0;i<N;i++)
        if (Order[i]==1)
            idx=i;

    for (i=0;i<N;i++)
        cout<<Order[(i+idx)%N]<<"\n";
}