2-opt

[News]

Replacing distance squared function with normal eucledian distance function.

← Previous revision​	Revision as of 23:12, 5 May 2024​
Line 65:	Line 65:
If <code>lengthDelta</code> is negative that would mean that the new distance after the swap would be smaller. Once it is known that <code>lengthDelta</code> is negative, then we perform a 2-opt swap. This saves us a lot of computation.	If <code>lengthDelta</code> is negative that would mean that the new distance after the swap would be smaller. Once it is known that <code>lengthDelta</code> is negative, then we perform a 2-opt swap. This saves us a lot of computation.
Also using squared distances there helps reduce the computation by skipping a square root function call. Since we only care about comparing two distances and not the exact distance, this will help speed things up. It's not much, but it helps with large datasets that have millions of vertices
=== C++ code ===	=== C++ code ===
Line 91:	Line 89:
// Distance between two points squared	// Distance between two points squared
inline int dist2(const Point &other) const {	inline int dist(const Point &other) const {
return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);	return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
}	}
};	};
Line 100:	Line 98:
int length = 0;	int length = 0;
for (int i = 0; i < path.size(); i++) {	for (int i = 0; i < path.size(); i++) {
length += path.dist2(path[(i + 1) % path.size()]);

[TD]length += path.dist(path[(i + 1) % path.size()]);[/TD]

[TR]
[TD]}[/TD]

[TD]}[/TD]
[/TR]
[TR]
[TD]return length;[/TD]

[TD]return length;[/TD]
[/TR]
[TR]
[TD]Line 148:[/TD]
[TD]Line 146:[/TD]
[/TR]
[TR]
[TD]for (int i = 0; i <= n - 2; i++) {[/TD]

[TD]for (int i = 0; i <= n - 2; i++) {[/TD]
[/TR]
[TR]
[TD]for (int j = i + 1; j <= n - 1; j++) {[/TD]

[TD]for (int j = i + 1; j <= n - 1; j++) {[/TD]
[/TR]
[TR]
[TD]int lengthDelta = -path.dist2(path[(i + 1) % n]) - path[j].dist2(path[(j + 1) % n]) + path.dist2(path[j]) + path[(i + 1) % n].dist2(path[(j + 1) % n]);[/TD]

[TD]int lengthDelta = -path.dist(path[(i + 1) % n]) - path[j].dist(path[(j + 1) % n]) + path.dist(path[j]) + path[(i + 1) % n].dist(path[(j + 1) % n]);[/TD]
[/TR]
[TR]
[TD][/TD]

[TD][/TD]
[/TR]
[TR]
[TD]// If the length of the path is reduced, do a 2-opt swap[/TD]

[TD]// If the length of the path is reduced, do a 2-opt swap[/TD]
[/TR]

Okumaya devam et...