Optimize settlement merging

[cowfee]

Settlement merging will first be done by simply merging the settlements in a randomized order. It is possible to improve this process:

• Use a dynamic programming approach, keeping a map of Set<solution ID> -> final merged settlement> (memoization) and recursively attempting to calculate every valid settlement and then picking the best-scoring one.
• Use a greedy approach where the settlement merging process assumes the following heuristic: it's best to merge the higher-scoring settlements. So, before merging, score all the settlements, and then try to merge them in order of highest score first. Since this is a dumb greedy algorithm, this can be very suboptimal (merging three lower-scoring solutions can be better than merging two higher-scoring solutions, but this algorithm would do the latter). It should be investigated whether or not this yields better results in practice compared to the randomization approach.
• A combination of the above: maybe use dynamic programming if the number of settlements is sufficiently small, and switch to a different approach otherwise.

[github-actions[bot]]

This issue has been marked as stale because it has been inactive a while. Please update this issue or it will be automatically closed.