On 2013-05-21 08:39, Wojciech "Spook" Sura wrote:
> W dniu 21.05.2013 o 08:35 Edek <e...@g...com> pisze:
>>> Rzuciłem ten problem w charakterze żartu, ponieważ strasznie trudno jest
>>> go formalnie zdefiniować - co już zostało zauważone. Sam wpadłem na
>>> rozwiązanie z połową obwodu plus jeden punkt i wydaje mi się, że to jest
>>> prawidłowe rozwiązanie, ale nigdy nie przetestowałem go w praktyce, bo
>>> choć technicznie poprawne, to jednak jest mało praktyczne :)
>>
>> Przynajmniej wiadomo, że jesz kulturalnie pizzę - ja jem łapom ;)
>>
>> Mnie w tej dyskusji ciekawi co innego: nasz mózgi radzą sobie z tymi
>> problemami bez problemu, ale jak trzeba zaimplementować algorytm
>> to nagle sprawa robi się mega-skomplikowana, ekhm, NP-zupełna.
>
> Tu nie chodzi o poziom komplikacji algorytmu, tylko o problem z formalną
> definicją - nie określiłem, w jaki sposób usuwane są kawałki pizzy.
> Gdybym to zrobił, to pewnie nie trzeba byłoby do tego nawet algorytmu,
> zrobiłby się z tego prosty problem geometryczny.

I miedzy innymi dlatego zabawa jest niezla... Szczegolnie, ze problem
jest niewatpliwie bardzo istotny. Ja zrozumialem problem tak, ze chcemy
jak najmniej pizzy zjesc zeby warunek koncowy byl spelniony.

--
Michal

do góry

On 21.05.2013 11:38, Michal Kleczek wrote:
> On 2013-05-21 11:15, Wojciech "Spook" Sura wrote:
>>
>> Załóżmy, że tniesz pionowo. Pozbywasz się górnego i dolnego punktu, więc
>> tam pizza już nie styka się z talerzem, natomiast obie połówki
>> przesuwasz w stronę środka talerza o pół grubości cięcia - tym samym
>> odsuwając pozostałe punkty od krawędzi.
>
> No ale to przy zalozeniu ze wycinasz pasek - czyli ciec jest dwa, a nie
> jedno.

Ale pasek wycinasz tylko punktów, więc raczej jest samo "cięcie nożem" -
magia liczb rzeczywistych.

Przykład na osi liczbowej - z przedziału <0-2> wycinasz 1. Masz <0,1) i
(1,2> - kawałki nie docierają do 1 (nie mają kresu) ale są dowolnie blisko.

--
Pozdrawiam
Michoo

do góry

On 2013-05-21 11:46, Michoo wrote:
> On 21.05.2013 11:38, Michal Kleczek wrote:
>> On 2013-05-21 11:15, Wojciech "Spook" Sura wrote:
>>>
>>> Załóżmy, że tniesz pionowo. Pozbywasz się górnego i dolnego punktu, więc
>>> tam pizza już nie styka się z talerzem, natomiast obie połówki
>>> przesuwasz w stronę środka talerza o pół grubości cięcia - tym samym
>>> odsuwając pozostałe punkty od krawędzi.
>>
>> No ale to przy zalozeniu ze wycinasz pasek - czyli ciec jest dwa, a nie
>> jedno.
>
> Ale pasek wycinasz tylko punktów, więc raczej jest samo "cięcie nożem" -
> magia liczb rzeczywistych.
>
> Przykład na osi liczbowej - z przedziału <0-2> wycinasz 1. Masz <0,1) i
> (1,2> - kawałki nie docierają do 1 (nie mają kresu) ale są dowolnie blisko.
>

No to jest pytanie o to, co to znaczy "dotykac". Czy przedział (1, 2>
"dotyka" jedynki?
Wg mnie "dotyka". Zdefiniuje "niedotykanie":
Istnieje takie eps, ze dowolny punkt pizzy jest w odleglosci > eps od
brzegu talerza.

--
Michal

do góry

Dnia Mon, 20 May 2013 16:13:45 +0200 po głębokim namyśle bartekltg rzekł:

> W dniu 2013-05-20 15:56, Michal Kleczek pisze:
>> On 2013-05-20 15:50, bartekltg wrote:

>> Dla ustalonego dx porownujemy sposoby :-)
>>
>> Ale ok - moze byc dlugosc cięcia. Wtedy ciecie z krawedzi o dlugosci
>> min polowy obwodu jest najlepszym rozwiazaniem?
>
> Nie. Cięcie po średnicy. Raz wystarczy.

Ja pizza ma dwa razy większą średnicę niż talerz to nie ma prawa działać,
chyba że źle rozumiem opis.

--
Edek

do góry

On 2013-05-21 11:55, Michal Kleczek wrote:
> On 2013-05-21 11:46, Michoo wrote:
>> On 21.05.2013 11:38, Michal Kleczek wrote:
>>> On 2013-05-21 11:15, Wojciech "Spook" Sura wrote:
>>>>
>>>> Załóżmy, że tniesz pionowo. Pozbywasz się górnego i dolnego punktu,
>>>> więc
>>>> tam pizza już nie styka się z talerzem, natomiast obie połówki
>>>> przesuwasz w stronę środka talerza o pół grubości cięcia - tym samym
>>>> odsuwając pozostałe punkty od krawędzi.
>>>
>>> No ale to przy zalozeniu ze wycinasz pasek - czyli ciec jest dwa, a nie
>>> jedno.
>>
>> Ale pasek wycinasz tylko punktów, więc raczej jest samo "cięcie nożem" -
>> magia liczb rzeczywistych.
>>
>> Przykład na osi liczbowej - z przedziału <0-2> wycinasz 1. Masz <0,1) i
>> (1,2> - kawałki nie docierają do 1 (nie mają kresu) ale są dowolnie
>> blisko.
>>
>
> No to jest pytanie o to, co to znaczy "dotykac". Czy przedział (1, 2>
> "dotyka" jedynki?
> Wg mnie "dotyka". Zdefiniuje "niedotykanie":
> Istnieje takie eps, ze dowolny punkt pizzy jest w odleglosci > eps od
> brzegu talerza.
>

W przeciwnym wypadku mozna sie spierac, czy w ogole cokolwiek trzeba
ciac... Magia liczb rzeczywistych.

--
Michal

do góry

W dniu 2013-05-21 12:00, Edek pisze:
> Dnia Mon, 20 May 2013 16:13:45 +0200 po głębokim namyśle bartekltg rzekł:
>
>> W dniu 2013-05-20 15:56, Michal Kleczek pisze:
>>> On 2013-05-20 15:50, bartekltg wrote:
>
>>> Dla ustalonego dx porownujemy sposoby :-)
>>>
>>> Ale ok - moze byc dlugosc cięcia. Wtedy ciecie z krawedzi o dlugosci
>>> min polowy obwodu jest najlepszym rozwiazaniem?
>>
>> Nie. Cięcie po średnicy. Raz wystarczy.
>
> Ja pizza ma dwa razy większą średnicę niż talerz to nie ma prawa działać,
> chyba że źle rozumiem opis.

"pizzę, której rozmiar pokrywa się z rozmiarem talerza"

Ja to rozumiem, jako dokładnie taki sam rozmiar.

Zaakceptowanie przez autora rozwiązania z wygryzieniem
minimalnej szerokośći po ponad polowie obwodu sugeruje,
że rozumiem dobrze.

pzdr
bartekltg

do góry

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]
;)

