# Given two paths, how can I merge them in a Divide-and-Conquer algorithm to find the optimum earning route given a set of points with rewards?

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.

• 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?
– D.W.
Commented Feb 13 at 6:57
• 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. Commented Feb 13 at 13:31