取宝石问题

题目

取宝石问题

假设在一个大房间有n个宝石，每一处宝石用一个坐标(x, y)表示。

如果你从任意一处宝石的地方出发，依次经过每个放宝石的地方并取走宝石，最终要求回到出发地点，问最短需要走的距离是多少。

本题允许走直线。

思路

采用枚举法，在这个情境里，经过不同地点的顺序会改变最终的行走距离。

所以，我们要枚举的就是经过1~n一共n个位置的顺序。

枚举n个位置的顺序其实是一个排列问题， 那么可以直接用 C++ 中的 next_permutation 函数来快速获得下一个排列，获得下一个排列的时间复杂度为 O(n) 。

细节
起始点和终点时固定的，所以数组的第一个数和最后一个数不参加排列。

代码

#include 
#define N 15
using namespace std;
int n = 4; // 4个宝石
int id[N] = {0, 1, 2, 3, 4, 0};
double x[N] = {0, 2, 2, 3, 5, 0}; // 宝石的x坐标
double y[N] = {0, 1, 4, 5, 6, 0}; // 宝石的y坐标

// 求两个点(x_1, y_1)和(x_2, y_2)之间的直线距离
double dis(double x_1, double y_1, double x_2, double y_2) {
    double dx = x_1 - x_2;
    double dy = y_1 - y_2;
    return sqrt(dx * dx + dy * dy);
}
int main() {
    
    double ans = -1;    // 因为最开始ans中没有值，所以我们可以将其设置为一个不合法的值	
    // 用do...while循环是为了防止第一次调用时数组id中的值已经被重排
    // 所以会导致标号为1, 2, ..., n的排列没有被计算。

    do {
        // 求解按照id[1], id[2], ..., id[n], id[1]作为行走路线的总距离。

        double cur = dis(x[id[1]], y[id[1]], x[id[n]], y[id[n]]);
        for (int i = 1; i < n; ++i)
            cur += dis(x[id[i]], y[id[i]], x[id[i + 1]], y[id[i + 1]]);
        
        // 如果当前路线的总距离小于之前最优解，就更新。

        if (ans < 0 || cur < ans) ans = cur;
    // 用``next_permutation``枚举所有n个点的排列
    } while (next_permutation (id + 1, id + n + 1));    
    
    // 输出答案，这里因为是浮点数，所以我们设置精度为4。

    cout << setprecision(4) << ans << endl;
    return 0;
}

复杂度分析

取得下一个排列的最坏时间复杂度为O(n)， 共有n！个排列，对每个排列计算距离的时间复杂度为O(n)， 因此最坏的时间复杂度为O(n! * n * n)。

但是对于n个不同的元素，取得下一个排列平均时间复杂度可能为O(1), 则平均时间复杂度为O(n! * n )。