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

Huang, Wenqi; Kang, Yan

Simulation Modelling Practice and Theory 10, No. 3-4, 195-207 (2002).

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.

MSC:

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.)

Keywords:

packing problem; NP hard; simulated annealing; quasi-physical method