5 ms·
Could do a Breadth First Search. Add a memo table to make it faster. The memo table key would be the vector changed into an int i.e. (2,1,4,5,3) -> 21453. Th
by spaghetti 18y ago
Could do a Breadth First Search. Add a memo table to make it faster. The memo table key would be the vector changed into an int i.e. (2,1,4,5,3) -> 21453. The memo table value would just be a bool... true if we've already seen the current permutation of the vector, false otherwise.
- endtime 18y agoWhy 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.