Lets assume that you’re dating because you want to find the optimal partner aka true love. Computer Science has developed a number of heuristic algorithms that you might find useful:
- Random Walk
- change to a random partner (perhaps whenever you believe your partner is below the mean) until time runs out.
- Hill Climbing
- grab the best partner you can see from where you are and repeat until that’s the partner you’re currently with.
- Memetic Algorithm
- ask other people how they found their current partner. (And then use that advice depending on whether you think their partner is above or below the mean.)
- Genetic Algorithm
- grab a bunch of partners and keep the best one, repeat until time runs out.
- Simulated Annealing
- like hill climbing, but take a chance with a random partner sometimes, doing this less and less as your biological clock ticks down.
It may appear that most people are naively employing the suboptimal random walk algorithm or hill climbing at best, however dating is a lot messier than most NP problems:
- You can only know the exact goodness of a partner once you’ve been with that partner.
- The goodness of a partner is ineffable (reducing the effectiveness of a memetic algorithm), and even if it weren’t goodness isn’t constant;
- Thanks to Wittgenstein’s Private Language Argument, you can’t remember how good your last partner was.
- Changing partners has some (variable) cost.
- Once you’ve changed partners, it’s very difficult to go back.
- Taking other people’s partners brings up a whole host of complications;
- As does having multiple partners at one time (ruling out a genetic algorithm).
Since genetic algorithms won’t work in practice, simulated annealing appears to be the best way to avoid stopping at a local maxima; however I am uncertain that it is better than a random walk. Is simulation the only way to be sure?
This has been a nodeshell rescue by your friendly neighbourhood CS grad student.