It's an optimization problem: computer has to place the
three hospitals so that the cost (number of steps getting every household
to the hospital) is at its lowest.
The simplest algorithm - hill-climbing - solves it in 11 steps.
Yet the algorithm might just find a local minimum. In a more complex situation ie given a
larger 'state-space' with more houses, , one might want to do better...
So begins the CS50 AI optimization lecture. Very timely, to my mind. I had just
finished watching a video on plans to build solar farms in the Sahara.
* * *
This is the gig: the computer moves a hospital up, down, sideways
and if one of these is more cost-effective, that one becomes the new
start position. When there are no more better choices, the program stops.
The difficulty is that one can get bottlenecked in a local minimum.
There are variations on the hill-climbing algorithm:
The example below is from a random restart(with maximum at 20). What came
back was between 36 and 54.
No comments:
Post a Comment