Dear all,
When I read the greedy example on page 32 “Consider 2n cities on a line, half of which are white, and the other half
are black.” of chapter 1, I feel a little lost. Could you please elaborate more on the input and output?
If “Multiple pairs of cities may share a single section of road”, why not simply connect city 0 with city n (suppose they have difference colors) and all other pairs are automatically connected?
thanks.
Yang
Hey Yang,
Sorry for my late reply. I think the reason you cannot simply connect the first and the last cities (i.e., 0 and n - 1) is because they may have identical color which stops us pairing them. I think we probably will draw an figure to further explain this. Please let us know if you have any problem.
Thanks a lot for your response.
What if the input is 1:white, 2:white, 3:black, 4:black?
According to the optimum solution, i.e. “pairing each city with the nearest unpaired city of different color”, then the pairing would be 1<->3 and 2<->4, however the global optimum would be just connecting 1 and 4?
Hey Yang,
In your case, the segments of 1<->3 and 2<->4 have overlapped part 2<->3 which will be double-counted. Therefore, this solution will be identical to connecting 1<->4 directly. In other words, both solutions uses the same length of road.
BTW, it seems that you have owned EPI for a while, and we would like to hear your opinions personally 
Could you email us to tsung.hsien.lee@gmail.com, adnan.aziz@gmail.com ?