algorithm - Solver for TSP-like Puzzle, perhaps in Javascript -

i have created puzzle derivative of travelling salesman problem, call trace perfect.

it undirected graph weighted edges. goal traverse every edge @ least once in direction using minimal weight (unlike classical tsp goal visit every vertex using minimal weight).

as final twist, edge assigned 2 weights, 1 each direction of traversal.

i create new puzzle instance everyday , publish through json interface.

now know tsp np-hard. puzzles typically have handful of edges , vertices. after need humanly solvable. brute force basic optimization might enough.

i develop (javascript?) code retrieves puzzle server, , solves algorithm in reasonable amount of time. additionally, may post solution server registered in leader board.

i have written basic brute force solver in java using back-end java model on server, code fat , runs out of heap-space quick, expected.

is javascript solver possible , feasible?

the json api simple. can find at: http://service.traceperfect.com/api/stov?pdate=20110218 pdate date puzzle in yyyymmdd format.

basically puzzle has many lines. each line has 2 vertices (a , b). each line has 2 weights (timea when traversing -> b, , timeb when traversing b -> a). , should need construct graph data structure. other properties in json objects visual purposes.

if want become familiar puzzle, can play through flash client @ http://www.traceperfect.com/

if interested in implementing solver themselves, post detail api submitting solution server, simple.

thank reading longish post. forward hear thoughts one.

if running out of heap space in java, solving wrong.

the standard way solve breadth-first search, , filter out duplicates. need 3 data structures. first graph. next queue named todo of "states" work have left do. , last hash maps possible "state" in pair (cost, last state).

in case "state" pair (current node, set of edges traversed).

assuming have data structures, here pseudocode full algorithm should solve problem efficiently.

foreach possible starting_point:   new_state = state(starting_point, {no edges visited})   todo.add(new_state)   seen[new_state] = (0, null)  while todo.workleft():   this_state = todo.get()   (cost, edges) = seen[this_state]   foreach directed_edge in graph.directededges(this_state.current_node()):     new_cost = cost + directed_edge.cost()     new_visited = directed_edge.to()     new_edges = edges + directed_edge.edge()     new_state = state(new_visited, new_edges)     if not exists seen[new_state] or new_cost < seen[new_state][0]:       seen[new_state] = (new_cost, this_state)       queue.add(new_state)  best_cost = infinity full_edges = {all possible edges} best_state foreach possible location:   end_state = (location, full_edges)   (cost, last_move) = seen[end_state]   if cost < best_cost:     best_state = end_state     best_cost = cost  # trace final answer. path_in_reverse = [] current_state = best_state while current_state[1] not empty:     previous_state = seen[current_state][1]     path_in_reverse.push(edge previous_state[0] current_state[0])     current_state = previous_state 

and reverse(path_in_reverse) gives optimal path.

note hash seen critical. prevents getting endless loops.

looking @ today's puzzle, algorithm have maximum of million or states need figure out. (there 2**16 possible sets of edges, , 14 possible nodes at.) fit ram. of nodes have 2 edges connected. advise collapsing those. reduce 4 nodes , 6 edges, upper limit of 256 states. (not possible, , note multiple edges connect 2 nodes.) should able run little use of memory.