K-centers Problem

K-center problem

K Centers Problem | Set 1 (Greedy Approximate Algorithm) - GeeksforGeeks

원래 np 지만 조건 하에 greedy에 근사 가능

1. 임의로 vertex 선정
2. 선정된 vertex 와 거리 계산
3. 계산된 거리의 최대값이 (Maximum distance) 최소가 되는 거리를 지정한 k값 내에서 도출

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int maxindex(int* dist, int n)
{
    int mi = 0;
    for (int i = 0; i < n; i++) {
        if (dist[i] > dist[mi])
            mi = i;
    }
    return mi;
}
 
void selectKcities(int n, int weights[4][4], int k)
{
    int* dist = new int[n];
    vector<int> centers;
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
    }
 
    // index of city having the
    // maximum distance to it's
    // closest center
    int max = 0;
    for (int i = 0; i < k; i++) {
        centers.push_back(max);
        for (int j = 0; j < n; j++) {
 
            // updating the distance
            // of the cities to their
            // closest centers
            dist[j] = min(dist[j], weights[max][j]);
        }
 
        // updating the index of the
        // city with the maximum
        // distance to it's closest center
        max = maxindex(dist, n);
    }
 
    // Printing the maximum distance
    // of a city to a center
    // that is our answer
    cout << endl << dist[max] << endl;
 
    // Printing the cities that
    // were chosen to be made
    // centers
    for (int i = 0; i < centers.size(); i++) {
        cout << centers[i] << " ";
    }
    cout << endl;
}
 
// Driver Code
int main()
{
    int n = 4;
    int weights[4][4] = { { 0, 4, 8, 5 },
                          { 4, 0, 10, 7 },
                          { 8, 10, 0, 9 },
                          { 5, 7, 9, 0 } };
    int k = 2;
 
    // Function Call
    selectKcities(n, weights, k);
}
// Contributed by Balu Nagar