Approximation algorithm. How to find shortest cycle that gains >= x points

Question

There's a map with points:

The green number next to each point is that point's ID and the red number is the bonus for that point. I have to find fastest cycle that starts and ends at the point #1 and that gains at least x (15 in this case) bonus points. I can use cities several times; however, I will gain bonus points only once. I have to do this using Approximation algorithm, but I don't really know where to start.

The output would look like this:

(1,3,5,2,1) (11.813 length)

Answer 1

Isn't that a NP problem? If it is, you cannot find the fastest one without testing all possibilities, which would take rather long.

The problem is similar to the Traveling Sales Man, IMHO. The best known solution for this problem so far is the Ant Colony Solution. This solution does not guarantee to always find the best solution possible, but it will find at least a pretty good solution within an acceptable amount of time.

I think it may be possible to modify the Ant Colony Solution to also address your problem, by taking the bonus points into account somehow. Probably not the answer you hopped to hear, but the best one I have to offer at the moment.