我正在對 TSP 實施貪婪方法：
從第一個節點開始。
轉到尚未訪問的最近節點。（如果有多個，請轉到索引最低的那個。）
不要忘記包括從節點 1 到最后訪問的節點的距離。
但是，我的代碼給出了錯誤的答案。我在 Python 中實作了相同的代碼，python 代碼給出了正確的答案。
在我的問題中，節點是二維平面上的坐標，距離是歐幾里得距離。
我什至將所有內容都更改為，long double因為它更精確。
事實上，如果我顛倒for回圈的順序來反轉方向并添加一個額外的if陳述句來處理關系（我們想要最小索引最近的節點），它會給出一個非常不同的答案。
這是因為精度問題嗎？
（注意：我必須列印floor(ans)）
輸入：鏈接
預期輸出：1203406
實際輸出：1200403
#include <iostream>
#include <cmath>
#include <vector>
#include <cassert>
#include <functional>
using namespace std;
int main() {
freopen("input.txt", "r", stdin);
int n;
cin >> n;
vector<pair<long double, long double>> points(n);
for (int i = 0; i < n; i) {
int x;
cin >> x;
assert(x == i 1);
cin >> points[i].first >> points[i].second;
}
// Returns the squared Euclidean Distance
function<long double(int, int)> dis = [&](int x, int y) {
long double ans = (points[x].first - points[y].first) * (points[x].first - points[y].first);
ans = (points[x].second - points[y].second) * (points[x].second - points[y].second);
return ans;
};
long double ans = 0;
int last = 0;
int cnt = n - 1;
vector<int> taken(n, 0);
taken[0] = 1;
while (cnt > 0) {
pair<long double, int> mn = {1e18, 1e9};
for (int i = 0; i < n; i) {
if (!taken[i]) {
mn = min(mn, {dis(i, last), i});
}
}
int nex = mn.second;
taken[nex] = 1;
cnt--;
ans = sqrt(mn.first);
last = nex;
}
ans = sqrt(dis(0, last));
cout << ans << '\n';
return 0;
}
UPD：Python代碼：
import math
file = open("input.txt", "r")
n = int(file.readline())
a = []
for i in range(n):
data = file.readline().split(" ")
a.append([float(data[1]), float(data[2])])
for c in a:
print(c)
def dis(x, y):
cur_ans = (a[x][0] - a[y][0]) * (a[x][0] - a[y][0])
cur_ans = (a[x][1] - a[y][1]) * (a[x][1] - a[y][1])
cur_ans = math.sqrt(cur_ans)
return cur_ans
ans = 0.0
last = 0
cnt = n - 1
take = []
for i in range(n):
take.append(0)
take[0] = 1
while cnt > 0:
idx = -1
cur_dis = 1e18
for i in range(n):
if take[i] == 0:
if dis(i, last) < cur_dis:
cur_dis = dis(i, last)
idx = i
assert(idx != -1)
take[idx] = 1
cnt -= 1
ans = cur_dis
last = idx
ans = dis(0, last)
print(ans)
file.close()
# 1203406
uj5u.com熱心網友回復：
是的，差異是由于舍入誤差造成的，由于您使用了long double. 如果您更改 C 代碼，使其使用與 Python 相同的精度（IEEE-754，即double精度），您會在兩個代碼中得到完全相同的舍入誤差。這是 Godbolt Compiler explorer 中的演示程式，您的示例歸結為 4000 分：https ://godbolt.org/z/rddrdT54n
如果我在整個輸入檔案上運行相同的代碼，我會在 C 和 Python 中得到 1203406.5012708856 （必須離線嘗試，因為 Godbolt 可以理解地殺死了該程序）。
請注意，理論上您的 Python 代碼和 C 代碼并不完全相似，因為它們會按字典順序std::min比較元組和對。因此，如果您有兩個完全相等的距離，則呼叫將選擇兩個索引中較小的一個。但實際上，這并沒有什么不同。std::min
現在我不認為你真的可以擺脫四舍五入的錯誤。有一些技巧可以最小化它們。
使用更高的精度 (
long double) 是一種選擇。但這也會讓你的代碼變慢，這是一個權衡重新調整您的點，使它們相對于所有點的質心，并且單位反映您的問題（例如，不要以毫米、英里、公里或其他方式思考，而是以“資料集的方差”為單位）。在計算歐幾里得距離時，您無法擺脫數值抵消，但如果相對距離與坐標的絕對值相比較小，則抵消通常更嚴重。這是一個小演示：
#include <iostream> #include <iomanip> int main() { std::cout << std::setprecision(17) << (1000.0001 - 1000)/0.0001 << std::endl << (1.0001 - 1)/0.0001 << std::endl; return 0; }0.99999999974897946 0.99999999999988987最后，還有一些技巧和演算法可以更好地控制大額誤差累積（https://en.wikipedia.org/wiki/Pairwise_summation , https://en.wikipedia.org/wiki/Kahan_summation_algorithm）
最后一條評論，與您的問題有點無關：auto與 lambdas 一起使用，即
auto dis = [&](int x, int y) {
// ...
};
C 有許多不同型別的可呼叫物件（函式、函式指標、仿函式、lambdas 等），并且std::function是一種有用的包裝器，可以讓一種型別代表具有相同簽名的所有型別的可呼叫物件。這會帶來一些計算開銷（運行時多型性、型別擦除），并且編譯器將很難優化您的代碼。因此，如果您不需要 的型別擦除功能std::function，只需將您的 lambda 存盤在用 . 宣告的變數中auto。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/510557.html
標籤：C 调试精确旅行推销员