| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* Add greedy algorithm for solving TSP
Many problems of Combinational Optimization can be represented as graphs.
These problems have enormous significance in many aspects of science, but there are not any algorithms to solve some of them in polynomial time. However many, heuristic and metaheuristic algorithms have been published over the past years in order to solve / approximate the solutions to these problems.
The purpose of this commit is to add implementation of such algorithms for solve one of the most famous problems of Combinational Optimizations, Travelling Salesman Problem (TSP). A greedy algorithm has been implemented at the moment for this reason. "applications" package has been created which include modules that represent a problem. Each module contains several algorithms for solving the specific problem.
At this commit, tsp.py module is added which contains greedy_tsp()
function; a implementation of a greedy algorithm.
* Fix example error
* Trivial changes
List of changes:
Removal of unnesecary _is_weighted() function
Improvements on documentation
* Add applications package to setup.py file
* Change output of greedy algorithm
Algorithm's output is a list of nodes now
* Add simulated annealing algorithm
Add a metaheuristic local search algorithm for solving TSP
* Minor changes
* Fix example doc errors
* Compatible with python 3
* Move tsp module to algorithms package
* Code improvements
* Handle small graphs and fix doc examples
* Documentation changes and rename variables
* Adds Threshold Accepting algorithm for TSP
* Implemented maximal matching of minimal weight and created test suite.
* Removed useless print
* Implemented Christofides.
* Coding was missing
* Add more general traveling_salesman_problem using christofides
Also reconfigure import structure and remove min_weight_matching from
module since it is now in matching.py
* Add new functions to the docs and minor typos
* pep8 fixes
* fix pep8 and change .gitignore
* Add tests of the approximation namespace
update docs in approximation/__init__.py
* Fix is_matching to check if edges in G. Other tweaks:
doc changes
and put not_implemented_for on find_matching functions
* Improve is_matching selfloop handling and expand tests
* Move tsp to approximation directory. Apply black.
* Move tsp tests to approximation tests folder
* Attempt to bring tsp up to current code.
* commit pep8 that my black didnt change, but pep8speaks did find. ??
* tweak a few things and run black
* combine #4083 and #3585 into traveling_salesman.py
* Match chistofides output to other tsp functions
and adjust calling syntax of tests
tweak docs
tweak see also section
* Put big-O complexity in in-line math env.
Prevents sphinx from trying to do variable substitution between
pipes.
* Minor touchups to christofides docstring.
* RST touchups to tsp module docstring.
* Rm extra string from tsp module.
* Docstring touchups for traveling_salesman_problem.
* rst fixups for greedy_tsp docstring.
* rst formatting for simulated annealing docstring.
* More math in-lining for simulated annealing docstring.
* rst and minor grammatical fixes to TA docstring.
* Fix path-finding and test all methods for tsp function
* the refactoring was incomplete. Now maybe is
- Add tests of TSP with all methods.
- Refactor tests to match simulated_annealing tests and threshold tests.
- Unify treatment of weight so unweighted edges use default weight 1.
weight now defaults to "weight" with a default value of 1.
- Rename tolerance to max_iterations (tolerance is used for error bound)
- Rename iterations to N_inner (each iteration takes this many inner loops)
- Introduce idioms like `pairwise` and `cycle.copy()` (over cycle[:])
- Allow passthrough of method kwargs for traveling_salesman_problem
Still need to:
- add test of case where path is more than one edge less that cycle
(incomplete_graph)
- require cycle input (maybe make default list(G)??)
- consider the complexity claims in the doc_strings
* More api changes to TSP functions
- `chritofides` now allows (and ignores) selfloops
- `move` can be a function as well as "1-1" and "1-0"
- `method` for traveling_salesman_problem must have 2 arguments
instead of passing kwargs. User must "curry" to set parameters
- changed doc_string typos in matching.py
* Add test to check that cycle=False can remove many edges
* Change init_cycle api to require input from user
The idea is to make the user specify the initial cycle to start from
rather than relying on the programmers default of a greedy algorithm.
To easy usage, I check for a string "greedy" as a shortcut.
* Update docs with more correct complexity info.
* Check for complete graph now more efficient and selfloops ignored
* merge is_matching changes
Co-authored-by: Thodoris Sotiropoulos <theosotr@windowslive.com>
Co-authored-by: Luca Cappelletti <cappelletti.luca94@gmail.com>
Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
|
