Cellular network assignment processor using minimum/maximum convergence technique
First Claim
1. A method for processing information comprising:
- assigning an address to each of a plurality of processing cells, said address including coordinates representing a particular set of input parameters for a multidimensional assignment problem, said input parameters originating from a plurality of sources wherein parameters from each of said sources correspond to one of said dimensions of said assignment problem, and wherein each of said processing cells receives, stores, and transmits information values;
storing one of said information values in each processing cell;
connecting each individual processing cell to every other processing cell whose assigned address has a conflict with the assigned address of said individual processing cell, said conflict defined as occurring when the assigned address of said individual processing cell has at least one common input parameter with the assigned address of another processing cell;
comparing the information values of processing cells in each of a plurality of groups of processing cells which are connected;
setting a flag in those processing cells which meet a preselected criteria of the compared information values for each group;
determining if a conflict exists between each flagged processing cell and other flagged processing cells;
unsetting the flag in those flagged processing cells which are in conflict with other flagged processing cells as determined by said determining step; and
performing the steps of comparing, setting flags, determining, and unsetting flags on one group of processing cells at a time until a flagged processing cell having no conflicts with other flagged processing cells is found for each group, whereby said flagged processing cells having no conflicts with other flagged processing cells together represent an optimal solution to said assignment problem.
2 Assignments
0 Petitions
Accused Products
Abstract
A cellular network assignment processor (10) for solving optimization problems utilizing a neural network architecture having a matrix of simple processing cells (12) that are highly interconnected in a regular structure. The cells (12) accept as input, costs in an assignment problem. The position of each cell (12) corresponds to the position of the cost in the associated constraint space of the assignment problem. Each cell (12) is capable of receiving, storing and transmitting cost values and is also capable of determining if it is the maximum or the minimum of cells (12) to which it'"'"'s connected. Operating on one row of cells (12) at a time the processor (10) determines if a conflict exists between selected connected cells (12) until a cell (12) with no conflict is found in each row. The end result is a chosen cell (12), in each row, the chosen cells (12) together representing a valid solution to the assignment problem.
-
Citations
14 Claims
-
1. A method for processing information comprising:
-
assigning an address to each of a plurality of processing cells, said address including coordinates representing a particular set of input parameters for a multidimensional assignment problem, said input parameters originating from a plurality of sources wherein parameters from each of said sources correspond to one of said dimensions of said assignment problem, and wherein each of said processing cells receives, stores, and transmits information values; storing one of said information values in each processing cell; connecting each individual processing cell to every other processing cell whose assigned address has a conflict with the assigned address of said individual processing cell, said conflict defined as occurring when the assigned address of said individual processing cell has at least one common input parameter with the assigned address of another processing cell; comparing the information values of processing cells in each of a plurality of groups of processing cells which are connected; setting a flag in those processing cells which meet a preselected criteria of the compared information values for each group; determining if a conflict exists between each flagged processing cell and other flagged processing cells; unsetting the flag in those flagged processing cells which are in conflict with other flagged processing cells as determined by said determining step; and performing the steps of comparing, setting flags, determining, and unsetting flags on one group of processing cells at a time until a flagged processing cell having no conflicts with other flagged processing cells is found for each group, whereby said flagged processing cells having no conflicts with other flagged processing cells together represent an optimal solution to said assignment problem. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. In an information processor having a plurality of processing cells, each of said cells for receiving, storing, and transmitting an information value, the improvement comprising:
-
means for assigning an address to each processing cell, said address including coordinates representing a particular set of input parameters for a multidimensional assignment problem, said input parameters originating from a plurality of sources wherein parameters from each of said sources correspond to one of said dimensions of said assignment problem; means for connecting each individual processing cell to every other processing cell whose assigned address has a conflict with the assigned address of said individual processing cell, said conflict defined as occurring when the assigned address of said individual processing cell has at least one common input parameter with the assigned address of another processing cell; means for comparing the information values of processing cells in each of a plurality of groups of processing cells which are connected; means, responsive to said comparing means, for setting a flag in those processing cells which meet a preselected criteria of the compared information values for each group; means for determining if a conflict exists between each flagged processing cell and other flagged processing cells; means, responsive to said determining means, for unsetting the flag in those flagged processing cells which are in conflict with other flagged processing cells; and means for controlling said comparing means, said flag setting means, said determining means, and said flag unsetting means, so that said comparing means, said flag setting means, said determining means, and said flag unsetting means all operate on one group of processing cells at a time, until a flagged processing cell having no conflicts with other flagged processing cells is found for each group, whereby said flagged processing cells having no conflicts with other flagged processing cells together represent an optimal solution to said assignment problem. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
Specification