I have read the original problem. Since the number of cities is large, it is impossible to get the exact answer. Approximation algorithm is the only choice. As @maniek mentioned, there are many choices of AA. If you have experience with AA before, that would be best, you can choose one the those which you are familar with and get a approximate answer. However, if you didn't do AA before, maybe you can start with backtracking with pruning.
As for this problem, you can easily get these pruning rules:
- Bring as few blimps as possible. That means when you start from HQ and visit city A,B,C..., and then return to HQ(you can regard it as a single round), the number of blimps you brought is the same as the cities you will visit.
- With the sale price gets lower, when it becomes lower than the travel expense, the city will never be visited. That gives the ending of backtracking method.
You can even apply KNN first to cluster several cities which located nearby. Then start from HQ and visit each group.
To sum up, this is indeed an open problem. There is no best answer. Maybe in case 1, using backtracking gives the best answer while in case 2, simulated annealing is the best. Just calculate the approximate answer is enough and there are so many ways to achive this goal. All in all, the really best approach is to write as many AAs as you can, and then compare these results and output the best one.