The problem statement is the following: given a non-empty set P of (x, y) points with an associated reward, find the path through P that gives the maximum earning. The earning of a path is the sum of the rewards minus the total cost of visiting each point, measured as the distance between any pair points. I have to design a Divide and Conquer algorithm to solve the problem.

The first thing I did was to partition the set in two halves, which I did successfully calculating the middle point of each coordinate axis. Then, I designed a brute force solution for the base case, for routes of size 3 or less which gives optimum solutions in a reasonable amount of time.

Now, the part I'm struggling with is the combine part of Divide and Conquer. I figured I have to merge two optimum size 3 or less routes together, but I'm having a hard time finding a solution. Joining the paths by the end-points doesn't work well, and neither does necessarily joining the end-points with their nearest neighbor. I don't know graph theory yet, maybe it's necessary?

I'd appreciate any tip, reference or direction to find a way to solve the problem for bigger subproblems.

  • $\begingroup$ What definition of "path" do you use? Do you allow vertices to be visited multiple times? Edges to be used multiple times? If you visit a vertex multiple times, do you get multiple copies of the reward? Can you credit the source where you encountered this? $\endgroup$
    – D.W.
    Commented Feb 13 at 6:57
  • $\begingroup$ A path is a line that joins any two points. Vertices can be visited at most once but it's not required. Edges don't need to be used more than once. Rewards can be collected just once because vertices can be visited at most once. This is from a series of projects of a local University I'm studying for self learning. $\endgroup$
    – synzgrsck
    Commented Feb 13 at 13:31
  • $\begingroup$ Our site works differently from others you might be used to. We're not a forum. Please don't respond to comments in the 'Your Answer' box. The 'Your Answer' box should be reserved for material that directly answers the question asked. Please don't put extra information in an answer or comment. Instead, edit the question to revise it so it contains all relevant information, and so people don't need to read anything other than the question to understand what is being asked. $\endgroup$
    – D.W.
    Commented Feb 13 at 17:47
  • $\begingroup$ A path must be a straight line? You can't go from A to B and then B to C unless A,B,C are all on a straight line? That sounds counter-intuitive. I encourage you to credit the original source. $\endgroup$
    – D.W.
    Commented Feb 13 at 17:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.