我正在尝试实施分而治之算法来解决旅行商问题。 我将问题分为几个小部分，但我不知道下一步该怎么做。

这是我的代码：

struct coordinate
{
    float x;
    float y;
};

vector<coordinate> coordinates; //Please assume it is filled with random coordinates

void DivideAndConquer(int divide)
{
    vector<vector<coordinate>> routes;
    vector<coordinate> empty;
    int check = 0;


    for (int i = 0; i < coordinates.size(); i++)
    {   
        if (i == divide * check)
        {
            check++;
            routes.push_back(empty);
        }
        routes[check - 1].push_back(coordinates[i]);
    }

    //What now?
}

我还实现了计算距离的方法：

float Distance(coordinate first,coordinate second)
{
    return sqrt(pow(second.x - first.x,2) + pow(second.y - first.y,2) * 1.0);
}

float RouteDistance(vector<coordinate> route,bool returnBack)
{
    float totalDistance = 0;
    for (int i = 1; i < route.size(); i++)
    {
        totalDistance += Distance(route[i-1],route[i]);
    }
    if (returnBack) totalDistance += Distance(route[0],route[route.size() - 1]);

    return totalDistance;
}

我也写了蛮力算法，我相信它可以用于分而治之。 它只是返回给定坐标矢量的最佳路径。

vector<coordinate> BruteForce(vector<coordinate> route)
{

    vector<int> turn;
    for (int i = 0; i < route.size(); i++) turn.push_back(i);

    int currentBestDistance = RouteDistance(route,true);
    vector<coordinate> currentBestRoute = route;

    do
    {
        vector<coordinate> newRoute;
        int newRouteDistance;

        for (int e : turn)
        {
            newRoute.push_back(route[e]);
        }
        newRouteDistance = RouteDistance(newRoute,false);

        if (newRouteDistance < currentBestDistance)
        {
            currentBestRoute = newRoute;
            currentBestDistance = newRouteDistance;
        }

    } while (next_permutation(turn.begin(),turn.end()));

    return currentBestRoute;
}

在DivideAndConquer中，当前将坐标矢量划分为子矢量的大小，该子矢量的大小称为“ divide”参数，我们称之为“

10 20
23 54
98123
55 72
16 82

我们称之为“ DivideAndConquer（2）”
结果：

10 20
23 54

98 123
55 72

16 82