In mathematics (and therefore in computer science), there is a category of problems that we call NP-Complete (NP-difficult), because their resolution is complex and generally requires a computation of a complexity of type kPN. With for example P as dimension of the space of the problem, N another dimension in the problem (number of samples ...). The documentation and research on these problems is abundant, indeed, this type of problem is the nightmare of mathematicians and computers as soon as N is growing. One of the typical examples of NP-Complete problems is that of the "commercial traveler". It is for this problem that we propose an algorithm of linear complexity to find at first sight the ideal solution, knowing that it is established that if an NP-complete problem has a solution (polynomial or linear), then all NP-Difficult problems can also be solved in polynomial or linear time. The proposed algorithm known as the Leafar spiral simply consists in superimposing on the "cloud" of points representing the cities, a Fibonacci spiral (spiral of increasing ration) placing the center of this spiral on the center. of gravity of the point cloud, then to rotate it according to a particular method. Therefore, the ideal path can be easily constructed by traversing the spiral and by "collecting" the points on either side, in the order of intersection with the perpendicular to the tangent to the spiral, provided that they are not closer to another spiral arm. This algorithm is recursive because, starting from 4 points (or more) fulfilling certain conditions of local density, one eventually attends the formation of a local "cluster", which needs to be treated itself as a sub-problem, with its own sub-spiral, then connected to the mother macro-spiral. Moreover, the algorithm contains an accretion step, which corresponds to the capture of one or more cities located in one arm of the spiral, by the path of an adjacent arm, when it is sufficiently close to it so that the capture optimizes the way. Thus, any set of seemingly chaotic points can be organized into a perfect "fractalization" according to the pattern of the Fibonacci spiral. The fields of application are very numerous: solving all the problems of graphs and combinatorics, cosmology, meteorology, operational calculation ... In fact, all the domains requiring complex calculations can benefit from this invention.
展开▼
