类似于 TSP 的谜题的求解器，可能是用 Javascript 编写的

Question

我创建了一个难题，它是旅行商问题的衍生问题，我称之为“Trace Perfect”。

它本质上是一个带有加权边的无向图。目标是使用最小权重在任何方向上至少遍历每条边一次（与经典 TSP 不同，传统 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 的 Flash 客户端来玩它/

如果有人有兴趣自己实现一个求解器，那么我将发布有关将解决方案提交到服务器的 API 的详细信息，这也非常简单。

感谢您阅读这篇较长的文章。我期待听到您对此的想法。

Answer 1

对于图表的大部分部分，您可以应用 http://en.wikipedia.org/wiki/Seven_Bridges_of_K %C3%B6nigsberg。

通过这种方式，您可以获得需要重复解决的行数。

一开始，您不应该从具有短顶点的节点开始，您应该在这些节点上移动两次。
如果我总结一下：

• 从具有奇数条边的节点开始。
• 不要多次穿越位于偶数节点上的线路。
• 使用最短路径从一个奇数节点移动到另一个奇数节点。

简单的递归强力求解器以及这种启发式可能是一个很好的开始方式。

或者另一种方式。
尝试找到最短的顶点，如果将它们从图重新挖掘中删除，图将只有两个奇数节点，并且将被视为可解为 Koningsberg 桥。解决方案是在这个简化的图上不拿起铅笔来求解图，一旦你点击“删除”边缘的节点，你就可以前后移动。

Answer 2

在你的java后端，你也许可以使用这个TSP代码（正在进行中），它​​使用Drools Planner（开源，java）。

Answer 3

如果您在 Java 中耗尽了堆空间，那么您的解决方法是错误的。

解决此类问题的标准方法是进行广度优先搜索，并过滤掉重复项。为此，您需要三个数据结构。第一个是你的图表。接下来是一个名为“状态”的待办事项队列，用于表示您尚未完成的工作。最后一个是一个哈希，它将您所处的可能“状态”映射到该对（成本，最后状态）。

在这种情况下，“状态”是对（当前节点，已遍历的边集）。

假设您拥有这些数据结构，这里是完整算法的伪代码，应该相当有效地解决这个问题。

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 个可能的节点。）这很可能适合 RAM。但大多数节点只有 2 条边相连。我强烈建议折叠这些。这会将您减少到 4 个节点和 6 个边，上限为 256 个状态。 （并非所有都是可能的，请注意，现在有多个边连接两个节点。）这应该能够运行得非常快，并且几乎不使用内存。