Muszę przyznać, że stopień zaciekawienia tym tematem przeszedł moje oczekiwania.
W tym stosunkowo długim poście:
- Odpowiadam na kierowane do mnie pytania.
- Zamykam dyskusję związaną z pytaniem "Czy obranie drogi najpierw największy może być przyczyną, dla której nie podamy prawidłowej odpowiedzi?".
- Podsumowuję wszystko co zostało do tej pory powiedziane i rozpisuję to w postaci formalnego algorytmu.
- Napominam o zagadnieniach złożoności obliczeniowej.
- Wskazuję na odmienne podejście do tego problemu.
Zanim przejdę do meritum muszę przyznać, że przesyłanie rozpisanego przeze mnie kodu do tego problemu (o który często prosicie w mailach)drogą doczepiania go jako załącznika do indywidualnych listów jest kłopotliwe. Czy istnieje możliwość umieszczenia tego kodu w sieci, skąd każdy mógłby go pobierać do woli?
Wpierw przytoczę ponownie treść problemu:
Mamy zadany obszar, będący nieskończenie długą taśmą o zadanej szerokości.
Ponadto znamy promienie pewnej skończonej liczby okręgów.
Zadanie polega na wyszukaniu takiego ułożenia okręgów, aby
wysokość ograniczająca najwyższy okrąg była jak najniżej.
Odnoszę wrażenie że wiele osób nie potrafi tego poprawnie odczytać i prawdopodbnie jest to moja wina. Dlatego z góry przepraszam i zwracam uwagę na to że:
-problem dotyczy płaszczyzny a nie przestrzeni, mamy więc doczynienia z kołami (a nie kulami), a sugerowane (całkiem słusznie) porównanie do przekroju studni nie oznacza że mamy trzy wymiary.
-taśma jest nieskończona, ale ma swój początek, który umówiliśmy się umieszczać na dole.
Dryobates: Jeżeli chodzi o szybkość mojego kodu, to może być ona różna, w zależności od stopnia dokładności jaka nas interesuje, w najszybszym wariancie jest ona wielomianowa, w najwolniejszym podwójnie wykładnicza (czyli dla 10 okręgów trwa to wieczność).
Odpowiadając na drugie twoje pytanie powiem, że owszem sprawdza możliwość wprowadzania okręgów w dziury (co jest bezpośrednim powodem tak wielkiej złożoności obliczeniowej). Przesyłam Tobie ten kod ze szczególnymi podziękowaniami za zaangażowanie.
Ponadto sprawdziłem Twoje wyprowadzenia matematyczne, które reprezentują szczególnie eleganckie podejście do tematu, niestety nie są one poprawne (upewniałem się przez 1,5 godziny, żeby mieć pewność),
np.wzór H1 (pierwszy który podajesz)
zamiast H1 = R + r + Sqrt(r*(2R + r)) powinno być:
H1=R+r+Sqrt((R+r)(R+r)-4(R-Sqrt(Rr)(R-Sqrt(R*r))). co zaskakujące (i nie potrafię doprawdy powiedzieć dlaczego) twoje wzory dają zaledwie odrobinę zawyżony wynik (np dla R=8,r=3). Twój wzór daje 21.58 a powinno być 20.08, lecz nawet gdyby były one poprawne nie mają one wymaganej siły dowodowej, co w dosyć prosty sposób wykażę w następnej części listu.
"Czy obranie drogi najpierw największy może być przyczyną, dla której nie podamy prawidłowej odpowiedzi?".
Otóż niestety może być. Wiadomo, aby obalić jakiekolwiek twierdzenie wystarczy podać chociaż jedną sytuację w której jest ono fałszywe, oto ona:
Mamy obszar o długości 2R, jedno koło o wielkości R (zajmuje ono całą szerokość) oraz cztery koła o promieniach r=0.3R (nie zmieszczą się one w skrawku pomiędzy dużym kołem a narożnikiem obszaru, swoją drogą największy jaki się zmieści ma promień R*(3-2Sqrt(2))=około 0.17R). Jakie jest optymalne ułożenie? Dwa małe o promieniach r w narożnikach, następnie jeden duży R spoczywa na nich i na nim kładziemy styczne do ścian dwa pozostałe o promieniach r. A jakie rozwiązanie znajdziemy idąc od największego? Największy na dole, a potem cztery mniejsze nad nim. Na rysunku od razu widać że
tracimy w ten sposób rozwiązanie.
Zresztą możemy je stracić także i w takiej sytuacji: Szerokość 6R, Jeden okrąg o promieniu 2R, dwa o promieniach 1.5R. Ta sytuacja jest nieco odmienna. Oczywiście można dojść do rozwiązania zaczynając od największego, ale trzeba go umieścić w środku szerokości, a nie w narożniku. Naprawdę nie sposób pokryć tego algorytmicznie.
Okazuje się więc że zaczynając od największych, możemy w pewnych sytuacjach utracić dobre ułożenie.
Dlatego kolejne otwarte pytanie brzmi: Czy istnieje jakiś sposób aby obejść ten problem? Przyznam się, że sam na tym etapie jeszcze tego nie wiem.
Zapomnijmy na chwilę o tym że czasami możemy utracić dobre rozwiązanie z racji tego, że zaczynamy od największych okręgów. Nadeszła chwila aby zaproponować pierwszy algorytm.
Dane wejściowe: Liczba rzeczywista dodatnia D (szerokość), skończony ciąg n liczb rzeczywistych dodatnich r[n] (promienie).
0. Start.
- Posortuj r[n] malejąco.
- Powtarzaj co następuje n razy:
2.1 Pobierz kolejny promień R
2.2 Wypisz wszystkie położenia w które mógłbyś wstawić koło o promieniu R, biorać pod uwagę wstawienie go: (w narożnik obszaru) lub (tak aby był on styczny do wcześniej naniesionych kół i do ścian obszaru jednocześnie) lub (tak aby był on jednocześnie styczny do dowolnych dwóch kół naniesionych wcześniej).
2.3 Z wypisanych położeń wybierz najniższe, wprowadź tam koło i wróć do punktu 2
- Stop
Ważne pytanie stawiane przy pisaniu programów to: Powiedzmy że jeżeli dane będą zawierały podanych siedem kół, to program będzie znajdzie ich położenie w czasie t (np.dwie minuty), Więc o więcej czasu będzie trwało wykonanie programu, gdy wprowadzone dane będą o jedną dłuższe (czyli osiem kół)?. Jeżeli wydłuży się dwukrotnie to mówimy że złożoność obliczeniowa danego algorytmu jest wykładnicza.
Zaproponowany wyżej algorytm nie jest wykładniczy, dla każdego kolejnego koła musi sprawdzić pewną ilość możliwości, która jest większa od ilości możliwych ułożeń dla poprzedniego koła o pewną wartość wyrażoną wielomianem (w tym wypadku chyba 6+2n). Niemniej nie zapominajmy, że nasz algorytm czasami gubi poprawną odpowiedź.
Może więc całkowicie zmienić sposób patrzenia na nasz problem? Zamiast "Spróbuj upchnąć koło tu, a potem tam..." umieśćmy pierwsze koło w narożniku. Nasz obszar właśnie podzielił się na dwa podobszary (w jednym szczególnym przypadku na trzy). Teraz obliczmy jakie największe koło zmieściłoby się w tym nowym obszarze i przypiszmy tą liczbę do niego. Teraz bierzemy drugi okrąg i jeżeli jest on mniejszy lub równy tej liczbie, wstawiamy go do tego podobszaru, jeżeli nie, wyrzucamy go na górę (oczywiście w miarę najniżej), nasze nowe koło właśnie dokonało dalszego podziału obszaru, dla każdego z tych podobszarów (jest ich teraz cztery w pewnej szczególnej sytuacji) obliczmy promień dla największego koła które hipotetycznie zmieściło by się w takim obszarze i przypisujemy tą liczbę do niego, i tak dalej.
Jak zwykle czekam na wasze obserwacje, szczególnie dotyczące właśnie zaproponowanej metody.
Gorąco pozdrawiam.