[결정 문제][그래프] ARCTIC 북극 기지

1. 최적화 문제

 

이 문제는 각 기지를 모두 연결할 수 있는 거리 중에서 최대 거리를 최소화 하는 문제로

 

모든 경우의 수를 만들어서 최대거리가 최소인 경우를 찾으면 된다.

 

하지만 이 최적화 문제는 경우의 수가 너무 많다.

 

2. 결정 문제

 

결정 문제로 문제를 변형해보자

 

모든 기지를 통신반경 D인 무전기로 연결할 수 있는지?

 

이 문제를 이진탐색으로 여러번 수행하면 

 

최적해에 아주 가까운 근사값을 얻을 수 있을 것이다.

 

3. 코드

 

class Coord {
    public:
    double y, x;
    Coord(double y = 0, double x = 0){
        this->y = y;
        this->x = x;
    }
};
 
std::vector<Coord> center;
int visited[100] ={0,};
double dis[101][101];
 
double distance(Coord& a, Coord& b)
{
    double y = a.y - b.y;
    double x = a.x - b.x;
    return sqrt(y*y+ x*x); 
}
 
bool isOkay(double D, int centerNum)
{
    for(int i = 1; i < center.size(); i++)
    {
        if(centerNum == 0) visited[i] = 0;
        else if(visited[i] == 0) break;
        else if(i + 1 == center.size()) return true;
    }
    for(int j = 1; j < center.size(); j++)
    {
        if(visited[j] == 0 && centerNum != j && dis[centerNum][j] <= D)
        {
            visited[j]++;
            if(isOkay(D,j)) return true;
        }
    }
    return false;
}
 
double bisearch()
{
    for(int i = 0; i < center.size(); i++)
        for(int j = 0; j < center.size(); j++)
            dis[i][j] = distance(center[i], center[j]);
 
    double lo = 0.0 , hi = 1500.0;
 
    for(int i = 0; i < 100; i++)
    {
        double mid = (hi + lo )/2.0;
 
        if(isOkay(mid, 0)) hi = mid;
        else lo = mid;
    }
 
    return lo;
}

 

4. 더 빠르게 구현할 수 있는지?

bfs 그래프의 너비탐색을 이용하면 더 빠르게 수행 될 것이다.

 

크루스칼의 최소 스패닝 트리 알고리즘

 

플로이드의 모든 쌍 최단 거리 알고리즘등을 변형하면 더 빠르게 수행 될 것이다.

 

 

ARCTIC