机器学习成功地解决NP-难中的组合优化问题吗？基于机器学习的调度问题探讨

Question

国际象棋已经完成了。我猜想Alpha GO也是Exp完成的。如果我错了，请纠正我。现在，深度强化学习已经成功地解决了这一问题。其他更实际的问题，如调度、装箱和路由呢？特别是，使用ML技术调度应用程序的技术现状如何？我们应该从这个方向出发吗？

Answer 1

你不必为了得到一个困难的问题而完成任务。NP-完全已经够糟了.

密码假设(例如单向函数的存在)也是制造困难问题的好方法。

在这一领域进行了大量的研究，如学习布尔公式和有限自动机的密码限制 - DFA是不能在多项式时间内学习的PAC。

然而，这些负面结果与编写一个伟大的国际象棋程序有着重要的区别。负结果意味着对于给定的问题，没有任何算法能解决所有的实例(比如说，多项式时间)。这并不意味着在某些/大多数/所有情况下，你都不能更好地发挥人类的冠军。

请注意，这种复杂的观察是对技术的漠不关心。机器学习只是处理这些问题的另一种(有用的)方法。

在机器学习能力方面，可以发现机器学习中的NP-完全问题(SVM、神经网络、决策树)。这并不妨碍他们找到许多有用的模型。