Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feat: Added Travelling Salesman Problem using bit-manipulation #2136

Merged
merged 10 commits into from
Jan 22, 2023

Conversation

Rytnix
Copy link
Contributor

@Rytnix Rytnix commented Oct 5, 2022

Description of Change

In this algorithm, we are going to use Bitmasking technique to solve the famous NP-hard Traveling Salesman Problem.
As we know working with bits decreases the time complexity a little bit.
What I did is considered the nodes/cities as bits of a decimal no and traversed the whole path, Since traversing will have
redundant computations so, I used a dynamic programming memoization technique to overcome that.

Checklist

  • Added description of the change
  • Added file name matches File name guidelines
  • Added tests and examples, test must pass
  • Added documentation so that the program is self-explanatory and educational - Doxygen guidelines
  • Relevant documentation/comments is changed or added
  • PR title follows semantic commit guidelines
  • Search previous suggestions before making a new one, as yours may be a duplicate.
  • I acknowledge that all my contributions will be made under the project's license.

Notes:

Copy link
Member

@Panquesito7 Panquesito7 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Great work! 🚀

@Panquesito7 Panquesito7 added enhancement New feature or request automated tests are failing Do not merge until tests pass requested changes changes have been requested labels Oct 5, 2022
@Rytnix Rytnix requested a review from Panquesito7 October 5, 2022 18:13
@Rytnix
Copy link
Contributor Author

Rytnix commented Oct 8, 2022

Hi @Panquesito7, Please review my PR, It's been 4 days since I fulfilled your requested changes.

@Panquesito7 Panquesito7 removed the automated tests are failing Do not merge until tests pass label Dec 27, 2022
@Panquesito7 Panquesito7 removed the requested changes changes have been requested label Dec 27, 2022
Copy link
Member

@Panquesito7 Panquesito7 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Amazing. Thank you! 🚀

@Rytnix
Copy link
Contributor Author

Rytnix commented Jan 12, 2023

@Panquesito7 Please merge this pull request.

@Panquesito7 Panquesito7 merged commit 0931d53 into TheAlgorithms:master Jan 22, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging this pull request may close these issues.

[FEATURE] Travelling Salesman - DP Optimisation using BitManipulation
3 participants