2

奇怪的问题不是真正的代码而是逻辑，希望可以在这里发布，在这里

我有一个可以被认为是图表的数据结构。每个节点可以支持许多链接，但仅限于每个节点的值。所有链接都是双向的。每个环节都有成本。成本取决于节点之间的欧几里得差异，每个节点中两个参数的最小值。和一个全局修饰符。

我希望找到图表的最大成本。

想知道是否有一种聪明的方法可以找到这样的匹配，而不是通过蛮力进行......这很丑陋......而且我不确定如果不花费 700 万年的时间运行它，我什至会如何做到这一点。

澄清：

Global variable = T
many nodes N each have E,X,Y,L
L is the max number of links each node can have.
cost of link A,B = Sqrt(  min([a].e | [b].e)  ) x 
     ( 1 + Sqrt( sqrt(sqr([a].x-[b].x)+sqr([a].y-[b].y)))/75 + Sqrt(t)/10 )


total cost =sum all links.....and we wish to maximize this.

节点的平均值为 40-50 范围为 (20..600) 平均节点链接因子为 3 范围 0-10。

4

6 回答 6

2

为了让阅读本文的其他人完整起见，我建议重新审视您的图论算法：

  • 迪杰斯特拉
  • 一个明星
  • 贪婪的
  • 深度/广度优先
  • 甚至动态规划（在某些情况下）
  • 等等。等等。

那里的某个地方是您问题的正确解决方案。我建议先看看 Dijkstra。

我希望这可以帮助别人。

于 2009-06-14T22:03:01.113 回答
1

这相当于旅行商问题（因此是 NP 完全问题），因为如果您能有效地解决这个问题，您可以简单地通过将每个成本替换为其倒数来解决 TSP。

这意味着您无法完全解决。另一方面，这意味着你可以完全按照我所说的去做（用它的倒数替换每个成本），然后在这个问题上使用任何已知的 TSP 近似方法。

于 2009-06-14T22:42:39.693 回答
1

对我来说似乎是最大流量问题。

于 2009-06-14T22:45:41.747 回答
1

如果我正确理解了问题，则可能没有多项式解决方案。因此，我将实现以下算法：

  1. 通过 beng greedy找到一些解决方案。为此，您按成本对所有边进行排序，然后从最高的开始遍历它们，尽可能向图形添加边，并在节点不能接受更多边时跳过。
  2. 查看您的优势并尝试使用启发式方法更改它们以存档更高的成本。我想到的第一个：您循环遍历所有节点的 4 元组（A、B、C、D），如果您当前的图有边 AB、CD 但 AC、BD 会更好，那么您进行更改。
  3. 可选地与 6 元组或其他遗传算法相同（它们被称为这种方式，因为它们通过突变工作）。
于 2009-06-14T22:06:20.297 回答
0

是否有可能通过从任何给定的起点贪婪地选择下一个最昂贵的选项（省略到访问节点的跳转）并在访问所有节点后停止？如果你走到了死胡同，就回溯到上一个没有死胡同的地方，然后贪婪地选择。这将需要一些工作，可能需要像堆栈一样的东西来保持你的路径。我认为如果成本有序且非负数，这将非常有效。

于 2009-06-14T19:29:50.313 回答
0

使用遗传算法。它们旨在解决您所说的问题，快速降低时间复杂度。检查您选择的语言的 AI 库。

于 2009-06-14T19:34:00.053 回答