np-hard

0热度

1回答

所以我发现一个问题，旅行者可以在图形中行进一定距离，所有双向边具有一定的长度（距离）。假设在旅行某个边缘（任一方向）时，您可以获得一些金钱/礼物（这是针对所有边缘的问题），因此您必须找到您可以在可以旅行的给定距离上收集的最高金额。基本问题是如何找到给定距离的所有可能路径（图中可能有循环），并在找到所有可能的路径后，收集最大费用的路径就是答案。注意：你想出的任何可能的路径都不应该有一个循环（直线路径

3热度

1回答

你称之为列表的属性，它描述了它包含重复的程度？

我有一个选择清单的笛卡尔乘积，使得重复元素的数量是最高的函数： import Data.List (nub) f :: Eq a => [[a]] -> [[a]] f xss = filter ((==) minLength . length . nub) cartProd where minLength = minimum (map (length . nub) ca

0热度

1回答

我们可以通过仅使用一辆车来优化VRPTW中的行驶距离吗？

是否可以仅使用一辆车来优化VRPTW。由于单辆车辆必须按顾客的预约时间顺序前往顾客。

1热度

1回答

Rails供应商资产模板

我想知道是否有一个很好的解决方案可以将供应商html模板放入Rails资产管道。现在我做它通过将两个模板，我需要在/public 我用鲍尔安装angular-ui-bootstrap工作和application.rb加入config.assets.path后，我可能需要从application.js中的JavaScript罚款。你如何做相同的角模块需要的HTML模板？ JS在/src，模板在/t

2热度

1回答

NP完整吗？

决策问题：对于给定的图G和数字“a”，“b”，需要回答是否存在具有至少'b'大小的累积邻域的一组'a'顶点。我们如何证明这个问题是NPC？

1热度

1回答

通过所有其他节点（NP-Hard？）从节点A到B的最短路径

我的问题：找到从节点A到节点B的最短路径，该节点通过未加权的直接图形的所有其他节点。我知道存在这样一条路。我相信这是NP-Hard，但我无法解释它。我的教授喜欢让算法在O(|V| + |E|)的运行时间上执行，其中V是一组节点和E边缘集合。看起来它与this problem类似，但Graph的属性不同，它有什么区别吗？

-1热度

2回答

获取致命异常

喜而点击按钮我的申请与下面的错误消息:: W/dalvikvm(15165): threadid=1: thread exiting with uncaught exception (group=0x40018578) E/AndroidRuntime(15165): FATAL EXCEPTION: main E/AndroidRuntime(15165): java.lang.NullPo

-1热度

1回答

如何证明E_tm = {M | M是一个图灵机，它不接受}是NP-Hard？

我不知道如何开始。我的想法是从一些NP完全问题提供多时间减少。 E_tm 我不明白的是，知道E_tm不可判定，但NP-Hard类是可判定的。

0热度

2回答

如果Y在多项式时间内可以归约为X，那么X至少和Y一样硬呢？

我很难理解两类问题的复杂性之间的关系，比如NP-hard和NP-complete问题。答案在https://stackoverflow.com/a/1857342/状态：直观地说，这些都是至少一样努力的NP完全问题的问题。请注意，NP-hard问题不必在NP和中，它们不必是决策问题。这里的确切定义是：问题X是NP难的，如果有一个NP完全问题Y，这样Y还原为X在多项式时间。如果问题Y可以在多

1热度

1回答

DCOS集群资源分配是NP难

在这里，在DCOS文件中指出， “决定在何处运行的进程，以最好地利用群集资源被硬，NP-很难在-的事实。” 我不否认这听起来是对的，但是有证据吗？