3 ms·
Why would you use a blind search rather than A*? It's not hard (edit: actually, maybe it is) to come up with a heuristic for this problem. Also, your memo tab
by endtime 18y ago
Why would you use a blind search rather than A*? It's not hard (edit: actually, maybe it is) to come up with a heuristic for this problem.
Also, your memo table wouldn't work for large vectors...
Edit 2: Even worse, the branching factor of that search tree would be O(n!).
- spaghetti 18y agoRight about the larger vectors. I don't know A*. What's an example heuristic for this puzzle?
- endtime 18y agoIt's actually not easy to come up with an admissible heuristic for this, because of the reversal operator. I'm about to be late for dinner at a friend's so I don't have time to come up with something now, but if no one has by the time I'm back I'll think about it. Edit: How about the sum of the differences of adjacent elements - n - 2? This seems to capture the notion that something reversed but in order is okay. I still don't think this is admissible though. Well, here's an admissible one. Count how many adjacent elements are not the element to the left + 1, and divide that sum by 2. Pretty sure that'd work.