Given an undirected graph with n nodes, I need to find the shortest cycle of involving exactly n/2 vertices (i.e. keeping the distance traveled by the cycle to a minimum). Some nodes cannot directly connect; they're in specific areas and I can only travel from one area to another, not within one area.
I'm just asking in general here, what kind of techniques can I use to get the best (shortest) possible cycle of n/2 nodes? So far I've written a basic substitution optimizer and just a greedy Depth First Search. I'm wondering what would be the best approach for me to start on now?