algorithm - Solving a TSP-related task -

i have problem similar basic tsp not quite same.

i have starting position player character, , has pick n objects in shortest time possible. doesn't need return original position , order in picks objects not matter.

in other words, problem find minimum-weight (distance) hamiltonian path given (fixed) start vertex.

what have currently, algorithm this:

best_total_weight_so_far = inf  foreach possible end vertex:     add vertex 0-weight edges start , end vertices     current_solution = solve tsp graph     remove 0 vertex      total_weight = weight (current_solution)     if total_weight < best_total_weight_so_far         best_solution = current_solution         best_total_weight_so_far = total_weight 

however algorithm seems time-consuming, since has solve tsp n-1 times. there better approach solving original problem?

it rather minor variation of tsp , np-hard. heuristic algorithm (and shouldn't try better heuristic game imho) tsp should modifiable situation. nearest neighbor wouldn't bad -- in fact situation better when used in tsp since in nearest neighbor return edge worst. perhaps can use nn + 2-opt eliminate edge crossings.

on edit: problem can reduced tsp problem directed graphs. double of existing edges each replaced pair of arrows. costs arrows existing cost corresponding edges except arrows go start node. make edges cost 0 (no cost in returning @ end of day). if have code solves tsp directed graphs use in case well.