Dnia Tue, 21 May 2013 17:04:53 +0200 po głębokim namyśle bartekltg rzekł:

> 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ł:

>>> 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.

O ile dobrze pamiętam morał tej historii był taki: jeżeli na podstawie
mieści się 1000000 i 1/2 kulki, wystąpią nieregularności. Jak równe
1000000 - też ;).

>> 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.

Jeżeli małe w porównaniu do pudła i dobrze potrząśniesz: tak.

> 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.

Nie próbowałem wyżarzać boczku. To tylko hipermakety praktykują
i to za pomocą chemii :)

Nie jest wielką tajemnicą, że moja wiedza nt. numeryki i algorytmiki
jest dość wyrywkowa. Wyżarzania jeszcze nigdy nie stosowałem.

>> 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.
>
> ?

Mówiłem o: małych kuleczkach nasypanych do pojemnika (do czego analogiczne
są bąbelki przy powierzchni i częściowo kryształy). One będą dążyły do
"zmieszczenia się" jak najniżej, czyli w jakiejś minimalnej objętości [1].

Problem jest podobny do układania boczku: zaczyna się układać od brzegu
zapełniając patelnię, aż się dochodzi do ostatnich kawałków, gdzie może
się okazać, że "klocek nie pasuje do dziury" i wtedy zaczyna się
przekładać pozostałe tak, żeby "jeszcze jeden wlazł".

To jest analogiczne do lokalnych strukturalnych nieregularności:
cześć kulek lokalnie ułoży się bardzo nietypowo, ale cały układ dzięki
temu będzie "niższy". Podobnie jest w materiałach, w tym kryształach
(ok, czytałem o tym zanim miałem komputer - nie wiem czy znajdę
linka i czy dobrze pamiętam detale).

To jest dosyć daleka analogia, ale problem w pierwszym przybliżeniu jest
podobny. Nie jest taki sam, bo tu mamy twarde ograniczenie koła, a przy
kulkach minimum bliskie globalnego.

[1] Jeszcze pytanie jakie kulki. Lekkie mogą się zachowywać nieco inaczej,
ale jak nasypiesz metalowych i potrzęsiesz nimi będziesz miał płaską
powierzchnię na wierzchu.

--
Edek