Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-02-02
2003-06-17
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S200000, C701S202000, C340S990000
Reexamination Certificate
active
06581002
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an information processing method and an information processing apparatus that are suitable when used for combination optimization problems such as traveling salesman problem, for example.
2. Description of the Related Art
Here is taken a problem in which the number N of its factors can be defined, as a problem for which a calculation should be executed. The problem for finding a route shortening the length of each line connecting points among routes once passing all of a plurality of points given on a two-dimensional plane is typical one of such problems, and the number of given points is represented by N. Considering these points as positions of cities, the problem of finding the shortest route is sometimes called a traveling salesman problem.
In general, in case that the calculation time required for executing a solution by naive algorithm increases by power of N, the problem is called a polynominal problem. On the other hand, in case that the calculation time increases exponentially of N, the increase of the calculation time with the increase of N is remarkable, and it is difficult to execute numerical calculation using a conventional computer. The class containing this problem is called NP (nondeterministic polynominal) complete problem. The complete NP problem has the possibility of becoming a polynominal problem if a dexterous algorithm is found, and vigorous researches are being made. It is important that, once any dexterous algorithm is found, all of the problems known as NP complete problems are shown to become polynominal problems.
The subject of the widest researches as an NP complete problem is the traveling salesman problem mentioned above. An example thereof is schematically shown in FIG.
1
. In
FIG. 1
, white points represent positions of cities, and the set of lines each connecting two cities is the shortest route. To solve this kind of problem, various approximate methods have heretofore been proposed, such as those using neural networks or spin glass.
Recently, a new approximate method using the concept of renormalization group was found by Y. Usami and Y. Kano regarding the traveling salesman problem and has been remarked (Phys. Rev. Lett. 75, 1683 (1995)). The renormalization group is a method that has performed its power in analyses like phase transition, and it is a basic concept of modern physics.
FIG. 2
schematically shows this method. In
FIG. 2
, black points represent positions of cities. This method divides a given distribution of cities into some regions called frames, and executes calculation for each frame to obtain an approximate solution. In the example of
FIG. 2
, a distribution is divided into four frames.
The approximate method using renormalization group is certainly excellent in capability of obtaining a solution more quickly than conventional methods. However, since it executes calculation for fixed frames, approximation accuracy cannot be increased so much, and it is difficult to realize an apparatus for execution and processing by a physical system as an exclusive device.
OBJECT AND SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide an information processing method and an information processing apparatus capable of quickly obtaining excellent approximate solutions of a combinatorial optimization problem such as traveling salesman problem and enabling realization of the processing apparatus as massively parallel exclusive devices.
Toward attainment of the above-mentioned object, the Inventor developed the concept of the above-indicated renormalization group, then contrived the use of a new renormalization transformation using movable frames instead of fixed frames and found the possibility of using this technique to obtain approximate solutions of combinatorial optimization problems such as traveling salesman problem with a high accuracy and at a high speed, which is just the present invention.
According to the first aspect of the invention, there is provided an information processing method comprising: preparing an information carrier corresponding to a distribution of a plurality of points given on an n-dimensional space (where n is an integer not smaller than 2); and using time development and time reversal of the information carrier to process the information.
According to the second aspect of the invention, there is provided an information processing apparatus configured to prepare an information carrier corresponding to the distribution of a plurality of points given on an n-dimensional space (where n is an integer not smaller than 2), and to use time development and time reversal of the information carrier for processing the information.
In the present invention, global nature of information given on an n-dimensional space, in particular, is detected by preparing an information carrier corresponding to a distribution of a plurality of given points and using the time development and time reversal of the information carrier.
In the present invention, the information carrier may be the density of particles (such as atoms or molecules) corresponding to a distribution of a plurality of given points, and its diffusion process may be used as a time change (time development). Alternatively, the information carrier may be an optical intensity corresponding to a distribution of a plurality of given points, and its defocusing process may be used as the time change (time development).
In a typical example of the present invention, for a problem of finding a route minimizing the total length of lines connecting points from routes once passing all points given on the n-dimensional plane (traveling salesman problem), an information carrier corresponding to a distribution of the given points is prepared, and time reversal of the information carrier is used.
Information processing according to the invention is such that all of its processes can be executed with a computer (or IC), and so may be done. However, physical processes, such as defocusing process and diffusion process, can be executed by using an existent physical system.
According to the invention having the above-summarized structure, good approximate solutions of combinatorial optimization problems such as traveling salesman problem can be calculated at a high speed by thinning movable frames of renormalization transformation while moving them to meet with a given distribution of a plurality of points on an n-dimensional space, such as distribution of cities. Since the renormalization transformation can be executed by using time reversal of a simple physical phenomenon such as physical process like diffusion process or defocusing process, it can be realized in form of massively parallel exclusive devices.
REFERENCES:
patent: 4962458 (1990-10-01), Verstraete
patent: 4984168 (1991-01-01), Neukrichner et al.
patent: 5036471 (1991-07-01), Tamura et al.
patent: 5255349 (1993-10-01), Thakoor et al.
patent: 5272638 (1993-12-01), Martin et al.
patent: 5848402 (1998-12-01), Pao et al.
patent: 5938720 (1999-08-01), Tamai
patent: 6023680 (2000-02-01), Wooster et al.
Papadimitriou et al., “On the Approximability of the Traveling Salesman Problem”, Proceedings of the thirty-second annual ACM symposium on Theory of computing, May 1999, pp. 126-133.*
Papadimitriou et al., “Some Complexity Results for the Traveling Salesman Problem”, Proceedings of the eighth annual ACM symposium on Theory of computing, May 1976, pp. 1-9.*
Penna, T.J.P., “Traveling salesman problem and Tsallis statistics”, Physical Review E, Third Series, vol. 51, No. 1, Jan. 1995, pp. R1-R3.*
Yoshiyuki et al., “New Method of Solving the Traveling Salesman Problem Based on Real Space Renormalization Theory”, Physical Review Letters, vol. 75, No. 9, Aug. 28, 1995, pp. 1683-1686.*
Fox et al., “Load Balancing Loosely Synchronous Problems with a Neural Network”, Proceedings of the third conference on Hypercube concurrent computers and applications, vol. 1, Feb. 1988, pp. 241-278.*
Garfinkel et al., “The Bottleneck Traveling
Frommer William S.
Frommer & Lawrence & Haug LLP
Gibson Eric
Simon Darren M.
Sony Corporation
LandOfFree
Information processing method and information processing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information processing method and information processing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information processing method and information processing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3109688