-
-
Notifications
You must be signed in to change notification settings - Fork 7.3k
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
Conversation
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Great work! 🚀
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
Hi @Panquesito7, Please review my PR, It's been 4 days since I fulfilled your requested changes. |
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
Outdated
Show resolved
Hide resolved
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Amazing. Thank you! 🚀
@Panquesito7 Please merge this pull request. |
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
Notes: