W dniu 2013-05-20 21:52, Edek pisze:
> Dnia Mon, 20 May 2013 01:55:16 +0200 po głębokim namyśle bartekltg rzekł:
>
>> Jeśli szukasz algorytmu dającego ścisły deterministyczny wynik,
>> jest źle. Prostszy problem, czyli zamiast dowolnej figury mamy okręgi:
>> http://en.wikipedia.org/wiki/Circle_packing_in_a_cir
cle
>> http://hydra.nat.uni-magdeburg.de/packing/cci/#Resul
ts
>
> Dobre. Nie wszystkie kolumny rozumiem, ale gęstość rośnie, czego można się
> było spodziewać.

I będzie rosnąć aż do maksymalnego upakowania na płaszczyźnie.
Zwróć uwagę, że definicja tam wymusza monotoniczność gęstości.
Jakby się zapytać, ile jednostkowych kół mieści się na patelnii
o promieniu r, i zrobić wykres gęstości, byłby on ząbkowany
(z maksimamy odpowiadającymi punktom z tabelki).


>> Zwróć uwagę, że tylko do 13 kółka 'minimalna patelnia'
>> jest pewna. Kolejne to to, co wypluł algorytm (w drugim linku jest
>> bardzo bogata bibliografia,
>> pewnie coś dla siebie zajdziesz boczku), nawet bez pewności,
>> że nie da się lepiej.
>
> O przepraszam bardzo. Podobno jestem dresem a nie boczkiem ;) No

Ech, tak to jest, jak człowiek pisze jedno zdanie, a w polowie
uznaje, że jakby je napisał inaczej, byłoby lepiej.
Na pocieszenie, skutki tego widać i w poważnych interentowych gazetach;)

> ale dzięki, nie wiedziałem, że koła w kole są warte takiej ilości
> zachodu i mają bibliografię - najważniejsze jest wiedzieć gdzie
> szukać, podobno.

Proste problemy często mają skomplikowane rozwiązania;)

>> Oryginalny problem i jakieś algorytmy i herystyki powinno się dać
>> wygooglać, problem dość życiowy,
>> ale mi nic rozsądnego wyszukiwarka nie wypluła,
>> pewnie złe zaklęcia wpisałem.
>
> Zakręcony ogon?
>
> Chyba najlepiej zacząć od bąbelków w wodzie, kulek w naczyniu
> czy struktury kryształów. Oidp kulki i tym podobne szukają stanu
> o najniższej energii - jeżeli znajdą minimum lokalne może

No właśnie, tylko lokalnie. Fizycznie mamy tak duże układy,
że coś się zaraz zaburzy i uklad przeleci do niższego minimum,
ale i tak obserwuje się przechłodzone czy przegrzane substancje.

> nastąpić gwałtowna konwersja do niżej położonego układu, co
> zawsze wiąże się z różnymi nieregularnościami w strukturze.
> Najlepsze jest to, że kulki w naczyniu tak mają, stabilizuje
> się układ z paroma nieregularnościami, jeżeli cała reszta może
> przez to zmieścić się "niżej". Potem wystarczy poszukać nie
> kulek a cząsteczek i ma się taki boczek...

Wsypując klocki do pudła ukłądają się one choćby
w przybliżeniu minimalnie? Nie do końca.

Na bazie takiej analogii z fizyką powstała metoda wyżarzania,
na pewno znasz
http://en.wikipedia.org/wiki/Simulated_annealing
Ale jak ono sobie poradzi z problemem boczku, trudno zgadnąć.
Cudów bym nie oczekiwał, ukłąd mały, lokalnych minimów rozsianych
wszędzie dużo.

> Tyle o kulkach, pamiętam że to się bardzo ciężko liczy, ale
> też pytanie jest w jakiej objętości się zmieszczą i czy na pewno.

?

pzdr
bartekltg