Solution to Exercise 4: Finding the Best Connection
Solve Exercise 4 of this chapter.
In this exercise, we need to find the largest subset of cities that have a direct road between any pair of them.
The following illustration can be helpful to understand what we want:
What does a solution look like this time? A solution now is a subset of cities. We don’t care about the order; we just want to know if there’s a road between any pair of them. Therefore, we’ll define operations that work for subsets.
The target function will be the size of the subset if any pair of cities in that subset has a direct path between them, or zero otherwise.
-
mutation
: This removes a city from the subset of cities. -
crossover
: This return the union of two subsets. The union is the collection of the cities included in both subsets but with no duplicates. For example, the union between ...
Get hands-on with 1400+ tech skills courses.