Optimierungsproblem einstellen - ist es np-vollständig?

10

Set ist gegeben. Für jedes Element haben wir das Gewicht und kosten . Das Ziel besteht darin, die Teilmenge der Größe , die die folgende Zielfunktion maximiert: .S={e1,,en}eiwi>0ci>0Mk

eiMwi+eiMwicieiMci

Ist das Problem NP-schwer?

Da die Zielfunktion seltsam erscheint, ist es hilfreich, eine Anwendung der Zielfunktion zu erklären.

Angenommen, wir haben n Artikel bis und es gibt Kopien jedes Objekts in unserem Inventar. Wir haben einige Kunden, die sich für diese Objekte im Verhältnis zu ihrem Gewicht , was bedeutet, dass das Objekt mit dem größeren beliebter ist. Wir haben ein Online-Verkaufssystem und müssen die Anfragen unserer Kunden korrekt beantworten. Wir können Objekte nicht an ihren Formen erkennen (sie sehen alle gleich aus!). Aber wir haben einige Klassifikatoren, um sie zu finden. Jeder Klassifikator kann zum Erkennen von Kopien eines Objekts verwendet werden. Wir möchten k klassifier ausführen, um die Zufriedenheit unserer Kunden zu maximieren.e1encieiwiwi

PS: Es kann nützlich sein, über den Fall nachzudenken, dass für alle ; Ich bin mir jedoch nicht sicher. [ Ich habe mich geirrt! Es ist in P durch diese Annahme ]wici=pin

Nasooh
quelle
Der richtige Begriff ist kleiner oder gleich dem größten Gewicht eines Elements, das nicht in M ​​enthalten ist. Wenn Sie also ein Element mit einem großen Gewicht haben, ist es besser, es in M ​​zu setzen, als es zu verschwenden. M sollte also aus den Elementen mit den k größten Gewichten bestehen. Recht?
Zotachidil
Es ist nicht richtig, weil auch die Kosten wichtig sind. Betrachten Sie folgendes Beispiel:
Nasooh
w1 = 50, c1 = 80 - w2 = 40, c2 = 15 - w3 = 10, c3 = 5. Für k gleich 1 ist die Wahl von e2 vorteilhafter als e1.
Nasooh
Du hast recht. Hmm ...
Zotachidil
2
Vielen Dank, dass Sie versucht haben, die Motivation zu erklären. Leider ist mir der Zusammenhang zwischen Ihrer Erklärung und der Zielfunktion in der Frage noch völlig unklar, aber ich denke, ich muss mit der aktuellen Erklärung zufrieden sein, um die Frage in einem angemessenen Umfang zu halten.
Tsuyoshi Ito

Antworten:

2

Die folgende Antwort zeigt, dass ein Sonderfall des Problems in Polynomzeit lösbar ist. Dies beantwortet die Frage in der Post nicht vollständig, kann aber einen Einblick geben, was für einen NP-Härtenachweis erforderlich sein könnte, und kann zusätzliches Interesse an der Post hervorrufen ...

Überwachung. Das Problem in der Post hat einen Algorithmus, der in jedem Fall, in dem jedes eine ganze Zahl ist, im in und . n D = i c icinD=ici

Beweisskizze. Korrigieren Sie alle Eingaben wobei und (WLOG) . Umformulierung des Problems etwas, das Ziel zu finden der Größe maximiert .w , c R n + S = { 1 , 2 , , n } M S K i M w i c i(S,w,c,K)w,cR+nS={1,2,,n}MSKiMwiciiMciiMwi

Betrachten Sie das folgende dynamische Programm. Für alle ganzen Zahlen mit , und , definieren Die gewünschte Lösung ist .(d1,d2,k,m)0d1d2D0kKkmnmax d ϕ(d,d,K,n)

ϕ(d1,d2,k,m)=max{iMwi(ci/d11) : M[m],|M|=k,iMci=d2}.
maxdϕ(d,d,K,n)

Wenn wir die möglichen Lösungen für in diejenigen die enthalten, und diejenigen, die dies nicht tun, erhalten wir die Wiederholung Wir verlassen die Grenzfälle als Übung.m φ ( d 1 , d 2 , k , m ) = max { φ ( d 1 , d 2 - c m , k - 1 , m - 1 ) + w m ( c m / d 1 - 1 ) ϕ (ϕ(d1,d2,k,m)m

ϕ(d1,d2,k,m)=max{ϕ(d1,d2cm,k1,m1)+wm(cm/d11)ϕ(d1,d2,k,m1).

Die Anzahl der Teilprobleme ist , und für jedes kann die rechte Seite der Wiederholung in konstanter Zeit ausgewertet werden, so dass der Algorithmus in und im Zeitpolynom läuft . n D O(n2D2)nD  

Logische Folge. Wenn P = NP nicht ist, wird jede Verringerung, die die NP-Härte zeigt, auf Fälle reduziert, in denen in nicht polynomisch ist .nDn

Anmerkung. Sofern ich mich nicht irre, gibt es in der Post auch ein PTAS für das Problem, das auf der Rundung der und der dynamischen Programmierung basiert . Die Existenz eines PTAS hat jedoch keinen direkten Einfluss darauf, ob das Problem NP-schwer ist, wie in der Post gefragt.wi

Ich bin auch neugierig --- weiß jemand, ob der Sonderfall, wenn (für jedes ) einen hat? (BEARBEITEN: Laut Willard Zhans Kommentar scheint dies optimiert zu sein, indem , dass es die größten Elemente enthält.) i M kwi=ciiMk

Neal Young
quelle
1
Ist der Fall von dasselbe wie das Minimieren , das optimiert wird, wenn aus dem größten 's? ( i j M w i w j ) / ( i M w i ) M w iwi=ci(ijMwiwj)/(iMwi)Mwi
Willard Zhan
@ WilliamZhan, ja, das scheint richtig.
Neal Young
-6

Sie fragen nach der Maximierung einer Funktion ohne Einschränkungen?

Es ist wirklich einfach. Wenn M die größte Menge ist, ist es die beste Lösung. Keine Notwendigkeit, etwas zu berechnen.

Dieses Problem scheint dem Rucksackproblem ähnlich zu sein, das übrigens NP ist.

Guillermo.
quelle
3
Die Frage lautet: "Die Teilmenge M der Größe k."
Tsuyoshi Ito