Timeline for Finding the shortest path through a digraph that visits all nodes
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 25, 2014 at 16:02 | comment | added | Boluc Papuccuoglu | Your last comment helped a lot, I was able to create a brute force search algorithm that heuristically preferred edges that led to vertices which were unexplored. A Hamiltonian path did indeed exist. | |
| Aug 25, 2014 at 16:00 | vote | accept | Boluc Papuccuoglu | ||
| Aug 21, 2014 at 13:21 | comment | added | Joseph Pepper | For example, if you can identify a small number of nodes whose removal partitions the graph into several pieces, you can make an approximate solution by combining solutions to the different subgraphs and linking across the cut nodes. However, this is unlikely to be optimal. | |
| Aug 21, 2014 at 13:18 | comment | added | Joseph Pepper | For a generic graph, there's not much you can do besides improved versions of brute force. More specific properties are necessary in order to tailor an algorithm to it. | |
| Aug 21, 2014 at 13:14 | comment | added | Boluc Papuccuoglu | I am not saying that I need to find an algorithm for any graph that fits my description. I have a certain 256-node graph that I need to solve. | |
| Aug 21, 2014 at 13:13 | history | edited | Joseph Pepper | CC BY-SA 3.0 | Clarity |
| Aug 21, 2014 at 13:10 | comment | added | Joseph Pepper | Yes, but if such an algorithm exists it can be used to solve the Hamiltonian path existence problem as I described, which makes the problem you are working on NP-hard. I edited my answer slightly to make this more clear. | |
| Aug 21, 2014 at 12:48 | comment | added | Boluc Papuccuoglu | To clarify, I am not saying that there is a Hamiltonian path and I need to find it, I am trying to find the shortest path in the 256 node graph that visits each node AT LEAST once. With the 27 node run, I was able to find a Hamiltonian path, which assured me that it was an optimal solution. I want to find a solution for the 256 node graph which is the shortest. | |
| Aug 21, 2014 at 12:45 | review | First posts | |||
| Aug 21, 2014 at 13:22 | |||||
| Aug 21, 2014 at 12:40 | history | answered | Joseph Pepper | CC BY-SA 3.0 |