51 ms·
Step 1 in this situatoon is to try and see if this is a known mathematically unsolved problem, and if it is, giving up. Isn't this just trying to find a hamilt
by leothetechguy 9mo ago
Step 1 in this situatoon is to try and see if this is a known mathematically unsolved problem, and if it is, giving up.
Isn't this just trying to find a hamiltonian cycle, isn't this NP hard? That's when I would give up, especially because you put so many constraints in it to make it human walkable.
Edit: Of course you don't have to give up, but it's good to know what you get yourself into
- procaryote 9mo agoWhy would you give up just because something is NP hard if there are good algorithms to approximate a solution, and an approximate but good solution is useful?
- viraptor 9mo agoYeah, there are many problems which are np-hard in theory, but then realistic cases give you way more constraints that make them solvable. So many hard graph problems become way simpler when applied to real maps, because you know that if you start getting away from something, your minimum remaining distance grows. But on an abstract graph there's no real mapping to our dimensions.
- threatofrain 9mo agoThat just means you didn’t encode the information you wanted into the graph.
- viraptor 9mo agoThere's no "information you wanted" in the plain np-hard version of traveling salesman for example. There's only cost. My point was that things get easier if you have the extra information and aren't solving the plain version anymore.
- deleted 9mo ago[deleted]
- stabbles 9mo agoFor constant n even exponential complexity reduces to constant time