np - VoidCC

np

10熱度

2回答

我見過幾個地方只是簡單地說明它已知P是NP和co-NP的交集的子集。證明P是NP的一個子集的證明不難找到。因此，爲了表明它是交集的一個子集，剩下要做的就是顯示P是共NP的一個子集。什麼可能證明這是什麼樣的？非常感謝！

0熱度

1回答

根據wiki將需要（N-1）！計算與N個城市的遊覽。我發現了一個更好的方法來做到這一點，但我無法用數學來計算我改進了多少。我可以告訴你，在我的家用電腦上，我能夠在不到1個小時內解決20個城市的地圖。 20！ = 2.43290200e + 18。這是我做的：當使用brout算法搜索N個城市的路線時（讓我們給他們一個名字：City（1），City（2），City（3）... City（N））（1

0熱度

1回答

優化平面中任意形狀的佈局

我想創建一個算法，可以將一組對象並在給定區域中組織它們，以便限制所有形狀的邊框被優化（通過使用的區域，或者通過最大化沿一個維度的跨度等）。所有的形狀都是封閉的和有界的。這樣做的目的是儘量減少使用激光切割機造成的材料浪費。這些形狀在CAD中生成並可以讀入該算法。然後該算法將爲工作區域（有效的激光切割區域）以及任意兩個物體之間的最小間距進行自變量，然後嘗試在指定尺寸範圍內組織物體，同時儘量減少區域使

1熱度

1回答

將子集求和的近似算法轉換爲php代碼

Cross-posted in MathExchange to elicit more responses。 ============================================== ================================== 我在寫我原來的問題在StackOverflow上，當我意識到它被問到before。原來我有什麼被稱爲一個子集和問題，讓我去w

2熱度

2回答

這是NP優化嗎？

在完整的Ñ -partite無向圖中，每個三方組具有Ñ頂點。我的問題是要在圖表中找到最小重量的n -clique。我想知道這個問題是否可以在Poly-n時間內解決。更多細節的術語：完整的k分圖：其中頂點相鄰的曲線圖，當且僅當它們屬於不同的部集（wikipedia）。圖中有k個分組集。在我的問題中，k = n。 Clique：圖G中的集團是G的完整子圖;也就是說，它是頂點的子集S，使得S中的每兩

1熱度

1回答

帶扭曲的多個TSP

幾個星期前，我遇到了一個問題，我幾乎打破了旅行商問題的變化。曲折是：有多個銷售員。城市列表正在動態增加（如在現場輸入）每個城市只在有限的時間內完全盈利，因爲在一段時間之後城市將返回較少的獎勵而且總時間限制顯然，這個問題是NP。我想知道是否有任何可以修改以適應此問題的良好TSP近似值？

3熱度

1回答

爲什麼星期六不補充NP？

我知道您無法提供驗證證書。但是，我只是在想，爲什麼我們不能給NDTM決定SAT的輸入，然後改變答案呢？缺陷在哪裏？

1熱度

2回答

旅行推銷員 - 近似在線軟件？

你們誰都知道解決方案能夠爲旅行商問題產生一個平庸的解決方案。我有3人打算訪問31個目的地......我不知道如何解決這個問題？感謝所有 - 馬克西姆

1熱度

1回答

爲什麼我們不能擁有FPTAS的強NP完整問題

我知道我們可以將FPTAS應用於像0-1揹包這樣的弱NP問題。但是爲什麼我們不能將相同的主體應用於像bin裝箱這樣的強NP問題。我還查看了關於相同但很少理解的wiki頁面。

2熱度

2回答

這是證明某件事情是否完整的正確理解？

據我所知有兩個步驟來證明一個問題是NP完全性：給出了一種算法，可以驗證在多項式時間內解決問題。也就是說，一種算法，其輸入是提出的問題解決方案，其輸出是「是」還是「否」，取決於輸入是否是問題的有效解決方案。證明這個問題是NP難 - 比如，假設你有一個可以在一個步驟計算其它已知的NP完全問題的神諭。使用它，編寫一個在多項式時間內解決這個問題的算法。例如，假設我們要證明下面的問題是NP完全性：給