Difficult Algorithm! - Page 4
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

Thread: Difficult Algorithm!

  1. #46
    Join Date
    Jul 2013
    Posts
    349

    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 05: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

This is a CodeGuru survey question.


Featured


HTML5 Development Center