Algorytm minimalizujący pole powierzchni, przy danej objętości

Rozważ następujące zadanie algorytmiczne:

Dane wejściowe: dodatnia liczba całkowita wraz z podstawową faktoryzacją Znajdź: dodatnie liczby całkowite które minimalizują , z zastrzeżeniem ograniczenia, że$n$
$x,y,z$$xy+yz+xz$$xyz=n$

Jaka jest złożoność tego problemu? Czy istnieje algorytm czasu wielomianowego? Czy to trudne NP?

Ten problem zasadniczo pyta: ze wszystkich prostokątnych brył, których objętość wynosi i których wymiary są liczbami całkowitymi, który ma najmniejszą powierzchnię?$n$

Problem ten postawił Dan Meyer pod tytułem Problem matematyczny, którego 1000 nauczycieli matematyki nie mogło rozwiązać . Jak dotąd żaden z nauczycieli matematyki, z którymi pracował, nie znalazł rozsądnego algorytmu dla tego problemu. W jego kontekście definicja „rozsądnego” jest nieco nieprecyzyjna, ale jako informatycy możemy zadać bardziej precyzyjne pytanie o złożoność tego problemu.

Oczywistym podejściem jest wyliczenie wszystkich możliwości dla , ale to zajmuje czas wykładniczy. Komentatorzy na blogu Dana Meyera zaproponowali wiele wydajnych algorytmów kandydujących, które niestety okazały się nieprawidłowe. Martin Strauss sugeruje, że ten problem wydaje się niejasno przypominać 3-partycję , ale nie widzę zmniejszenia.$x,y,z$

Pozwolę sobie również wyjaśnić niektóre nieporozumienia, które widziałem w komentarzach / odpowiedziach:

• Nie można zmniejszyć z 3-partycji, po prostu zastępując każdą liczbę jej siłą , ponieważ funkcje celu dwóch problemów są różne. Oczywista redukcja po prostu nie działa.$q$$2^q$

• Nie jest prawdą, że optymalne rozwiązanie obejmuje wybranie jednego z jako najbliższego dzielnika od do . Widzę wiele osób, które zakładają, że tak jest, ale w rzeczywistości nie jest to poprawne. Zostało to już obalone na blogu Dana Meyera. Weźmy na przykład ; , a 4 dzieli 68, więc możesz pomyśleć, że co najmniej jeden z powinien wynosić 4; nie jest to jednak poprawne. Optymalnym rozwiązaniem jest$x,y,z$$n$$\sqrt[3]{n}$$n=68$$\sqrt[3]{68} \approx 4$$x,y,z$$x=2$ , $y=2$ , $z=17$ . Kolejny kontrprzykład to $n=222$ ,$\sqrt[3]{222}\approx 6$, ale optymalnym rozwiązaniem jest$x=37$,$y=3$,$z=2$. (Możebyć prawdą, że dla wszystkich$n$optymalne rozwiązanie polega na tym, aby co najmniej jeden z$x,y,z$był równy albo najmniejszemu dzielnikowi$n$większemu niż$\sqrt[3]{n}$ lubnajwiększy dzielnik$n$mniejszy niż$\sqrt[3]{n}$ - W tej chwili nie mam kontrprzykładu - ale jeśli uważasz, że to stwierdzenie jest prawdziwe, wymagałoby to dowodu. Absolutnie nie możesz zakładać, że to prawda.)

• „Spraw , aby były tego samego rozmiaru” nie zawsze daje optymalną odpowiedź we wszystkich przypadkach; zobacz post na blogu Dana Meyera, aby uzyskać kontrprzykłady. Lub przynajmniej dla niektórych rozsądnych interpretacji wyrażenia „czynią je mniej więcej tego samego rozmiaru”, istnieją kontrprzykłady pokazujące, że ta strategia nie jest w rzeczywistości optymalna. Jeśli chcesz wypróbować jakąś strategię tego rodzaju, upewnij się, że dokładnie podałeś roszczenie, a następnie podaj dokładny matematyczny dowód.$x,y,z$

