我有一组主机和一组任务。
每个主机都有 cpu、mem 和 task 容量，每个 task 都有 cpu、mem 要求。
每个主机都属于一个延迟等级，并且可以与具有一定延迟值的其他主机进行通信。
每个任务可能需要以等于或小于某个值的延迟与另一个任务通信。
我的问题输入示例如下图所示。
其中任务 t1 需要分别以等于或小于 3、3 和 5 的延迟与任务 t2、t3 和 t4 通信，并且主机 h1 属于延迟等级 3，并以 2、5 和 2 的延迟与 h2、h3 和 h4 通信3分别。
我正在考虑使用 Hungarian/munkres 算法来解决这个问题，但是如何正确设置成本函数？有没有更好的分配算法来解决这个问题？
谢谢。
问问题
478 次
2 回答
1
正如你应该知道的，这个问题是 QAP（二次分配问题）的一个案例，这是 NP 完全的，这意味着：不存在解决它的最佳算法，至少在多项式时间内。更多细节在这里
虽然有几种方法可以处理，但我尝试了一些来自 AI 的简单方法，如遗传算法 (GA) 和 ACO，效果很好。我会推荐你GA。
于 2014-06-24T11:42:26.700 回答
1
Munkres 有一个 Python 包：http: //software.clapper.org/munkres/。你可以参考他们的实现：https ://github.com/bmc/munkres/blob/master/munkres.py
于 2014-06-24T10:50:55.633 回答