Optimierungsproblem einstellen - ist es np-vollständig?

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=\{e_1,\cdots,e_n\}$ $e_i$ $w_i>0$ $c_i>0$ $M$ $k$

\sum_{e_{i} \in M} w_{i} + \frac{\sum_{e_{i} \notin M} w_{i} c_{i}}{\sum_{e_{i} \notin M} c_{i}}

$\sum_{e_i\in M} w_i + \frac{\sum_{e_i\notin M} w_i c_i}{\sum_{e_i\notin M} c_i}$

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. $e_1$ $e_n$ $c_i$ $e_i$ $w_i$ $w_i$

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 ] $w_i c_i=p$ $i\leq n$

np-hardness optimization 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

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:

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 . $c_i$ $n$ $D = \sum_i c_i$

Beweisskizze. Korrigieren Sie alle Eingaben wobei und (WLOG) . Umformulierung des Problems etwas, das Ziel zu finden der Größe maximiert . $(S, w, c, K)$ $w,c\in\mathbb{R}_+^n$ $S=\{1,2,\ldots,n\}$ $M\subseteq S$ $K$ $\frac{\sum_{i\in M} w_i c_i}{\sum_{i\in M} c_i} - \sum_{i\in M} w_i$

Betrachten Sie das folgende dynamische Programm. Für alle ganzen Zahlen mit , und , definieren Die gewünschte Lösung ist . $(d_1, d_2, k, m)$ $0\le d_1 \le d_2 \le D$ $0\le k \le K$ $k\le m\le n$

ϕ (d_{1}, d_{2}, k, m) = max {\sum_{i \in M} w_{i} (c_{i} / d_{1} - 1) : M \subseteq [m], | M | = k, \sum_{i \in M} c_{i} = d_{2}} .

$\textstyle\phi(d_1, d_2, k, m) = \max \Big\{ \sum_{i\in M} w_i (c_i / d_1 - 1) ~:~ M \subseteq [m],\, |M| = k, \, \sum_{i\in M} c_i = d_2\Big\}.$

max_{d} ϕ (d, d, K, n)

$\max_d \phi(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. $\phi(d_1, d_2, k, m)$ $m$

ϕ (d_{1}, d_{2}, k, m) = max {\begin{cases} ϕ (d_{1}, d_{2} - c_{m}, k - 1, m - 1) + w_{m} (c_{m} / d_{1} - 1) \\ ϕ (d_{1}, d_{2}, k, m - 1) . \end{cases}

$\textstyle\phi(d_1, d_2, k, m) = \max\begin{cases} \phi(d_1, d_2 - c_m, k-1,m-1) + w_m(c_m/d_1-1) \\ \phi(d_1, d_2, k, m-1). \end{cases}$

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 . $O(n^2 D^2)$ $n$ $D$ $~~\Box$

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 . $D$ $n$

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. $w_i$

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.) $w_i=c_i$ $i$ $M$ $k$

Neal Young
quelle

Ist der Fall von dasselbe wie das Minimieren , das optimiert wird, wenn aus dem größten 's?

w_{i} = c_{i}

$w_i=c_i$

(\sum_{i \neq j \notin M} w_{i} w_{j}) / (\sum_{i \notin M} w_{i})

$(\sum_{i\neq j\notin M}w_iw_j)/(\sum_{i\notin M} w_i)$

M

$M$

w_{i}

$w_i$

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

Die Frage lautet: "Die Teilmenge M der Größe k."

Tsuyoshi Ito