• Czas działania nie jest wielomianowy. Aby problem występował w P, czas działania musi być wielomianem na długości danych wejściowych . Długość danych wejściowych to coś w rodzaju lg n , a nie n . Oczywisty algorytm siły brutalnej można uruchomić w czasie O ( n 3 ) lub O ( n 2 ) , ale jest on wykładniczy w lg n, a zatem liczy się jako algorytm czasu wykładniczego. To nie jest pomocne.$O(n^3)$$\lg n$$n$$O(n^3)$$O(n^2)$$\lg n$

Oto zmodyfikowana wersja algorytmu „wybierz dzielnik w pobliżu pierwiastka z kostki”. Wciąż musi brutalnie wymuszać wiele przypadków, więc nie jestem pewien, ile prawdziwej poprawy jest szybsze od wyliczenia wszystkich przypadków. Jednak przesłałem go jako poprawkę do algorytmu OEIS (tego, który wygenerował nieprawidłowe wyniki), ponieważ uważam, że powinien on być co najmniej dokładny.

Oto algorytm znajdowania (s1, s2, s3) i pola powierzchni prostokątnego pryzmatu, biorąc pod uwagę jego objętość n:

1. Biorąc pod uwagę n, znajdź pierwiastek kostki.
2. Ustaw początkową liczbę całkowitą s1 na suficie tego pierwiastka kostki.
3. Sprawdź, czy s1 jest dzielnikiem n, a jeśli nie, zmniejsz s1 o 1.
4. Jeśli zostanie znaleziony dzielnik s1, ustaw początkową wartość s2 jako pułap pierwiastka kwadratowego z (n / s1).
5. Następnie sprawdź, czy s2 jest dzielnikiem n / s1, a jeśli nie, zmniejsz s2 o 1.
6. Po znalezieniu dzielnika s2, s3 jest wtedy ustawiane na n / (s1 * s2).
7. Bieżące pole powierzchni jest obliczane przez 2 * (s1 * s2 + s1 * s3 + s2 * s3).
8. Obecny SA jest porównywany z bieżącym minimum. Jeśli jest to pierwsze obliczone pole powierzchni, jest ono zapisywane jako minSA. Po pierwszym sprawdzamy, czy bieżący SA jest mniejszy niż minSA, a jeśli tak, zapisz go w minSA.

Ten algorytm wylicza niektóre z potrójnych wartości (s1, s2, s3), ale wystarczy tylko przetestować dzielniki pod pierwiastkiem kostki. (Ponieważ nie wszystkie trzy dzielniki mogą znajdować się powyżej pierwiastka sześcianu). W podobny sposób s2 musi jedynie przetestować dzielniki n / s1 pod pierwiastkiem kwadratowym n / s1, ponieważ nie oba dzielniki mogą znajdować się powyżej pierwiastka kwadratowego)

Uwaga na krok 3: jeśli pierwiastek sześcianu jest dzielnikiem, to n jest sześcianem i możemy się tam zatrzymać z minimalnym polem powierzchni 6 * s1 ^ 2 od pudełka (s1, s1, s1).

Pyton:

import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0))) 
    minSA=-1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:  
            s1 = s1 - 1
        s1quot = int(n/s1) 
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))  
            SA = 2*(s1*s2 + s1*s3 + s2*s3)  
            if minSA==-1:
                minSA=SA
            else:
                if SA<minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1    
    return minSA

$k$

$\log(x), \log(y), \log(z)$$n$

• Najłatwiejszy trudny problem: partycjonowanie liczb / Mertens

• Partycjonowanie numerów w wielu kierunkach / Korf

Edytować

Oto nieformalny argument, dlaczego mało prawdopodobne jest istnienie szybkiego algorytmu. To zdanie się nie zmieniło, ale wyjąłem to, co tu kiedyś było, ponieważ zostało skonstruowane zbyt podobnie jak formalny dowód w następnej części, a dyskusja zaczęła się odsuwać na błędy, z których niektóre zauważyłem siebie i jednego z czego DW uprzejmie mi zwrócił uwagę. Zamiast tego spróbuję wyrazić za tym intuicję.

$N$

Co się stanie, gdy przetłumaczymy te same kroki na inną algebrę, taką jak dodawanie i odejmowanie zamiast mnożenia i dzielenia? Wiemy (patrz lemat poniżej), że nasz algorytm znajdzie 3-partycję, której produkty są równe, jeśli taka istnieje, lub też ustali, że taka 3-partycja nie istnieje. Tak więc, jeśli moglibyśmy przetłumaczyć te same techniki na grupę dodatków, moglibyśmy znaleźć 3-partycję, której sumy są równe, lub ustalić, że taka partycja nie istnieje. Innymi słowy, moglibyśmy rozwiązać 3-partycję w czasie wielomianowym. To niezbyt prawdopodobne.

