|
|
 |
| |
|
|
|
Simulation DNA Algorithm of Set Covering Problem |
|
|
|
PP: 139-144 |
|
|
|
Author(s) |
|
|
|
Kang Zhou,
Jin Chen,
|
|
|
|
Abstract |
|
|
| Sticker model is imitated by using set, variable length vector and biochemistry operator instead of tube, memory strand and
biochemistry experiment for the first time. Batch separation operator and electrophoresis operator are first put forward based on DNA
algorithm of Set Covering Problem (SCP) based on sticker model. Expression way, calculation method and basic properties of variable
length vector and the two biochemistry operators are analyzed in detail according to the characteristics of sticker model. Simulation
DNA algorithm (SDA) of SCP, which can find out all optimization set coverings, is designed, where all feasible set coverings are
extracted by using batch separation operator and all optimization set coverings are extracted by using electrophoresis operator. Minimal
element and deriving element are first introduced. And minimal element contains a large amount of deriving elements, so the set of
batch separation operator can be simplified. Less-than relation is established to simplify the set of electrophoresis operator. Therefore
the use of ’minimal element’ and ’less-than’ makes SDA of SCP more effective and practical. Time complexity of SDA of SCP is
proved, and it shows that SDA of SCP is an effective algorithm to solve SCP. |
|
|
|
|
|
|
|
