3 ms·
Your Favorite NP-Complete Cheat
- sdp 18y agoMy favorite NP-Complete Cheat: using A* heuristic search to find a solution in the graph of possible Rubik's cube configurations.
- lliiffee 18y agoMy favorite NP-complete cheat: You want to solve an integer programming problem, something like max sum_i x_i f_i Where the x_i are restricted to be binary. The cheat: Just let the x_i be real numbers in the [0,1] interval, and solve the problem through a super-efficient linear programming solver. If you happen to end up with a solution where all the x_i are binary, you have successfully found a solution to the original problem. If you aren't so lucky, well... This is simple, fast, and works amazingly well amazingly often.