leo848 / jufo2024-backend Goto Github PK

Held-Karp should be optimal. The current implementation always hands out near-optimal results. Thus, the question remains – why does this happen? Possible bugs need to be addressed.

Is currently O(n)

This improves code readability and showability. Also, more algorithms and traits can be added.

The insertion heuristic takes an existing path, checks for each vertex and each edge in the path how much it would cost to insert and then inserts the optimal vertex at the optimal location.

Complexity: O(n³)
list traversal * vertex choice * length of existing path