So, for the purposes of creating a heuristic for a Sokoban AI, I have to solve the following problem (if you're curious, the elements of the matrix each represent taxicab distances from boxes to storage tiles):
There is an nxn matrix. Suppose S is a sum of n elements in the matrix, with the restriction that no two elements in this sum can share the same row or column number. Find the minimum value of S. (If it helps, each element is always a non-negative integer).
The naive approach is to loop through all n! permutations of elements and find the smallest one. But this is bad, it runs on order O(n!). I kept trying to think of optimizations, but nothing came to mind, just a bunch of probabilistic stuff and special cases, i.e. if one of the elements is a LOT bigger than the rest of the elements, don't let that ever be a part of the sum.
If anyone has a good solution to this, please post below, thanks! If not, I guess I can show you what I got so far, and maybe you can build off it???
I at some point came up with an idea. It's flawed, it doesn't always work, but I feel like I might be on the right track with this one:
Suppose my original matrix is M. Construct the matrix N, such that $N_{i,j} = b^{M_{i,j}}$, where b is some positive base less than 1. The problem is now the same as asking "Suppose P is a product of n elements in the matrix, with the restriction that no two elements in this product can share the same row or column number. Find the maximum value of P, then take the base b logarithm."
I then realized that, if two numbers have vastly, vastly different orders of magnitude, then finding the maximum between them (or rather, finding which one has the largest absolute value) is basically the same as adding them together. If we set b to be an extremely small number (say, 1/googol), then all the aforementioned values of P will have vastly different orders of magnitude (unless some of the values of P are the same. We'll get back to that later, but for now let's just ignore this nuance). As a result, our problem can be reduced to solving the sum of all values of P.
Now, one of several ways to define a determinant is to take all possible permutations of elements in the matrix such that no two elements share row numbers or column numbers, then find the product of each permutation, then multiply each odd permutation by -1, and finally add together these products. What we have is basically the same, but without the multiply by -1 step.
But that's an easy thing to fix. Our rule about adding things to get the maximum also works for subtracting, just as long as you don't mind the result being negative.
So, the process here is to construct a matrix N such that $N_{i,j} = ε^{M_{i,j}}$, where ε is an extremely small number. Then, compute the determinant of N. Then, take the absolute value. Then, take the base ε logarithm.
Technically, because of roundoff, it would be impractical to implement this using floating points, so I instead thought I'd make a class which simulates hyperreal numbers. For those who don't know what that is, just imagine a number system that includes h, and we're taking the limit as h goes to 0. In this case, h is our base (AKA b AKA ε).
So, in theory, this should work, and it should run at order O(n³) or O(n⁴), depending on how you do it. There's just one problem. If there are any ties, it doesn't work. That is, if in our original problem, there is one value of S which is smaller than all other values for S, this does work. Otherwise, it probably doesn't. It all ties back into that assumption that no two values of P would equal. If you add or subtract two numbers, one wayyyy huger than the other, you'll basically get whichever one is bigger (times ±1). But if the two numbers you add are the same, you'll either get twice the maximum, or you'll get 0. The twice the maximum case isn't too bad, you can just divide by 2 or 3 or whatever before taking the base ε logarithm. But in the case of 0, it's completely irreparable. So, if the minimum value for S is a tie between two permutations, but both permutations have opposite parity, this algorithm will completely fail.
So, yeah, that's all I got. I tried a bunch of things out. I tried multiplying every other element by -1 (which doesn't change anything, turns out), I tried multiplying each element by other values, but that led nowhere. I had this crazy idea where you multiply element i,j by $q^{(n²)^{i-1+n(j-1)}}$, where q is just some random variable, but I'm not sure where I was going with that. My brain is fried at this point, I'm gonna take a break from this problem.
Thanks!