:   .., .., ..
:  
:  87
:  
:  2020
:   .., .., .. // . 87. .: , 2020. .47-66. DOI: https://doi.org/10.25728/ubs.2020.87.3
:   , , - , , ,
(.):  unequal balls packing, three dimensional space, optical-geometric approach, billiard simulation method, computational algorithm, non-Euclidean metric
:   : , . NP-. , - . , . , , . , , , , . , , - , . . 3D- .
(.):  The article is devoted to the construction of optimal packings of unequal balls in a three-dimensional closed set. It is required to find such an arrangement of a fixed number of balls that their radii are maximal. This problem is NP-hard. To solve it, we propose a computational algorithm based on the optical-geometric approach and billiard modeling. Using this approach allows us to solve packing problems not only in Euclidean, but also in other metric spaces. We consider a problem in which, instead of the distance between the centers of the balls, the optimization parameter is the minimum traveling time between them. Such statements often arise if we consider problems of protecting the perimeter, in which the time of movement of the "intruder" to the protected object plays a much more significant role than the distance traveled, as well as in logistics, where the delivery time is paramount important. The algorithm was implemented, and computational experiments were performed. Both convex and non-convex sets were selected as container sets. The results of calculations allow us to positively assess the efficiency and effectiveness of the proposed algorithm. We performed a 3-D visualization of the results.

PDF

: 1647, : 290, : 4.


© 2007.