Repository navigation
[FEATURE]: Want to add Hamiltonian Path problem in JS repo. #1735
Description
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
Activity
Jivan052 commentedon Oct 17, 2024
@HRIDYANSHU054 kindly assign this issue to me
HRIDYANSHU054 commentedon Oct 18, 2024
@Jivanjamadar I don't have the necessary permissions to do that, you should ask a maintainer.
Jivan052 commentedon Oct 18, 2024
@vbrazo kindly assign this issue to me
appgurueu commentedon Oct 20, 2024
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).
Jivan052 commentedon Oct 20, 2024
@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.
Please, clarify so i can start to write program.
appgurueu commentedon Oct 20, 2024
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.