Dlaczego więc taki algorytm może działać w przypadku mnożenia, a nie w przypadku dodawania? Jednym z możliwych powodów jest to, że każda liczba całkowita ma unikalny rozkład na czynniki pierwsze przy pomnożeniu, ale jest cykliczna podczas dodawania. Innym jest to, że mnożenie tworzy pierścień z dodawaniem, więc masz inny zestaw operacji, których możesz użyć. Inną sprawą jest konieczność uogólnienia algorytmu, aby działał on dla liczb niepierwszych i może zależeć od ich pierwotności. Jedna wskazana DW jest taka, że ​​konkretna metoda tłumaczenia może wykładniczo zwiększyć rozmiar twoich danych wejściowych. A może jednak P = NP.

Ale jeśli są to luki, które pozwalają na szybki algorytm, myślę, że nadal warto wiedzieć, ponieważ sugeruje, gdzie powinniśmy skoncentrować nasze wysiłki. Powinniśmy szukać czegoś, co by się zepsuło, gdybyśmy próbowali zastosować to do problemu NP-zupełnego. Podejście, które uogólniałoby na inne algebry, prawdopodobnie polega na szczekaniu niewłaściwego drzewa. Podejrzewam jednak, że mnożenie nie jest wystarczająco różne, aby to zadziałało, ale to tylko przeczucie.

Lemat

$m = \sqrt[3]{N}$$(am, bm, \frac{m}{ab})$$a$$b$$(ab + \frac{1}{a} + \frac{1}{b})m^2$$a = b = 1$

$xyz = N$

$(am)(bm) + (am)(\frac{m}{ab}) + (bm)(\frac{m}{ab}) = abm^2 + \frac{m^2}{b} + \frac{m^2}{a} = (ab+\frac{1}{a}+\frac{1}{b})m^2$

$f(a,b) = ab + \frac{1}{a} + \frac{1}{b}$$\frac{\delta f}{\delta a} = b - \frac{1}{a^2}$$\frac{\delta f}{\delta b} = a - \frac{1}{b^2}$$a = b^2, b = a^2$$a$$b$$a = b = 1$

Moją bezpośrednią motywacją do udowodnienia tego było wypełnienie fali ręki w moim dowodzie powyżej, że jeśli istnieje rozwiązanie z doskonałą kostką, jest ono optymalne. Jednak ta formuła może być przydatna do przycinania drzewa wyszukiwania.

Różne myśli

Nie widzę żadnej oczywistej symetrii oprócz wymienności x, y i z, co daje nam co najwyżej stały współczynnik 6. Mamy pewne przyspieszenia dla 2-partycji, które w zasadzie mówią, że chcielibyśmy, aby oba warunki być jak najbliżej siebie, ale nie widzę od razu zastosowania tego problemu.

Z góry mojej głowy, po prostu zapisanie dziennika wszystkich liczb natychmiast redukuje to do klasycznego problemu z 3 partycjami przy użyciu dodawania lub równoważnie, biorąc pewną liczbę do potęgi liczb w dowolnym problemie z dodawaniem 3 partycji, zamienia go w taki problem mnożenia jak ten. Oznacza to, że ten problem nie powinien być łatwiejszy. Mamy tutaj faktoryzację pierwszą, podczas gdy faktoryzacja ta nie byłaby pierwszą, ale czy to nam pomaga?

Graficznie powierzchnia xyz = 0 wyglądałaby jak połączenie płaszczyzn xy, yz i xz, a dla dowolnego dodatniego n równanie wyglądałoby jak y = n / xz, więc każdy przekrój wzdłuż płaszczyzny współrzędnych byłby hiperbola. Ogólnie możemy powiedzieć, że ilość, którą próbujemy zminimalizować, jest najniższa u źródła i rośnie najszybciej w linii, gdzie x = y = z. Gdybyśmy mogli szukać tylko wzdłuż tego rozmaitości, moglibyśmy zredukować się do problemu dwuwymiarowego.