np-hard

0熱度

2回答

我試圖推廣Paul Hankin在Maximizing the overall sum of K disjoint and contiguous subsets of size L among N positive numbers中提供的算法，使得解決方案不限於每個子集完全是大小L，目標不是最大化總體總和，而是返回可能的最大子集的集合。拼寫出詳細信息，X是一組N正實數： X={x[1],x[2]

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可以在多

0熱度

1回答

圖論，所有具有給定距離的路徑

所以我發現一個問題，旅行者可以在圖形中行進一定距離，所有雙向邊具有一定的長度（距離）。假設在旅行某個邊緣（任一方向）時，您可以獲得一些金錢/禮物（這是針對所有邊緣的問題），因此您必須找到您可以在可以旅行的給定距離上收集的最高金額。基本問題是如何找到給定距離的所有可能路徑（圖中可能有循環），並在找到所有可能的路徑後，收集最大費用的路徑就是答案。注意：你想出的任何可能的路徑都不應該有一個循環（直線路徑

1熱度

1回答

DCOS集羣資源分配是NP難

在這裏，在DCOS文件中指出，「決定在何處運行的進程，以最好地利用羣集資源被硬，NP-很難在-的事實。」我不否認這聽起來是對的，但是有證據嗎？

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。由於單輛車輛必須按顧客的預約時間順序前往顧客。

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的屬性不同，它有什麼區別嗎？

0熱度

1回答

超圖的頂點着色，不均勻性限制NP-hard？

是一個超圖的頂點着色，沒有統一性限制NP-hard？我看過顯示k-聯合超圖的頂點着色的論文是NP-hard。然而，我找不到任何明確說明在一般情況下（而不僅僅是k均勻）超圖的頂點着色是否是NP難的來源。

-1熱度

1回答

如何證明E_tm = {M | M是一個圖靈機，它不接受}是NP-Hard？

我不知道如何開始。我的想法是從一些NP完全問題提供多時間減少。 E_tm 我不明白的是，知道E_tm不可判定，但NP-Hard類是可判定的。