1

我有一个我正在尝试使用 Java 完成的任务，但我对如何设置/下图的节点是什么感到困惑。基本上，它是笔式绘图仪问题，或者更常见的旅行商问题。我的以下输入是：

Line between 4 1 and 4 4    
Line between 4 4 and 4 7    
Line between 2 6 and 4 4   
Line between 4 4 and 6 2  
Line between 6 6 and 4 4   
Line between 2 2 and 4 4

我的输出结果如下：

<n> nodes explored
cost = 24.61
Move from 0 0 to 2 2
Draw from 2 2 to 4 4
Draw from 4 4 to 6 6
Move from 6 6 to 4 7
Draw from 4 7 to 4 4
Draw from 4 4 to 4 1
Move from 4 1 to 6 2
Draw from 6 2 to 4 4
Draw from 4 4 to 2 6

假设这张纸的左下角是你的起点（0,0），它的坐标上升，每个坐标都是一个节点，我将如何确定何时移动和画一条线。我知道我应该使用带有 A* 的无向图，但我仍然对哪些是节点（顶点）以及如何确定何时移动以及何时绘制线条感到很困惑，有人能给我一些建议吗？

编辑：请注意，指的是在整个搜索过程中探索的节点数量/数量。

4

2 回答 2

1

要使用 A*，您首先需要一个可接受的启发式函数。[解释它是什么附加在这个答案的末尾]。

问题作为 A 的图表：*
将 G=(V,E) 定义为您的图表，这样：
V={all possible drawings prefixes}[即每个可能的平局的所有可能的“快照”]。请注意，您不应该将此图保存在内存中，而是动态创建它，next()稍后将对此进行解释。[请注意，实际上，对于每个状态，您实际上只需要存储（1）当前笔在哪里（2）已经绘制了哪些线]
E={all possible changes from one 'snap shot' to another}
您还需要w:E->R[权重函数]，这将是简单的：w(point1,point2)=euclidian_distance(point1,point2)

您还应该定义next:V->P(V)：next(v)={all snap shots you can get from v, using exactly one move/draw
最后，您还应该定义F：所有“结束”状态。F={all the prefixes which all the lines are drawn}

如何运行 A*：
从你的笔在 (0,0) 处的快照开始，不画线[这是初始状态]，一直持续到找到最终状态之一。当你这样做时，如果你的启发式是有效的，那么你肯定得到了优化的解决方案，因为 A* 是可接受和优化的

(*)允许的启发式函数：
让h*(v)=real distance to target从顶点 v.
启发式函数 h:V->R 是允许的，如果h(v)<=h*(v)对于 V 中的每个 v

你真正的挑战
TSP 的困难部分是找到一个可接受的h. 这很难，因为你不知道最短路径是什么，而且如果启发式函数不可接受，则不能保证找到的解决方案会被优化。

建议：
您可能想使用一些任何时间算法，当我做了类似的事情时，[用多个代理解决了 TSP] 我也使用了 A*，但是从一个无效的启发式开始，并迭代地减少它，所以如果我有有足够的时间，我找到了最佳解决方案，如果没有 - 我返回了我能找到的最佳解决方案。

于 2011-09-13T07:04:56.640 回答
0

由于您要解决的问题是NP Hard，因此没有有效的方法来解决旅行商问题。您要做的第一件事是将所有顶点对（从和到）存储在 ArrayList 中，并根据需要使用它们。

什么时候应该移动：当
你在一个点并且你的 ArrayList 中没有起始节点时，你必须选择数组中的下一个元素并移动到那里。

什么时候应该平局：
平局可能发生在两种情况下。在您移动到某个点后，将进行平局。当您的线段终点作为起点存在于 ArrayList 中时，也会发生平局。

每次绘制后，您应该从 ArrayList 中删除该特定线段。当您的存储桶中没有其他任何东西时，您将停止您的程序。

于 2011-09-13T05:51:13.557 回答