U++ framework: UppHub » New STEM4U package

Home » Developing U++ » UppHub » New STEM4U package

Show: Today's Messages :: Polls :: Message Navigator
E-mail to friend

Re: New STEM4U package [message #54614 is a reply to message #54402]

Thu, 20 August 2020 13:10

koldo
Messages: 3464
Registered: August 2008

Senior Veteran

Added Travelling Salesman algorithm. A demo is included in STEM4U_DemoTest.

The Traveling salesman problem (TSP) of a list of points calculates the shortest possible route that visits each point and returns to the origin.

This is a NP-hard problem that for medium sets could be impractical to be solved by an exact algorithm as brute force or linear programming. Because of that, for practical reasons, its resolution using heuristics and approximations is advised.

This implementation uses a Nearest neighbor algorithm to get an initial guess, and follows with a 2-opt algorithm.

template <typename T> T TSP(const Vector<Vector<T>>& matrix, Vector<int> &order)

Returns the total distance of a traveling salesman problem defined by a matrix of distances between nodes. All the elements of the diagonal of this matrix have to be zero, and the elements above the diagonal are considered. It also returns the most optimal order between the nodes.
order may include an initial guess of the right ordering. If not, order should be empty.

template <typename T> T TSP(const Vector<Point_<T>>& points, Vector<int> &order)

Returns the total distance of a traveling salesman problem defined by a list of euclidean coordinates of the points. It also returns the most optimal order between the nodes.
order may include an initial guess of the right ordering. If not, order should be empty.

Best regards
Iñaki

Report message to a moderator

[Message index]

		New STEM4U package By: koldo on Tue, 25 February 2020 08:11
		Re: New STEM4U package By: koldo on Sun, 12 July 2020 16:48
		Re: New STEM4U package By: koldo on Thu, 20 August 2020 13:10
		Re: New STEM4U package By: koldo on Sun, 23 August 2020 10:05

Previous Topic:	Building TheIDE with using CMake
Next Topic:	plugin/assimp needs information about license

Goto Forum:

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

]

Current Time: Mon Oct 26 01:58:42 GMT+1 2026

Total time taken to generate the page: 0.00729 seconds