Machine for the finding of an optimum passage
First Claim
Patent Images
1. A digital problem solving machine of optimizer type, for the seeking of an optimum path between an initial state and a final state for a system with a plurality of quantified variables, m in number, each of which can take on N values, comprising:
- a. means for setting in the sets of coordinate values of the variables corresponding to the initial and final states of the said system and for setting in the coordinate value sets corresponding to the values of the variables defining the system forbidden states, referred to as constraints;
b. a plurality of computation-and-memorization cells for handling digital contents, arranged to have their initial contents set by said setting-in means;
c. means providing for variation of the said contents in said cells by quantities appropriately defined as a function of the said constraints imposed on the system, starting from the set of initial values, the evolution of the values of the said contents by said variation being capable of consideration as simulating the propagation of a backward dummy wave which propagates step by step in a representative space receiving the said wave of the preceding adjacent points, with the exception of the points representative of constraints which do not propagate the wave, such variation for each constraint being termed processing the constraint;
d. means for reading the finally obtained cell contents after processing each constraint, ande. decision means using the results of the reading performed by said reading means and comparing them for selecting at least one of m+1 possible alternative succeeding states, as being the state corresponding to the first optimum elementary action, which transfers the system from the initial state to the said selected succeeding state, and which includes means for producing at least one reiteration comprising;
f. means for setting as the new initial state of the system the said succeeding state selected by said decision means,g. means for reinitializing the cells contents,h. means for commanding anew the operation of the means defined in foregoing subparagraphs c) to g), inclusive, for reprocessing of the cell contents, andi. means for memorizing the set of optimum elementary actions found at each processing, which set gives by successive approximation, the said optimum route going from the initial state to the final state,the said digital machine comprising the improvements constituted by the following characteristics;
the said computation-and-memorization cells are P in number, where P<
mN, and constitute an operator;
0 Assignments
0 Petitions
Accused Products
Abstract
The optimiser includes P cells for the computation and memorization of a content, the P contents simulating the deformation of a backward wave front which explores a plane representative of a concrete situation submitted to constraints.
The set of elementary optimum actions which define the optimum path between an initial state and a final state are found by iteration.
-
Citations
26 Claims
-
1. A digital problem solving machine of optimizer type, for the seeking of an optimum path between an initial state and a final state for a system with a plurality of quantified variables, m in number, each of which can take on N values, comprising:
-
a. means for setting in the sets of coordinate values of the variables corresponding to the initial and final states of the said system and for setting in the coordinate value sets corresponding to the values of the variables defining the system forbidden states, referred to as constraints; b. a plurality of computation-and-memorization cells for handling digital contents, arranged to have their initial contents set by said setting-in means; c. means providing for variation of the said contents in said cells by quantities appropriately defined as a function of the said constraints imposed on the system, starting from the set of initial values, the evolution of the values of the said contents by said variation being capable of consideration as simulating the propagation of a backward dummy wave which propagates step by step in a representative space receiving the said wave of the preceding adjacent points, with the exception of the points representative of constraints which do not propagate the wave, such variation for each constraint being termed processing the constraint; d. means for reading the finally obtained cell contents after processing each constraint, and e. decision means using the results of the reading performed by said reading means and comparing them for selecting at least one of m+1 possible alternative succeeding states, as being the state corresponding to the first optimum elementary action, which transfers the system from the initial state to the said selected succeeding state, and which includes means for producing at least one reiteration comprising; f. means for setting as the new initial state of the system the said succeeding state selected by said decision means, g. means for reinitializing the cells contents, h. means for commanding anew the operation of the means defined in foregoing subparagraphs c) to g), inclusive, for reprocessing of the cell contents, and i. means for memorizing the set of optimum elementary actions found at each processing, which set gives by successive approximation, the said optimum route going from the initial state to the final state, the said digital machine comprising the improvements constituted by the following characteristics; the said computation-and-memorization cells are P in number, where P<
mN, and constitute an operator; - View Dependent Claims (3, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
2. each cell includes means for incrementation of its contents controlled by the aforesaid means for the setting in of coordinate values defining each constraint and includes means for sequentially delivering the said coordinate values of the constraints to the said incrementation means, the processing performed by the said operator thus being performed from constraint to constraint, and
the contents of each cell after processing of a constraint represents the difference between the number of steps performed on any one of the variables to pass the said constraint and the dummy number of steps which would lead to the same situation if the said constraint did not exist, so that the set of P contents can then be considered as representative of the difference expressed as the number of steps between the front of the said backward dummy wave and the front of the reference wave propagating in the same way as the dummy wave but not being disturbed by the said constraints.
Specification