Решатель для TSP-подобной головоломки, возможно, на Javascript

Если вам не хватает места в куче в Java, значит, вы решаете это неправильно.

Стандартный способ решить что-то подобное — выполнить поиск в ширину и отфильтровать дубликаты. Для этого вам нужны три структуры данных. Первый — это ваш график. Следующей является очередь с именем todo из «состояний» для работы, которую вам осталось сделать. И последнее — это хэш, который сопоставляет возможное «состояние», в котором вы находитесь, с парой (стоимость, последнее состояние).

В этом случае «состояние» — это пара (текущий узел, множество уже пройденных ребер).

Предполагая, что у вас есть эти структуры данных, вот псевдокод для полного алгоритма, который должен решить эту проблему достаточно эффективно.

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

# Now trace back the final answer.
path_in_reverse = []
current_state = best_state
while current_state[1] is not empty:
    previous_state = seen[current_state][1]
    path_in_reverse.push(edge from previous_state[0] to current_state[0])
    current_state = previous_state

И теперь reverse(path_in_reverse) дает вам оптимальный путь.

Обратите внимание, что хэш seen является критическим. Это то, что мешает вам попасть в бесконечные циклы.

Глядя на сегодняшнюю головоломку, этот алгоритм будет иметь максимум около миллиона состояний, которые вам нужно выяснить. (Есть 2 ** 16 возможных наборов ребер и 14 возможных узлов, в которых вы можете находиться.) Это, вероятно, поместится в ОЗУ. Но большинство ваших узлов имеют только 2 соединенных ребра. Я настоятельно рекомендую свернуть их. Это уменьшит вас до 4 узлов и 6 ребер, для верхнего предела 256 состояний. (Не все возможно, и обратите внимание, что несколько ребер теперь соединяют два узла.) Это должно работать очень быстро с небольшим использованием памяти.

Для большинства частей графика можно применить http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg.

Таким образом, вы можете получить количество строк, которые вы должны повторить, чтобы решить.

В начале вы не должны начинать с узлов, которые имеют короткие вершины, по которым вы должны пройти два раза. Если резюмировать:

• начать с узла с нечетным числом ребер.
• не перемещайтесь по линиям, которые находятся на четном узле, более одного раза.
• использовать кратчайший путь для перемещения от одного нечетного узла к другому.

Простой рекурсивный решатель грубой силы с этой эвристикой может быть хорошим началом.

Или другим способом.
Попробуйте найти кратчайшие вершины, которые, если вы удалите их из графа, напоминающего граф, будут иметь только две вершины с нечетными номерами и будут считаться разрешимыми как Конингсбергский мост. Решение состоит в том, чтобы решить граф, не поднимая карандаш на этом уменьшенном графе, и как только вы нажмете узел с «удаленным» ребром, вы просто вернетесь назад и вперед.

На вашем сервере Java вы можете использовать этот код TSP (в разработке), который использует Drools Planner (открытый исходный код, java).