Ustaw problem optymalizacji - czy jest np. Kompletny?

Ustawiono . Dla każdego elementu mamy wagę i kosztujemy . Celem jest znalezienie podzbioru o rozmiarze który maksymalizuje następującą funkcję celu: . $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}$

Czy problem jest trudny NP?

Ponieważ funkcja celu wydaje się dziwna, pomocne jest wyjaśnienie zastosowania funkcji celu.

Załóżmy, że mamy n przedmiotów od do a w naszym ekwipunku są kopie każdego obiektu . Mamy kilku klientów, którzy są zainteresowani tymi obiektami proporcjonalnie do ich wagi , co oznacza, że obiekt o większym jest bardziej popularny. Mamy internetowy system sprzedaży i musimy poprawnie odpowiadać na prośby naszych klientów. Nie możemy rozpoznać obiektów po ich kształtach (wszystkie wyglądają tak samo!). Ale mamy jakiś klasyfikator, aby je znaleźć. Każdy klasyfikator może służyć do wykrywania kopii obiektu. Naszym celem jest uruchomienie k klasyfikatora, aby zmaksymalizować zadowolenie naszych klientów. $e_1$ $e_n$ $c_i$ $e_i$ $w_i$ $w_i$

PS: Przydatne może być przemyślenie przypadku, w którym dla wszystkich ; jednak nie jestem pewien. [ Myliłem się co do tego! Zgodnie z tym założeniem jest w P ] $w_i c_i=p$ $i\leq n$

np-hardness optimization

— Nasooh
źródło

Właściwy termin jest mniejszy lub równy największej wadze elementu spoza M. Więc jeśli masz element o dużej wadze, lepiej jest umieścić go w M, niż pozwolić mu się zmarnować. Zatem M powinno składać się z elementów o największej masie k. Dobrze?

— zotachidil

To nie jest poprawne, ponieważ koszty są również ważne. Rozważ następujący przykład:

— Nasooh,

w1 = 50, c1 = 80 - w2 = 40, c2 = 15 - w3 = 10, c3 = 5. Dla k równego 1 wybór e2 jest korzystniejszy niż e1.

— Nasooh,

Masz rację. Hmm ...

— zotachidil,

Dziękujemy za próbę wyjaśnienia motywacji. Niestety związek między twoim wyjaśnieniem a funkcją celu w pytaniu jest nadal dla mnie całkowicie niejasny, ale sądzę, że muszę być zadowolony z obecnego wyjaśnienia, aby pytanie było rozsądne.

— Tsuyoshi Ito,

Odpowiedzi:

Poniższa odpowiedź zauważa, że szczególny przypadek problemu można rozwiązać w czasie wielomianowym. To nie w pełni odpowiada na pytanie zawarte w poście, ale może dać pewien wgląd w to, co może być potrzebne do potwierdzenia twardości NP i może wywołać dodatkowe zainteresowanie postem ...

Obserwacja. Problemem stanowisko zawiera algorytm, który, biorąc pod uwagę wszystkie przypadki, gdzie każdy jest liczbą całkowitą, jest uruchamiany w czasie wielomian i . $c_i$ $n$ $D = \sum_i c_i$

Szkic próbny. Napraw dowolne dane wejściowe gdzie i (WLOG) . Lekko odtwarzając problem, celem jest znalezienie o rozmiarze maksymalizującym $(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$

Rozważ następujący program dynamiczny. Dla dowolnych liczb całkowitych z , , i , zdefiniuj $(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$ Pożądanym rozwiązaniem jest.

ϕ (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)$

Dzieląc możliwe rozwiązania dla na te, które zawierają a te, które tego nie robią, otrzymujemy powtarzalność $\phi(d_1, d_2, k, m)$ $m$ Sprawy graniczne zostawiamy jako ćwiczenie.

ϕ (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}$

Liczba podproblemów jest , a każda strona prawy nawrotu można ocenić w stałym czasie, tak przebiegów algorytmu czasu wielomian i . $O(n^2 D^2)$ $n$ $D$ $~~\Box$

$D$ $n$

$w_i$

$w_i=c_i$ $i$ $M$ $k$

— Neal Young
źródło

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$

@WillardZhan, tak, to wydaje się słuszne.

— Neal Young,

-6

Pytasz o maksymalizację funkcji bez ograniczeń?

To jest naprawdę proste. Jeśli M jest największym zestawem, to jest najlepszym rozwiązaniem. Nie trzeba niczego obliczać.

Ten problem wydaje się podobny do problemu plecaka, który jest nawiasem mówiąc NP.

— Guillermo.
źródło

Pytanie brzmi: „podzbiór M rozmiaru k”.

— Tsuyoshi Ito