A heuristic quasi-physical strategy for solving disks packing problem. (English) Zbl 1011.68829

Summary: By elaborately simulating the movement of the smooth elastic disks in the container in the physical world, we can find the solution for the disks packing problem. This problem is a classical one that arises in many scientific and engineering fields, and it is also one of the NP hard problems. Based on the simulated annealing, i.e., imitating the displacements of the objects under different temperature, the calculation speed is improved. The performance of the algorithm is demonstrated by actual calculations.


68U99 Computing methodologies and applications
68U20 Simulation (MSC2010)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI