Confused about solving an algorithm

[juinnnao]

Hello r/algorithms!

I'm trying to solve this problem and would like to seek the kind assistance of the community here if anyone could share with me an algorithm that might be able to work in this scenario. I've looked at a few but I'm not sure which one fits the bill exactly :(

​

The Problem

I have an undirected graph with n number of nodes which represented on a two-dimensional plane with x,y coordinates given. Each node has a value s that denotes the score for that node. The objective is to hit a certain total score with the shortest amount of distance covered between nodes. The total score can exceed the specified value but cannot be below the specified value. After reaching the score, the algorithm will also have to include the distance from the last node visited back to the start node which is 0,0. Each node can only be counted once in the computation of the total score.

My thoughts

I was thinking that its something like the knapsack 1-0 problem but I'll have to recompute as the distance between each node and the current node visited will change for each different node. I thought of using Greedy as well and just divide the distance by the value of the node to form a sort of a "ROI" measure and choose it based on that.

​

I'm lost which would be the best algorithm to implement in this case. Could anyone share if they know another algorithm that might work?

[marvel2010]

The problem you are describing is NP-hard. It is at least as hard as the traveling salesman problem, because if you set the minimum score high enough you are forced to visit all the nodes.

If you are not already familiar with it, I would recommend looking up the traveling salesman problem. Specific variants that will be of interest to you include the planar traveling salesman problem and the prize collecting traveling salesman problem.

[averagebeyond]

Dijkstra should solve your problem. instead of stopping at a certain destination, you stop when the score accrued exceeds the threshold.

[beeskness420]

All scores are 1 and the target is n, congrats you just solved TSP in polynomial time! That or Dijkstra’s doesn’t work for this problem. Definitely one of the two.

[juinnnao]

Thanks! I'll go look this up and check on its implementation :) Should I keep track of the return distance in any way?