Balení kruhů v kruhu

Balení kruhem v kruhu je 2D problém s balením, jehož cílem je sbalit jednotkové kruhy do nejmenšího možného kruhu .

[jeden]

Historie

Tento problém balení byl stanoven a studován v 60. letech 20. století. Kravitz v roce 1967 publikoval balení až 19 kruhů bez analýzy optimálnosti řešení [2] . O rok později Graham dokázal, že nalezená řešení s počtem kruhů do 7 jsou optimální [3] , a Pirl nezávisle na něm, že optimální jsou obaly do 10 kruhů [4] . Až v roce 1994 Melissen prokázal optimálnost řešení s 11 kruhy [5] . Fodor v letech 1999 až 2003 ukázal, že řešení s 12 [6] , 13 [7] a 19 [8] kruhy jsou optimální.

Graham et al . Poslední přehled problému a přibližná řešení do 2989 kruhů (červen 2014) podal Eckard Specht [10] .

Tabulka prvních 20 balíčků

Minimální řešení (pokud existuje několik minimálních řešení, zobrazí se pouze jedna možnost):

Počet jednotkových kruhů Poloměr ohraničující kružnice Hustota Optimalita Diagram
jeden jeden 1,0000 Triviálně optimální.
2 2 0,5000 Triviálně optimální.
3 ≈ 2,154... 0,6466... Triviálně optimální.
čtyři ≈ 2,414... 0,6864... Triviálně optimální.
5 ≈ 2,701... 0,6854... Triviálně optimální. Optimalitu prokázal také Graham v roce 1968 [3]
6 3 0,6667... Triviálně optimální. Optimalitu prokázal také Graham v roce 1968 [3]
7 3 0,7778... Triviálně optimální.
osm ≈ 3,304... 0,7328... Optimalizace ověřená Pirlem v roce 1969 [4]
9 ≈ 3,613... 0,6895... Optimalizace ověřená Pirlem v roce 1969 [4]
deset 3,813... 0,6878... Optimalizace ověřená Pirlem v roce 1969 [4]
jedenáct ≈ 3,923... 0,7148... Optimalitu prokázal Melissen v roce 1994 [5]
12 4,029... 0,7392... Prokázaná optimalita Fodorem v roce 2000 [6]
13 ≈4,236... 0,7245... Prokázaná optimalita Fodorem v roce 2003 [7]
čtrnáct 4,328... 0,7474... hypoteticky optimální. [9]
patnáct ≈ 4,521... 0,7339... hypoteticky optimální. [9]
16 4,615... 0,7512... hypoteticky optimální. [9]
17 4,792... 0,7403... hypoteticky optimální. [9]
osmnáct ≈ 4,863... 0,7611... hypoteticky optimální. [9]
19 ≈ 4,863... 0,8034... Optimalitu prokázal Fodor v roce 1999 [8]
dvacet 5,122... 0,7623... hypoteticky optimální. [9]

Viz také

Poznámky

  1. ↑ Erich Friedman, Kruhy v kruzích na Erichově balicím centru (odkaz není k dispozici) . Získáno 7. června 2016. Archivováno z originálu dne 18. března 2020. 
  2. ↑ Kravitz, 1967 .
  3. ↑ 1 2 3 Graham, 1968 .
  4. ↑ 1 2 3 4 Pirl, 1969 .
  5. ↑ 1 2 Melissen, 1994 .
  6. ↑ 12 Fodor, 2000 .
  7. ↑ 12 Fodor , 2003 .
  8. ↑ 12 Fodor , 1999 .
  9. ↑ 1 2 3 4 5 6 7 Graham, 1998 .
  10. ↑ Eckard Specht: Nejznámější uspořádání stejných kruhů v kruhu (kompletní do N = 2600). Archivováno 4. března 2016 na Wayback Machine packomania.com.

Literatura


Odkazy