Opened 9 years ago
Closed 6 years ago
#386 closed task (done)
Heuristic algorithms for symmetric TSP
Reported by: | Peter Kovacs | Owned by: | Peter Kovacs |
---|---|---|---|
Priority: | major | Milestone: | LEMON 1.3 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description
Attachments (4)
Change History (19)
Changed 9 years ago by
Attachment: | 386-tsp-7ed08f6da055.patch added |
---|
comment:1 Changed 9 years ago by
Status: | new → assigned |
---|
comment:2 follow-up: 3 Changed 9 years ago by
I'm currently working on the revision and improvement of these tools.
comment:3 Changed 9 years ago by
Replying to kpeter:
I'm currently working on the revision and improvement of these tools.
Just for the record, please summarize what kind of modifications do you plan to make
Changed 9 years ago by
Attachment: | 386-tsp-6bf84eaa22d3--de22e61d6d0c.bundle added |
---|
A bundle file of 5 changesets
comment:4 Changed 9 years ago by
Please skip the previous attachment [7ed08f6da055] (it is not consistent) and consider the new attachment of 5 changesets:
- [6bf84eaa22d3] Heuristic algorithms for symmetric TSP (#386)
- [8e8e162dc361] Add a function for checking metric costs (#386)
- [08d95209631b] Doc group for TSP algorithms (#386)
- [e99bbeec2d02] Document and greatly improve TSP algorithms (#386)
- Add LEMON headers.
- Add Doxygen doc for all classes and their members.
- Clarify and unify the public API of the algorithms.
- Various small improvements in the implementations to make them clearer and faster.
- Avoid using adaptors in
ChristofidesTsp
.
- [de22e61d6d0c] A detailed test file for TSP algorithms (#386)
I think, after applying these patches, the TSP tools could be merged into the main branch. However, the implementation of InsertionTsp
still could be made faster by a factor of n (and the doc should be adjusted accordingly). Gabor or I will implement this enhancement soon.
comment:5 follow-up: 6 Changed 9 years ago by
The doc of TSP algorithms refer to the notion of "metric cost function". Therefore, we introduced checkMetricCost()
for this (see [8e8e162dc361]). I had no better idea than adding a separate header file tsp_utils.h
for this function. (I the future, other tools could be put here.) Do you like this solution?
comment:6 follow-up: 8 Changed 9 years ago by
Replying to kpeter:
The doc of TSP algorithms refer to the notion of "metric cost function". Therefore, we introduced
checkMetricCost()
for this (see [8e8e162dc361]). I had no better idea than adding a separate header filetsp_utils.h
for this function. (I the future, other tools could be put here.) Do you like this solution?
My major complain is why do you use Dijkstra for checking the triangular inequality? It should simply be checked directly for each triangle.
The tsp_utils.h
header file is alright for me, assuming that the tools here are really only useful for TSP related problems.
comment:7 follow-up: 9 Changed 9 years ago by
tsp_test
fails to compile for me:
[ 90%] Building CXX object test/CMakeFiles/tsp_test.dir/tsp_test.cc.o In file included from /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:32:0: /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: In member function ‘lemon::Opt2Tsp<CM>::Cost lemon::Opt2Tsp<CM>::run(const Path&) [with Path = std::deque<lemon::FullGraphBase::Node>, CM = lemon::GraphExtender<lemon::FullGraphBase>::EdgeMap<double>, lemon::Opt2Tsp<CM>::Cost = double]’: /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:193:7: instantiated from ‘void tspTest(const std::string&) [with TSP = lemon::NearestNeighborTsp, std::string = std::basic_string<char>]’ /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:257:49: instantiated from here /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’ /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:193:7: instantiated from ‘void tspTest(const std::string&) [with TSP = lemon::NearestNeighborTsp, std::string = std::basic_string<char>]’ /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:257:49: instantiated from here /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’ cc1plus: warnings being treated as errors /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: At global scope: /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: In instantiation of ‘lemon::Opt2Tsp<CM>::Cost lemon::Opt2Tsp<CM>::run(const Path&) [with Path = std::deque<lemon::FullGraphBase::Node>, CM = lemon::GraphExtender<lemon::FullGraphBase>::EdgeMap<double>, lemon::Opt2Tsp<CM>::Cost = double]’: /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:193:7: instantiated from ‘void tspTest(const std::string&) [with TSP = lemon::NearestNeighborTsp, std::string = std::basic_string<char>]’ /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:257:49: instantiated from here /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:126:12: error: unused parameter ‘tour’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: In member function ‘lemon::Opt2Tsp<CM>::Cost lemon::Opt2Tsp<CM>::run(const Path&) [with Path = std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >, CM = lemon::GraphExtender<lemon::FullGraphBase>::EdgeMap<double>, lemon::Opt2Tsp<CM>::Cost = double]’: /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:193:7: instantiated from ‘void tspTest(const std::string&) [with TSP = lemon::GreedyTsp, std::string = std::basic_string<char>]’ /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:258:30: instantiated from here /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’ /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: At global scope: /home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:126:12: error: unused parameter ‘tour’ Linking CXX executable suurballe_test
comment:8 Changed 9 years ago by
Replying to alpar:
Replying to kpeter:
The doc of TSP algorithms refer to the notion of "metric cost function". Therefore, we introduced
checkMetricCost()
for this (see [8e8e162dc361]). I had no better idea than adding a separate header filetsp_utils.h
for this function. (I the future, other tools could be put here.) Do you like this solution?My major complain is why do you use Dijkstra for checking the triangular inequality? It should simply be checked directly for each triangle.
You're right, it should be improved.
The
tsp_utils.h
header file is alright for me, assuming that the tools here are really only useful for TSP related problems.
I'm not sure about it. Checking whether a cost function is metric or not could be useful in other use cases, too. What do you think?
Should we call this header as metric_cost.h
? Or should we think of a header file, in which this function could be placed along with other similar tools, e.g. checkConervativeCost()
(in the future)?
comment:9 Changed 9 years ago by
Changed 9 years ago by
Attachment: | 386-ae0b056593a7--dff32ce3db71.bundle added |
---|
comment:10 Changed 9 years ago by
I attached a new bundle file that replaces the previous attachments. It contains the follwing 6 changesets:
- [ae0b056593a7] Heuristic algorithms for symmetric TSP (#386)
- [62ba43576f85] Doc group for TSP algorithms (#386)
- [9a51db038228] Document and greatly improve TSP algorithms (#386)
- [ef200e268af2] Unifications and improvements in TSP algorithms (#386)
- [07682e24c4e8] A detailed test file for TSP algorithms (#386)
- [dff32ce3db71] Make InsertionTsp much faster and improve docs (#386)
Four of these changesets are the rebased versions of previously attached ones. The other two make significant improvements:
- [ef200e268af2] fixes the compilation issue.
- [dff32ce3db71] makes the InsertionTsp algorithm faster by a factor of
n
.
In this new bundle file, the checkMetricCost()
utility function is omitted. Currently, I don't find it so important and I don't have a good idea for the name of the corresponding header file.
comment:11 Changed 8 years ago by
Type: | enhancement → task |
---|
comment:12 follow-up: 13 Changed 6 years ago by
I went through the changesets, it looks good. But, I started thinking of an alternative interface - instead of a FullGraph
, the input would be just a set of nodes of a (probably empty) graph plus the cost function (this is something like FullGraph::EdgeMap<>
, I know) and the would be the the graph containing the arcs of the tour. This is a very rough idea, not sure if it make any sense. What do you think?
If you say it's a nonsense, I will just merge the current version as is.
comment:13 Changed 6 years ago by
Replying to alpar:
I went through the changesets, it looks good. But, I started thinking of an alternative interface - instead of a
FullGraph
, the input would be just a set of nodes of a (probably empty) graph plus the cost function (this is something likeFullGraph::EdgeMap<>
, I know) and the would be the the graph containing the arcs of the tour. This is a very rough idea, not sure if it make any sense. What do you think?If you say it's a nonsense, I will just merge the current version as is.
What advantages would this solution have? Could we describe use cases in which it would be much easier or clearer to use? E.g. if you have a connected graph with non-negative edge costs and define the nodes as shortest path distances, then this design could be used in combination with an all-pair shortest path algorithm (see #346). Would it be much easier than mapping the nodes of the original graph to the nodes of a full graph of the same number of nodes? (Anyway, all pair shortest path algorithms could generate a transitive closure graph as a full graph with an edge map plus node reference map(s) similarly to graph copy tools.)
In fact, I don't think that this proposal is nonsense, but I also don't see major advantages.
Changed 6 years ago by
Attachment: | 386-out-iterator-d3dcc49e6403.patch added |
---|
comment:14 Changed 6 years ago by
The attached patch [d3dcc49e6403] improves the API of the TSP algorithms: an output iterator is required instead of a container in the tourNodes()
functions.
comment:15 Changed 6 years ago by
Resolution: | → done |
---|---|
Status: | assigned → closed |
All the relevant changesets are now in the main branch.
[7ed08f6da055] contains the implementation of five TSP heuristics (by Gabor Varga).