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

do góry

On 2013-05-21 16:52, bartekltg wrote:
> W dniu 2013-05-21 12:06, Michal Kleczek pisze:
>> On 2013-05-21 11:55, Michal Kleczek wrote:
>
>>>
>>
>> W przeciwnym wypadku mozna sie spierac, czy w ogole cokolwiek trzeba
>> ciac... Magia liczb rzeczywistych.
>
> Całe zadanie jest czymś takim od początku.
> Dla jednowymiarowej pizzy byś powiedział:
> Co wyciąć z jednostkowego domkniętego odcinka, by mieścił
> się w przedziale [0,1]
> ;)
>

Tak pol-zartem doszlismy do chyba powaznej sprawy - czyli w jaki sposob
pojecia matematyczne odpowiadaja rzeczywistosci. No bo co to niby znaczy
"wyciac" w powyzszym? Gdyby problem byl postawiony w kategoriach
fizycznych (czyli na przyklad sznurka i noza) to oczywiscie
jednowymiarowy "pasek" o minimalnej (ale wiekszej od zera) szerokosci.
Podobnie: pizza i noz to nie to samo co "kolo", "wnetrze kola", "okrag"
i "wycinanie prostej lub luku".
Trzeba uwazac. Matematyka to tylko zabawa symbolami - nic wiecej.

--
Michal

do góry

W dniu 2013-05-21 20:09, Michal Kleczek pisze:
> On 2013-05-21 16:52, bartekltg wrote:
>> W dniu 2013-05-21 12:06, Michal Kleczek pisze:
>>> On 2013-05-21 11:55, Michal Kleczek wrote:
>>
>>>>
>>>
>>> W przeciwnym wypadku mozna sie spierac, czy w ogole cokolwiek trzeba
>>> ciac... Magia liczb rzeczywistych.
>>
>> Całe zadanie jest czymś takim od początku.
>> Dla jednowymiarowej pizzy byś powiedział:
>> Co wyciąć z jednostkowego domkniętego odcinka, by mieścił
>> się w przedziale [0,1]
>> ;)
>>
>
> Tak pol-zartem doszlismy do chyba powaznej sprawy - czyli w jaki sposob
> pojecia matematyczne odpowiadaja rzeczywistosci. No bo co to niby znaczy
> "wyciac" w powyzszym? Gdyby problem byl postawiony w kategoriach
> fizycznych (czyli na przyklad sznurka i noza) to oczywiscie
> jednowymiarowy "pasek" o minimalnej (ale wiekszej od zera) szerokosci.
> Podobnie: pizza i noz to nie to samo co "kolo", "wnetrze kola", "okrag"
> i "wycinanie prostej lub luku".
> Trzeba uwazac. Matematyka to tylko zabawa symbolami - nic wiecej.

Jak się nie umie nią posługiwać, to tylko zabawa.
Jak się umie, potężna narzędzie;>

pzdr
bartekltg

do góry

W dniu 2013-05-21 20:20, bartekltg pisze:
> W dniu 2013-05-21 20:09, Michal Kleczek pisze:
>> On 2013-05-21 16:52, bartekltg wrote:

>>> Całe zadanie jest czymś takim od początku.
>>> Dla jednowymiarowej pizzy byś powiedział:
>>> Co wyciąć z jednostkowego domkniętego odcinka, by mieścił
>>> się w przedziale [0,1]
>>> ;)
>>>
>>
>> Tak pol-zartem doszlismy do chyba powaznej sprawy - czyli w jaki sposob
>> pojecia matematyczne odpowiadaja rzeczywistosci. No bo co to niby znaczy
>> "wyciac" w powyzszym? Gdyby problem byl postawiony w kategoriach
>> fizycznych (czyli na przyklad sznurka i noza) to oczywiscie
>> jednowymiarowy "pasek" o minimalnej (ale wiekszej od zera) szerokosci.
>> Podobnie: pizza i noz to nie to samo co "kolo", "wnetrze kola", "okrag"
>> i "wycinanie prostej lub luku".

I chyba nikt nie traktował tego jako zagadkę o fizycznych obiektach.

