CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 4 of 4 FirstFirst 1234
Results 46 to 46 of 46
  1. #46
    Join Date
    Jul 2013

    Re: Difficult Algorithm!

    Quote Originally Posted by razzle View Post
    Your problem eludes a dynamic programming formulation (at least I couldn't do it).
    Well, I think I can now.

    The villages are visited in order along the street (from lower distances to higher).

    The first and the last hospitals are special cases. We start with the first hospital and it can be placed at any village. Then for each placed hospital we place the next at a higher distance. When calculating the total distances we include villages at lover distances only, except for the last hospital when all villages are included.

    The hospitals are placed in stages, one in each stage. In each stage we calculate the lowest total distance for each possible placement of one hospital by considering the previous stage only. When a hospital is placed it adds to the total distance function but the addition is independent of placements made in earlier stages. At each stage we have the best possible placements so far and we can track back which placements led up to them. This is also true for the final stage where the best placement of the last hospital will reveal the best placement of all hospitals, and we have an optimal solution.

    That's a proper dynamic programming formulation but it's just a sketch of course. The rest is the homework.
    Last edited by razzle; September 8th, 2014 at 04:17 AM.

Page 4 of 4 FirstFirst 1234

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Windows Mobile Development Center

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)

We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.