Czy ten kombinatoryczny problem optymalizacji jest podobny do jakiegokolwiek znanego problemu?

10

Problem jest następujący:

Mamy dwuwymiarową tablicę / siatkę liczb, z których każda reprezentuje pewną „korzyść” lub „zysk”. Także ma dwie nieruchome całkowite i (jako „szerokość” i „wysokość”). A stałej całkowitej . $w$ $h$ $n$

Teraz chcą nałożyć prostokątów o wymiarach na siatce, tak aby łączna suma wartości komórek w tych prostokątów jest zmaksymalizowane. $n$ $w \times h$

Poniższy rysunek przedstawia przykład dwuwymiarowej siatki z dwóch takich prostokątów overlayed na nim (obraz nie wykazuje rozwiązanie optymalne, tylko jedno możliwe nakładanie się, gdy i ) $w = h = 2$ $n = 2$

Przykład siatki

Prostokąty nie mogą się przecinać (w przeciwnym razie musielibyśmy po prostu znaleźć optymalną pozycję dla jednego prostokąta, a następnie umieścić wszystkie prostokąty w tej pozycji.)

W powyższym przykładzie całkowita suma wartości w komórkach wyniosłaby $-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

Czy jest to podobne do jakiegokolwiek znanego problemu optymalizacji kombinatorycznej? abym mógł zacząć czytać i spróbować znaleźć sposoby na rozwiązanie tego problemu.

Więcej informacji dla zainteresowanych:

Do tej pory jedynymi pomysłami, jakie miałem, był albo chciwy algorytm (który znalazłby najlepszą lokalizację dla pierwszego prostokąta, a następnie znalazłby nienakładające się położenie dla drugiego prostokąta itp.) Lub jakieś metaheurystyczne, takie jak algorytmy genetyczne.

W rzeczywistości chcę rozwiązać ten problem za pomocą siatki, która ma około miliona komórek i dziesiątki tysięcy (lub nawet setki tysięcy) prostokątów, chociaż nie jest konieczne rozwiązanie go w krótkim czasie (tzn. Byłoby to do przyjęcia algorytm zajmuje godziny, a nawet dni.) Nie oczekuję dokładnego rozwiązania, ale chcę uzyskać taki, który jest tak dobry, jak to możliwe, biorąc pod uwagę te ograniczenia.

Twoje zdrowie!

— pięćdziesiąt osiem
źródło

(przez telefon) wydaje się, że można to rozwiązać przy maksymalnym dopasowaniu przy transformacji i kilku dodatkowych ograniczeniach. Spróbuję napisać później.

— Nicholas Mancuso

n

$n$

n - 1

$n-1$

s

$s$

L

$L$

s

$s$

L

$L$

\geq s

$\ge s$

2

Moje ostatnie sformułowanie miało fatalną wadę, która wymagałaby wykładniczej ilości węzłów „ograniczających”.

$r$ $w_r$ $r, r'$ $k=n$

— Nicholas Mancuso
źródło

To kierunek, w którym obecnie się skłaniam, eksperymentuję z tym i akceptuję rozwiązanie, jeśli to ten, którego używam, na zdrowie.

— pięćdziesiąt osiem

2

Możesz sformułować to jako gigantyczną instancję programowania liniowego liczb całkowitych (ILP), a następnie zastosować gotowy do użycia solver ILP (lp_solve, CPLEX itp.). Dadzą ci najlepsze rozwiązanie, jakie mogą znaleźć. Biorąc pod uwagę rozmiar wystąpienia problemu, nie wiem, czy będzie to wystarczająco wydajne, ale łatwo byłoby spróbować.

$x_r$ $r$ $x_r=1$ $r$ $x_r=0$ $\sum_r c_r x_r$ $c_r$ $r$ $\sum_r x_r = n$ $x_r + x_s \le 1$ $r,s$

— DW
źródło

Czy uważasz, że ten problem jest trudny do NP? Nie jestem przekonany, że nie ma rozwiązania wieloczasowego, a solwery ILP raczej nie ukończą nawet instancji o średniej wielkości.

— RB

1

@RB, nie mam pojęcia, czy jest to trudne NP. Zobacz mój komentarz pod pytaniem o programowaniu dynamicznym, aby po raz pierwszy zastanowić się, jak znaleźć algorytm czasu wielomianowego (ale nie wiem, czy wynikowy algorytm będzie miał wartość P, czy nie). Jeśli chodzi o to, co potrafią solwery ILP, jedynym sposobem na sprawdzenie tego jest próba - czasem ich wydajność może być zaskakująca.

— DW