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

Question

Я создал головоломку, которая является производной от задачи коммивояжера, которую я называю Trace Perfect.

По сути, это неориентированный граф со взвешенными ребрами. Цель состоит в том, чтобы пересечь каждое ребро хотя бы один раз в любом направлении, используя минимальный вес (в отличие от классического TSP, где целью является посещение каждой вершины, используя минимальный вес).

В качестве окончательного поворота ребру присваиваются два веса, по одному для каждого направления обхода.

Я создаю новый экземпляр головоломки каждый день и публикую его через интерфейс JSON.

Теперь я знаю, что TSP NP-сложен. Но у моих головоломок, как правило, есть только кучка ребер и вершин. Ведь они должны быть по-человечески разрешимы. Так что грубой силы с базовой оптимизацией может быть достаточно.

Я хотел бы разработать некоторый (Javascript?) Код, который получает загадку с сервера и решает с помощью алгоритма в разумные сроки. Кроме того, он может даже отправить решение на сервер для регистрации в таблице лидеров.

Я написал базовый решатель перебора для него на Java, используя мою внутреннюю модель Java на сервере, но код слишком толстый и быстро исчерпывает пространство кучи, как и ожидалось.

Возможен ли и возможен ли решатель Javascript?

JSON API прост. Вы можете найти его по адресу: http://service.traceperfect.com/api/stov?pdate=20110218, где pdate - дата головоломки в формате yyyyMMdd.

В основном у головоломки много строк. Каждая линия имеет две вершины (A и B). Каждая строка имеет два веса (время A для обхода A -> B и время B для обхода B -> A). И это должно быть все, что вам нужно для построения структуры данных графа. Все остальные свойства в объектах JSON предназначены для визуальных целей.

Если вы хотите познакомиться с головоломкой, вы можете играть в нее через флэш-клиент по номеру http://www.TracePerfect.com/

Если кто-то заинтересован в реализации решателя для себя, я опубликую подробности об API для отправки решения на сервер, что также очень просто.

Спасибо, что прочитали этот длинный пост. Я с нетерпением жду ваших мыслей об этом.

Answer 1

Если вам не хватает места в куче в 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 состояний. (Не все возможно, и обратите внимание, что несколько ребер теперь соединяют два узла.) Это должно быть в состоянии работать очень быстро с небольшим использованием памяти.

Answer 2

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

Answer 3

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

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

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

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

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

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