pzdr
bartekltg

do góry

W dniu 2013-05-21 11:38, Michal Kleczek pisze:
> On 2013-05-21 11:15, Wojciech "Spook" Sura wrote:
>> W dniu 21.05.2013 o 11:06 Michal Kleczek <m...@k...org>
>> pisze:
>>
>>> On 2013-05-20 16:13, bartekltg wrote:
>>>> W dniu 2013-05-20 15:56, Michal Kleczek pisze:
>>>>>
>>>>> Ale ok - moze byc dlugosc cięcia. Wtedy ciecie z krawedzi o dlugosci
>>>>> min
>>>>> polowy obwodu jest najlepszym rozwiazaniem?
>>>>
>>>> Nie. Cięcie po średnicy. Raz wystarczy.
>>>
>>> Moge prosic o wyjasnienie? W swojej ciemnocie tego nie widze.
>>
>> Załóżmy, że tniesz pionowo. Pozbywasz się górnego i dolnego punktu, więc
>> tam pizza już nie styka się z talerzem, natomiast obie połówki
>> przesuwasz w stronę środka talerza o pół grubości cięcia - tym samym
>> odsuwając pozostałe punkty od krawędzi.
>
> No ale to przy zalozeniu ze wycinasz pasek - czyli ciec jest dwa, a nie
> jedno.


A nie tak ustaliliśmy? Zjadamy jakąś figurę, pasek, o ustalonej
szerokości dx.

Jeśli obchodzi nas minimalna długość trasy noża, rozwiązanie
pewnie będzie inne (wspominane już objechanie ciut ponad polowy
obwodu?)

pzdr
bartekltg

do góry

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

do góry

Dnia Tue, 21 May 2013 16:45:59 +0200 po głębokim namyśle bartekltg rzekł:

> W dniu 2013-05-21 12:00, Edek pisze:
>> Dnia Mon, 20 May 2013 16:13:45 +0200 po głębokim namyśle bartekltg
>> rzekł:
>>
>>> W dniu 2013-05-20 15:56, Michal Kleczek pisze:
>>>> On 2013-05-20 15:50, bartekltg wrote:
>>
>>>> Dla ustalonego dx porownujemy sposoby :-)
>>>>
>>>> Ale ok - moze byc dlugosc cięcia. Wtedy ciecie z krawedzi o dlugosci
>>>> min polowy obwodu jest najlepszym rozwiazaniem?
>>>
>>> Nie. Cięcie po średnicy. Raz wystarczy.
>>
>> Ja pizza ma dwa razy większą średnicę niż talerz to nie ma prawa
>> działać,
>> chyba że źle rozumiem opis.
>
> "pizzę, której rozmiar pokrywa się z rozmiarem talerza"
>
> Ja to rozumiem, jako dokładnie taki sam rozmiar.
>
> Zaakceptowanie przez autora rozwiązania z wygryzieniem minimalnej
> szerokośći po ponad polowie obwodu sugeruje, że rozumiem dobrze.

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.

--
Edek

do góry