0

我创建了一个由旅行商问题衍生而来的谜题，我称之为 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 -> B 时为 timeA，当遍历 B -> A 时为 timeB）。这应该是构建图形数据结构所需的全部内容。JSON 对象中的所有其他属性都用于视觉目的。

如果您想熟悉这个谜题，可以通过http://www.TracePerfect.com/上的 Flash 客户端播放它

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

感谢您阅读这篇冗长的帖子。我期待听到您对此的看法。

4

3 回答 3

4

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

于 2011-02-18T19:49:29.950 回答
0

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

通过这种方式，您可以获得应重复求解的行数。

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

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

带有这种启发式的简单递归蛮力求解器可能是开始的好方法。

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

于 2011-02-18T08:11:49.497 回答
0

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

于 2011-02-18T10:25:07.710 回答