W dniu 2013-05-19 17:51, Edek pisze:
> 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?).
>
> O ile mnie zadanie rano stanowczo przerosło i nawet nie
> oczekuję żadnych konkretnych algorytmicznych rozwiązań,
> jaka jest złożoność tego problemu? Powiedzmy, że boczek
> ma przekrój wypukły.

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


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.

Czytałem to jakiś czas temu i najprostszy algorytm miał
swoją cześć 'wykładniczą' pod postacią przeszukiwania
możliwych postaci "grafu kontaktów".

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.


BTW. podobny problem występuje z serem lub wędliną
na kanapce. Tam najlepiej sprawdza się krojenie
i przestawianie małych kawałków sera aż do uzyskania
zadowalającej dokładności.
;)

pzdr
bartekltg