np-complete

1熱度

1回答

我有以下NP完全問題：給定一組N個N字段中的一組位置，以及一組m個節點，還有一個節點的連通圖（即一個無向圖，其邊緣代表每對與每個節點接觸的節點）以及接觸範圍R（與N×N字段具有相同的長度單位），在關於連接圖的字段中找到節點的位置（即放置節點，接觸的任何對接近比R和eny對不接觸比R更遠），或者表明這種放置不存在。我們是否有任何知名的NP完全問題，這個問題可以簡化爲？（也可以考慮優化版本的問題

4熱度

3回答

NP完全與NP-硬

如果問題已知的是NP完全可以減少到另一個問題乙在多項式時間內，則B是（A）NP完全（B）NP-硬沒有給出關於問題B是否在NP中的問題。我很困惑，因爲在Hopcraft和Ullman的書中，如果一個NP完全問題P1在多項式時間內可以歸結爲問題P2，那麼P2就是NP-完全的。但它也需要一個問題是NP-Complete，它應該屬於NP類。夥計們幫助理解這個概念。

0熱度

1回答

串來串糾正問題的NP完全性證明

我有這樣的任務，證明這個問題：有限字母£，兩個字符串X，Y€ £*，和一個正整數K.是有一種方法可以從字符串x中得到字符串y ，其方式爲K 或更少操作單個符號刪除或相鄰符號交換？是np完整的。我已經想出了我必須從集合覆蓋問題的決策版本進行轉換，但我不知道如何做到這一點。任何幫助，將不勝感激。

1熱度

1回答

從頂點覆蓋減少來證明NP完全

我們定義ROMAN-SUBSET如下面的問題： INPUT：向圖G =（V，E）和一個正整數k OUTPUT：如果有一個V的子集R，使得| R |使得G中的每個定向電路包括來自R的至少一個頂點，那麼輸出應該是「真」，否則它應該是「假」。假設頂點覆蓋（VC）問題是NP完全的，我必須證明ROMAN-SUBSET也是NP-完全的。根據我的理解，這意味着接受VC輸入，修改它，然後顯示將它插入ROMA

4熱度

1回答

利潤最大化算法：解決方法/方法？（高級NP-Complete）

這個很難，所有的幫助真的很感謝！我知道這是一個NP完全，因此不能在多項式時間內解決，但尋找分析的幫助下，什麼類型的NP完全問題它減少了，它提醒你類似的問題，等等。故事如下。我擁有與n卡車的冰淇淋卡車業務。有米停止在哪裏我交付。每個位置m i已有p i人在等我。買完冰淇淋後，大家都離開了。 p i隨着時間的推移，越來越多的人排隊購買冰淇淋。我怎樣才能找出下一輛卡車的位置，以便在任何特定的日子裏

0熱度

1回答

證明NP完全

嗨，大家好，我有一個問題。我想知道如果有人知道如何證明它。下面是問題：子集和問題顯示爲NP完全。輸入是一系列正數w1，...，wn，W，其中W是目標權重。問題是要確定是否有一組權重F⊆{1，...，n}，使得某些權重之和等於目標權重（即w1 + ... + wi = W）設定受限子集總和問題如子集總和一樣，但是額外要求目標權重小於所有權重總和的一半。（如果失敗，則必須立即拒絕輸入。）顯示受

5熱度

2回答

最小加法鏈求冪

我知道它已被證明是NP-complete，沒關係。我目前正在用分支和邊界來解決這個問題，我在乘法的次數上設置了初始上限，它需要正常的二進制平方/乘法算法，並且它給出了正確的答案，但是我對運行不滿意時間（對於200左右的數字可能需要幾秒鐘）。這是一個NP完全問題，我不期待什麼壯觀;但通常有一些技巧會讓實際時間受到控制。有沒有更快的方法來做到這一點在實踐中？如果是這樣，他們是什麼？

3熱度

4回答

所有的NP問題都是NP完成的嗎？

的NP-完整的定義是的問題是NP完全如果它屬於類NP 所有NP的其他問題多項式的變換，那麼，如果NP中的所有其他問題轉化爲NP完全問題，那麼這是否也意味着所有NP問題都是NP完全問題呢？如果兩者相同，對它們進行分類有什麼意義？換句話說，如果我們有一個NP問題，那麼通過（2）這個問題可以轉化爲一個NP完全問題。因此，NP問題現在是NP完全的，NP = NP完全。兩個類都是等價的。只是試圖

-1熱度

2回答

在PHP中編寫課程時間表系統最有效的方法是什麼？

問題：給定一套強制性和選擇性課程，每個課程只在特定時間段（有7個時間段）可用，生成所有可能的時間表。實施例：對於強制性課程： MAT101 - 1，2，5 HIS102 - 2，4，6 ENG105 - 3，6，7 可選課程： LIT103 - 3，4，6 CHE101 - 7,1，2 BIO101 - 5，4,7 MAT201 - 6,5，1 ANT201 - 1 （不是每個選修課程必須包

7熱度

1回答

一般NP-hard，但在平面圖中有多項式時間解的問題列表？

我遇到了很多問題，可以制定爲圖問題。它通常是NP-hard，但有時圖形可以證明是平面的。因此，我有興趣學習這些問題和算法。所以據我所知：最大切平面圖形四着色的平面圖最大獨立集在立方平面圖希望有人可以完成這個列表。