我有两个独立的问题，围绕图形旋转，并确定一种方法，找到从s到t的简单路径，通过尽可能多的蓝色顶点。另外，我必须确定NP-Hard这两个问题中的哪一个。
第一个问题中的图是一个无向图，其中一些顶点是蓝色，而另一个问题中的图是一个有向无环图，其中一些顶点是蓝色。
我有一个暗示，有向无环图的第二个问题，可以使用动态编程解决，但我很难掌握如何将问题建模为动态编程问题，因为我没有看到重叠子问题。也许有人可以证明或澄清如何做到这一点？
第一个问题应该是NPHard问题，可以简化为汉密尔顿路径，我可以部分地看到这是正确的，但随后问题出现了，有向无环图的第二个问题是否也可以简化为哈密顿量路径，也使它成为NPHard？为什么或者为什么不？
NP完全性的基本不对称性是NP问题总是可以简化为NP完全或硬问题，但NP完全问题不能总是简化为NP问题。
你是对的，第一个问题是NP难，而且原因与汉密尔顿路径有关，但减少则是另一回事。鉴于无向图上的哈密顿路径问题，您是否总能用第一个问题表达它？
至于第二个，假装你不只是听到“拓扑排序”一词在微风中漂浮......