我必須提出一個算法,它可以找到地球上最近的兩個點。我編寫了下面的代碼,它適用於我的測試,但執行時間太長。我試圖修改代碼,但它沒有幫助。也許有人會有一個想法,我該怎麼辦?如何減少算法執行的時間
struct Points
{
std::string key;
double latitude;
char latSign;
double longitude;
char longSign;
};
typedef std::pair<std::pair<std::string, std::string>, double> myType;
double toFraction(short deegres, short minutes)
{
return (double)deegres + (minutes/60.0);
}
double orthodroma(const Points &a, const Points &b)
{
double radian = M_PI/180;
return acos((cos((90 - a.latitude) * radian) *
cos((90 - b.latitude) * radian)) +
(sin((90 - a.latitude) * radian) *
sin((90 - b.latitude) * radian) *
cos((a.longitude - b.longitude) * radian))) *
(180/M_PI);
}
bool sortByLatitude(const Points &a, const Points &b)
{
return a.latitude > b.latitude;
}
myType bruteForce(const std::vector<Points> &vec, int begin, int n)
{
myType result;
double min = 1000000;
int _i, _j;
if(n > 300)
{
}
for(int i = begin; i < (n + begin) - 1; i++)
{
for(int j = i + 1; j < n + begin; j++)
{
double tmp;
tmp = orthodroma(vec[i], vec[j]);
if(tmp < min)
{
min = tmp;
_i = i;
_j = j;
}
}
}
result.first.first = vec[_i].key;
result.first.second = vec[_j].key;
result.second = min;
return result;
}
myType divideAndConquer(std::vector<Points> &vec, int begin, int n)
{
if(n <= 3)
{
return bruteForce(vec, begin, n);
}
std::sort(vec.begin(), vec.end(), sortByLatitude);
int middle = n/2;
Points point = vec[middle];
myType left = divideAndConquer(vec, begin, middle);
myType right = divideAndConquer(vec, middle, (n - middle));
bool which;
double minDist = std::min(left.second, right.second);
if(left.second < right.second)
which = false;
else
which = true;
std::vector<Points> arr;
for(int i = 0; i < n; i++)
{
if(abs(vec[i].latitude - point.latitude) < minDist)
{
arr.push_back(vec[i]);
}
}
int size = arr.size();
if(size < 2)
{
if(which)
return right;
else
return left;
}
else
{
myType one = bruteForce(arr, 0, size);
if(which)
{
if(one.second < right.second)
return one;
else
return right;
}
else
{
if(one.second < left.second)
return one;
else
return left;
}
}
}
PS。我必須使用分治法。
請描述你有問題,你用什麼樣的解決方案。 –
你是否在優化模式下編譯代碼? – jpo38
問題是執行時間。該程序在輸入處獲取數據,並且必須在指定時間內(6.20秒)滿足要求,但我的執行時間約爲7.99秒,我正在尋找解決方案來改進它。 – wege