Find Best N Points From a Graph


I’ve given a task and wonder if there are any better solutions.

Inputs of task are:

  1. Distance of district pairs

  2. Population of pairs

Goal is:

  • Find n districts at which its population and districts x miles range districts’ population is max.

Extra information:

  • Unique district size is tens of hundreds.

As an example, if I pick up district A, population will be A‘s population plus other districts’ population which are less than x miles far away from it. Total population will be n districts at which population is calculated as I mentioned.

What I’ve tried:

  1. Brute Force
  2. Generic Algorithms

What I planning to do:

  1. A* Search

My question is, there may be any other solution (optimal if possible) instead of these one. i.e. sorting districts by their population, merging x miles nearest to them into one until I get n districts.

Any ideas?