Linked Markovian quantum tunnels: An approximation technique for solving the bin packing problem

摘要

According to quantum mechanics there exists a small probability for a particle to pass through a barrier. The principle behind this assertion is known as Quantum Tunnelling effect because the escaping particle has to, somehow, dig a passage to the other side of the barrier. When placed in a proper context, this nonlocal phenomenon can be a powerful concept for solving combinatorial problems. The strategy used consists in simulating quantum tunnels aiming to find approximate solutions for a particular optimum of a combinatorial cost function. In this paper we present such a scheme, composed by a finite number of linked Markov Chains. Each Markov Chain is connected with its adjacent by a link that mimics a quantum tunnel. The numerical practicality of the model is demonstrated using the traditional one-dimensional Bin Packing Problem. (C) 2017 Elsevier B.V. All rights reserved.