It'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.
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.