>> Trzeba uwazac. Matematyka to tylko zabawa symbolami - nic wiecej.
>
> Jak się nie umie nią posługiwać, to tylko zabawa.
> Jak się umie, potężna narzędzie;>

Oczywiście 'umie' w szerokim znaczeniu tego słowa;)

pzdr
bartekltg

do góry

On 20/05/2013 14:53, Michal Kleczek wrote:
> On 2013-05-20 15:37, Andrzej Jarzabek wrote:
>>
>> Istnieje bardzo wiele sposobów, w których cel można osciągnąć wycinając
>> dowolnie małą powierzchnię. Jak je porównasz?
>>
>
> To dobre pytanie.
> Idea jest taka, ze przyjmujemy jakis parametr i ustalamy jego wartosc.
> Porownywane metody pociecia musza byc parametryzowane tym samym parametrem.
>
> W przypadku paska i wycinkow mozna np przyjac za parametr szerokosc
> paska x. Wtedy wycinamy kolko o promieniu x ze srodka i odpowiednie
> wycinki kolowe.
>
> Moze byc?

To dośc nieprecyzyjne postawienie zadania. Czy kółko jest "paskiem"?
Jeśli uznamy że jest, to powstaje pytanie, czy szerokość takiego "paska"
to rzeczywiście promień koła - zależy od definicji owego "paska" i jak
dokładnie wolno wycinać. Biorąc pod uwagę, że paski mogą być cięte po
krzywych można się zastanawiać nad definicjią szerokości. A jak już
będziemy mieli taką definicję, to się zastanowić, czy pasek stworzony
przez wycięcie fragmentu między dwoma równoległymi odcinkami odległymi o
x nie będzie miał mniejszej 'szerokości' tam, gdzie dochodzi do krawędzi
pizzy i ma zaokrągloną końcówkę. I tak dalej.

do góry

W dniu 21.05.2013 o 17:13 Edek <e...@g...com> pisze:
> Ooops. Faktycznie nie zrozumiałem założeń, nie wiem dlaczego myślałem,
> że pizza jest "za duża" czyli większa niż talerz.

No właśnie ja też nie wiem, kroiłeś kiedyś pizzę położoną na dwukrotnie
mniejszym talerzu? :) Bo ja zdecydowanie lubię kolor moich ścian i sufitu
:)

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

W dniu niedziela, 19 maja 2013 17:51:02 UTC+2 użytkownik Edek napisał:

> Witam, grupa źle na mnie wpływa - nakładając dzisiaj rano
> płaty boczku na patelnię (okrągłą) zastanawiałem się,
> jakiego algorytmu użyć, aby uzyskać możliwie największą
> ilość boczku nałożonego na patelnię tak, żeby się równo
> przypiekł.


> Powiedzmy, że boczek jest podłużny i ma przekrój opsiany
> poligonem, jak to boczek. Kroimy w poprzek, czyli w
> płaszczyźnie przekroju, i układamy na patelni o promieniu
> r tak, aby uzyskać najlepsze możliwe wykorzystanie powierzchni
> patelni. Przekrój boczku na płaską podstawę (nie wiem jak
> to dobrze opisać, mam nadzieję że wiadomo o co chodzi,
> z boczkiem każdy przecież miał do czynienia kiedyś, prawda?).


Ktoś kiedyś szukał dobrego programu do rozwiązywania jednej z
wielu odmiany tego zadania. Mianowicie było dostępnych N
kształtów/rozmiarów desek. Zakup każdego kształtu wiązał się
z kosztem. Było także zadanych M kształtów i każdy kształt
potrzebny w określonej ilości. I jedne i drugie kształty
były wielokątami. Trzeba było uzyskać te M kształtów z
tamtych N kształtów, minimalizując koszt całkowity. Na koszt
całkowity poza zakupem N kształtów składał się także koszt
cięcia. Tak więc trzeba było zminimalizować cenę zakupu plus
łączną długość cięcia plus ilość pojedynczych cięć po prostej.

Zadanie było jak najbardziej praktyczne.

Pozdrawiam

do góry