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.
- etc
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.