×

Machine for the finding of an optimum passage

  • US 3,974,481 A
  • Filed: 05/14/1974
  • Issued: 08/10/1976
  • Est. Priority Date: 05/14/1973
  • Status: Expired due to Term
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;

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×