假设我有一个边相对较少的有向图（例如N=1000个节点，M=3000个边）。我需要枚举从1到N的节点，以便尽可能少的边从编号较低的节点指向编号较高的节点。
例如，这是一个很好的优势：
44 o----------->o 12
这个很糟糕：
3 o------------> 117
我该如何处理这个问题？我想这类任务已有算法，但不知道该搜索什么。此外，我不需要找到绝对最好的解决方案，只要在实践中足够接近即可。例如，如果全局最佳是5个坏边，那么对于我的目的来说，具有10个坏边的解决方案也足够好了（但200不是）。
特别是因为你只想要一个好的解决方案，而不一定是最好的，所以听起来马尔可夫链蒙特卡罗方法应该适合你。
-
从节点的随机枚举E_0开始，计算你的分数S（E_0）
-
对于许多步骤
- 每次步骤j，通过改变两个节点的数量，从当前E_j中获得新的枚举候选E*
- 计算分数S（E*）。（不要完全计算它是新的，而是根据S（E_j），只考虑您更改的两个节点和它们所涉及的边）
- 如果S（E*）<=S（E_j）
- 如果S（E*）>S（E_j）仍将E_j改为E_*概率，f.e.（S（e_j）/S（e_*））^k，其中k影响你强烈希望你的算法惩罚糟糕的选择
在运行此算法时，请跟踪获得的最低分数和实现该分数的枚举。
你必须有来自循环的边，所以你首先想把你的问题分解成强连接的组件。
请注意，强连接组件的图是非循环的，这意味着来自不同组件的两个节点很容易进行比较。
然后，您可能可以尝试搜索循环，并在每个循环中"标记坏"一条边，这将把您的组件转换为DAG本身（您可以尝试删除许多循环中常见的边，这应该会有所帮助）。
我不得不承认，我不知道在边缘不好的情况下会如何表现，但我认为这是一个很好的方法。