-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
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
[FEATURE]: Want to add Hamiltonian Path problem in JS repo. #1735
Comments
@HRIDYANSHU054 kindly assign this issue to me |
@Jivanjamadar I don't have the necessary permissions to do that, you should ask a maintainer. |
@vbrazo kindly assign this issue to me |
Sure, but please implement the Held-Karp algorithm. The naive "enumerate all permutations" algo (1) doesn't add much vs. generate permutations etc. which we already have; (2) is much slower (exponential vs factorial). |
@appgurueu You mean, I have to implement Held-Karp algorithm to just calculate minimum cost to visit all cities in TSP ( travelling salesman) or implement both Held-Karp algorithm and hamiltonian algorithm in program to find Hamiltonian path & minimum cost to visit all cities at once. |
Sure, implementing it as a solution to the TSP problem also works, and is more useful, since Hamiltonian cycle is just a special case of the TSP. (And Hamiltonian path can be reduced to Hamiltonian cycle.)
I'm not aware of a "hamiltonian algorithm" related to this. Please do not confuse algorithm and problem. The Held-Karp algorithm can be used to solve the Hamiltonian cycle (and thus the Hamiltonian path) problem more efficiently than the naive algorithm of enumerating all permutations, again because it's essentially a special case of TSP. |
Motivation
In backtracking, Hamiltonian problem is plays great role. Adding this file of program in JS & test file increase it's diversity.
Examples
Pathfinding Algorithms: This is useful for finding specific paths in graphs, such as city routing problems.
Puzzle Solving: Problems like the Knight's Tour in chess or Traveling Salesman Problem can have solutions inspired by Hamiltonian paths.
Game Development:
In games where players need to visit locations without revisiting them (e.g., mazes or maps), this algorithm helps check the validity of paths.
Possible workarounds
Graph Theory Library:
This program could be part of a broader graph algorithms library. You can add this class alongside other algorithms like DFS, BFS, Dijkstra, etc.
Puzzle Solvers:
Hamiltonian paths are used in puzzles and games, and this program could be a part of a game engine that checks valid paths or graph traversal.
Educational Projects:
If your open-source project is educational (focused on algorithms and data structures), this could serve as a solid example of backtracking and graph traversal.
Additional information
No response
The text was updated successfully, but these errors were encountered: