Search for Hamiltonian paths using a membrane system in polynomial time
The creation of algorithms within the framework of a classical algorithmic model ( Turing and Post machines , normal Markov algorithms , Minsky counter machines , etc.) can be safely attributed to abnormal programming due to the exceptional minimality of the expressive means of these models. No exception to this rule is such a relatively new algorithmic model, such as membrane systems or P-systems, invented by the Romanian scientist George Paun a little more than ten years ago. 
The purpose of this innovation was to study the computational capabilities of cell-like structures (meaning biological cells), and in general all this activity was inspired by Adleman ’s famous experience in solving the problem of finding the Hamiltonian path using DNA calculations. Strange as it may seem, but this topic is dedicated just to solving (unfortunately, virtual) the same problem, but with the help of a simple membrane system. So, under the cut the reader will find 1) a brief description of what membrane systems are; 2) how to “program” such “iron”; 3) membrane algorithm for solving the Hamiltonian path problem, which has a polynomial execution time.
The membrane system is primarily a system of nested membranes. In addition to other membranes, inside each membrane, there may also be some multiset of some objects, most often symbols. A multiset is a set in which elements can be repeated, but the order of the elements is not at all important.
Thus, the membrane system can informally be thought of as a bag in which there are cards with letters and other bags. However, the situation is not prohibited when the membrane (bag) does not contain either symbols or other membranes, or both of them (empty bag). And yet, the characters can even be outside the outermost membrane, which is called the skin membrane.
Each membrane can be marked with a special symbol (membrane identifier), and the labels do not need to be unique.
In fact, the membrane system is a tree structure in which the role of the root is played by either the medium or the skin membrane. Membrane A is a subsidiary of B, if A is directly embedded in B. Membrane systems are usually written as strings, in which the membranes themselves are indicated by brackets (an important note is that the order of objects within brackets plays absolutely no role). The above system, for example, can be written as follows: [ 0 baha [ 1 I] 1 Hrb [ 2 lvoe] 2 ra] 0 or so [ 0 ahra [ 2 ovel] 2 Hrbb [ 1 I] 1 a] 0 or in general like this:
[ 0 [ 1 I] 1 [ 2 love] 2 Habrahabr] 0 ...
Any membrane system is dynamic, i.e. changes with time, while talking about its evolution. The laws (rules) of evolution are determined by the developer of the system, and these rules are its integral part. In the literature devoted to membrane calculations, there are many types of such rules. For our purposes, only three basic types of rules will suffice: the evolution of intramembrane multisets; the transfer of characters to the outside; membrane division.
The evolution of multisets is described by rules of the form A → B, where A and B are two lines representing some subsets of characters (therefore, the order of the characters in these lines is not important). For example, aab → bc. The meaning of such rules is that if a membrane has a combination of symbols A, then it must be replaced by a combination of B. There are contraindications to nuances. First, the principle of maximum parallelism is in effect - all substitutions that can be applied must be applied. Secondly, if there are several competing rules, then the choice of one of them is performed nondeterministic, i.e. by chance. Thirdly, sometimes, to resolve such conflicts on a set of rules, priority is introduced, i.e partial order relation. By the way, membrane systems with priority rules are just algorithmically universal models compatible with the Turing machine (but we will not use priority).
Symbols in the process of evolution of the system can be transferred between the membranes, in particular, the output of symbols from the membrane to the surrounding region is described by the following rule [A] → [] B. For example, [ab] → c. The meaning of this rule is that if in some membrane there is a combination of symbols A, then it is removed from the membrane and turns into a combination of B.
Finally, the most interesting operation (allowing to implement algorithms, such as described below) is the division of membranes. The rule of dividing the membrane has the form [a] → [B] [C] (here a is some symbol, B and C are strings). For example, [x] → [aa] [b]. The meaning of this operation: if the symbol a is formed inside the membrane, then this membrane is divided (first all the rules of the previous two types are fulfilled) with two, in the first the a is replaced with the combination B, in the second with C.
Note that each rule, in principle, can be tied to a specific membrane (with a given label), however, for our purposes such a complication of the model, fortunately, is not required.
It is assumed that on each clock (discrete time) in the system, all those rules that can be executed at a given time are executed. Coupled with algorithmic universality, this means that membrane systems can be considered as a parallel computational model. Moreover, the degree of parallelism in such a model is dynamic - the more objects in the system, the more (on average) the number of simultaneously triggered rules. This membrane systems favorably differ from, for example, parallel Turing machines.
Let a directed graph G be given and a starting vertex given in this graph. We will move along the edges of the graph according to their directions (you cannot walk against the arrow of the arrow). If there is such a route around the graph that includes vertices exactly once, then this route is called the Hamiltonian path. If from the last vertex of the Hamiltonian path we can go to the starting vertex, then this path is called the Hamiltonian cycle. Actually, the problem considered below is formulated as follows: is there a path in the given graph G of Hamiltonians starting from the u -th vertex? Thus, the solution to the problem is only one bit of information - the path exists (1) or does not exist (0). This is a classic NP-complete problem (although, most often, it is considered as the problem of finding the Hamiltonian cycle), respectively, not a single polynomial algorithm for its solution is currently known.
We number all the vertices of the graph from 1 to n. Without limiting generality of reasoning (such a standardexcuse is an excuse), we will assume that the starting vertex is the first. 
The graph itself will be specified using a set (string) of characters corresponding to the arcs of the graph. Each arc u → v is given by a special symbol of the form A uv . Note that A uv is one character (the image of which is composed of several other characters)! For example, the graph in the figure on the right is given by the character string A = A 13 A 21 A 32 A 24 A 43 . By the way, this graph contains the only Hamiltonian path starting from the first vertex: 1 → 3 → 2 → 4.
The idea of ​​the algorithm is as follows. At the first step, we create (using the division operation) sufficiently large identical membranes in which the conditions of the problem are coded (ie, the graph G). At the second step, a random Hamiltonian path search is performed inside each membrane — a maximum of n-1 iteration is done; at each iteration, an attempt is made to extend the current path by selecting a random outgoing arc from the current vertex. If the attempt is unsuccessful, the process of evolution within this membrane stops. In principle, in this case it would be possible to remove the entire membrane, but we will not be engaged in such nonsense (writing the garbage collector) in order not to clutter up the main idea. Due to the fact that the number of membranes in which the search is performed is quite large, the probability that there is a Hamiltonian path in the graph, and the algorithm did not find it, can be quite small (more precisely, we can control this probability).
Algorithm input data: initially there is only one membrane in which a) the character set A is located, which is a graph in which we are looking for a path from the first vertex; b) the list of unvisited vertices given by the symbols U 2 , U 3 , ..., U n (the first vertex is considered to have already been visited); c) division counter D T. For example, for the graph shown above, the original membrane has the form [D T U 2 U 3 U 3 A 13 A 21 A 32 A 24 A 43 ].
The first step is to create the required number of identical membranes. This is achieved using the following rule:
The application of this rule leads to a doubling of each membrane, at the same time, the division counter decreases by one. It is easy to guess that the number of membranes will increase exponentially as a result - 1, 2, 4, 8, etc. After T iterations, we will have 2 T identical membranes, in which the division counter will be equal to D 0 . The appearance of this symbol in the membrane triggers the second step of the algorithm — the construction of the Hamiltonian path. This step is implemented by the following four rules.
Important note: when we speak, for example, about rule 3, we mean a whole set of rules for all possible symbols X i and A ij . Those. Under “as if” rule 3, n 2 “real” rules are actually hidden. Now a brief description of what these four rules do. Rule 2: the start of the second step of the algorithm, the current vertex is the first (symbol X 1 ), the symbol L 1 means that the length of the current path is still equal to one. Rule 3: being at the vertex labeled X i , we make a random transition along some arc emanating from this vertex. Rule 4: if the vertex we went to has not been visited yet, then the transition is accepted. Rule 5: change the current vertex and increase by one the length of the current path.
If, as a result of applying rule number 3, we are at the top that has already been visited before, then this membrane will no longer evolve, because none of the rules apply to its character set. This membrane is out of luck. Nothing means lucky others! Unless of course the graph has a Hamiltonian cycle. If there is no such cycle, then in no more than n iterations of the second step, the whole life in our membrane system will freeze. And what happens if a membrane manages to go all the way? In this case, the L n symbol will be generated in this membrane, which in essence means that a path with a length of n vertices has been traversed, and no vertex has been visited twice. This means that the appearance of such a symbol is a signal of a successful search. To simplify the recognition of the answer, add the last rule to the system.
Here S stands for success (from success). So, if after T + n iterations of the algorithm in the environment surrounding our membranes, at least one symbol S appears, then the graph is Hamiltonian, if not, then with some probability P this graph is non-Hamiltonian (we could not be lucky, and despite that the graph is still the desired path, not a single membrane has found it). It was the turn to deal with this probability, and at the same time with the as yet undefined parameter T.
Now we have to do some math work. Consider the worst case of a failed search, when there is only one Hamiltonian path in the graph. It is more or less obvious that with a random selection of outgoing arcs, the probability of finding this path (for a single membrane) is greater than q = 1 / n n , since at each iteration, we have a maximum of n outgoing arcs, of which at least one enters the desired path. Total iterations n-1, for simplicity of the formula, we will increase this number to n. Then the probability p of not detecting the same path is less than p = 1-1 / n n . It seems that this value is suspiciously similar to one, but still there is a slight gap, which we will use. Recall that we have not one membrane, but immediately M = 2 T of such membranes. And we are interested in the probability that none of them will find our way. We have a series of M experiments performed according to the Bernoulli scheme, with the probability of success q and failure p. It is known that the number of successes in such a series obeys the binomial distribution, in particular, the probability that there will not be a single success (epic fail) is equal to P = p M. And here's a solemn moment - choose M to be equal to Kn n , where K is some positive parameter. Then, P = (1-1 / M) KM . And since M is very large even for small values ​​of n, then the second remarkable limit can be applied and it turns out that P is well described by the formula P = e -K . For example, for K = 100, the probability of not detecting the existing Hamiltonian path will be approximately P = 10 -44 , i.e. This event (epic fail) is almost unbelievable. Yes, this is all fine, but after all, M (the number of membranes) also turns out to be not small. But, remember that M = 2 T , and T is the very parameter that controls the first step of the algorithm. So, from the relation 2 T = Kn n it is easily deduced that T = O (nlog 2 n). And this, in turn, just means that the total complexity of the entire algorithm is linear-logarithmic, and therefore polynomial . What was required to show! At the same time, the probability of incorrect operation of the algorithm is controlled by the parameter K, which practically does not affect the complexity of the algorithm.
First, if we fix some value of n and from this value 1) we calculate T; 2) form a set of rules, as described above, then the membrane system constructed in this way will solve the problem of finding the Hamiltonian path in any graph whose number of vertices does not exceed n. Those. such a system is in fact an algorithm (program), and not a scheme for solving a single instance of the problem. In this case, the alphabet of this system will be polynomial with respect to n.
Secondly, if for a moment we break away from the magic phrase “a polynomial algorithm for solving an NP-complete problem”, then it will immediately become obvious that we simply replaced the temporal exponentiality with the spatial, because each membrane needs its own placeunder the sun - a set of bytes in computer memory or physical volume, if the membranes are realized by cells or molecules (as in the experience of Adleman). If we assume that one membrane occupies a volume equal to the volume of a hydrogen atom (the border is unattainable) and put K = 1, then the total volume of the membranes after the first step of the algorithm for a small graph of 100 vertices will be about 10 900 volumes of the Earth that this number exceeds the estimated volume of the universe). So, we did not manage to find free cakes. But we got acquainted with the new algorithmic model and with another very nontrivial (I’m not afraid of this word - abnormal) “programming” method.
Thank you all for your attention!
The purpose of this innovation was to study the computational capabilities of cell-like structures (meaning biological cells), and in general all this activity was inspired by Adleman ’s famous experience in solving the problem of finding the Hamiltonian path using DNA calculations. Strange as it may seem, but this topic is dedicated just to solving (unfortunately, virtual) the same problem, but with the help of a simple membrane system. So, under the cut the reader will find 1) a brief description of what membrane systems are; 2) how to “program” such “iron”; 3) membrane algorithm for solving the Hamiltonian path problem, which has a polynomial execution time.Membrane system
The membrane system is primarily a system of nested membranes. In addition to other membranes, inside each membrane, there may also be some multiset of some objects, most often symbols. A multiset is a set in which elements can be repeated, but the order of the elements is not at all important.
Thus, the membrane system can informally be thought of as a bag in which there are cards with letters and other bags. However, the situation is not prohibited when the membrane (bag) does not contain either symbols or other membranes, or both of them (empty bag). And yet, the characters can even be outside the outermost membrane, which is called the skin membrane.
Each membrane can be marked with a special symbol (membrane identifier), and the labels do not need to be unique.
In fact, the membrane system is a tree structure in which the role of the root is played by either the medium or the skin membrane. Membrane A is a subsidiary of B, if A is directly embedded in B. Membrane systems are usually written as strings, in which the membranes themselves are indicated by brackets (an important note is that the order of objects within brackets plays absolutely no role). The above system, for example, can be written as follows: [ 0 baha [ 1 I] 1 Hrb [ 2 lvoe] 2 ra] 0 or so [ 0 ahra [ 2 ovel] 2 Hrbb [ 1 I] 1 a] 0 or in general like this:
[ 0 [ 1 I] 1 [ 2 love] 2 Habrahabr] 0 ...
Evolution of the membrane system
Any membrane system is dynamic, i.e. changes with time, while talking about its evolution. The laws (rules) of evolution are determined by the developer of the system, and these rules are its integral part. In the literature devoted to membrane calculations, there are many types of such rules. For our purposes, only three basic types of rules will suffice: the evolution of intramembrane multisets; the transfer of characters to the outside; membrane division.
The evolution of multisets is described by rules of the form A → B, where A and B are two lines representing some subsets of characters (therefore, the order of the characters in these lines is not important). For example, aab → bc. The meaning of such rules is that if a membrane has a combination of symbols A, then it must be replaced by a combination of B. There are Symbols in the process of evolution of the system can be transferred between the membranes, in particular, the output of symbols from the membrane to the surrounding region is described by the following rule [A] → [] B. For example, [ab] → c. The meaning of this rule is that if in some membrane there is a combination of symbols A, then it is removed from the membrane and turns into a combination of B. Finally, the most interesting operation (allowing to implement algorithms, such as described below) is the division of membranes. The rule of dividing the membrane has the form [a] → [B] [C] (here a is some symbol, B and C are strings). For example, [x] → [aa] [b]. The meaning of this operation: if the symbol a is formed inside the membrane, then this membrane is divided (first all the rules of the previous two types are fulfilled) with two, in the first the a is replaced with the combination B, in the second with C.Note that each rule, in principle, can be tied to a specific membrane (with a given label), however, for our purposes such a complication of the model, fortunately, is not required.
It is assumed that on each clock (discrete time) in the system, all those rules that can be executed at a given time are executed. Coupled with algorithmic universality, this means that membrane systems can be considered as a parallel computational model. Moreover, the degree of parallelism in such a model is dynamic - the more objects in the system, the more (on average) the number of simultaneously triggered rules. This membrane systems favorably differ from, for example, parallel Turing machines.
Hamilton path problem
Let a directed graph G be given and a starting vertex given in this graph. We will move along the edges of the graph according to their directions (you cannot walk against the arrow of the arrow). If there is such a route around the graph that includes vertices exactly once, then this route is called the Hamiltonian path. If from the last vertex of the Hamiltonian path we can go to the starting vertex, then this path is called the Hamiltonian cycle. Actually, the problem considered below is formulated as follows: is there a path in the given graph G of Hamiltonians starting from the u -th vertex? Thus, the solution to the problem is only one bit of information - the path exists (1) or does not exist (0). This is a classic NP-complete problem (although, most often, it is considered as the problem of finding the Hamiltonian cycle), respectively, not a single polynomial algorithm for its solution is currently known.
We number all the vertices of the graph from 1 to n. Without limiting generality of reasoning (such a standard
The graph itself will be specified using a set (string) of characters corresponding to the arcs of the graph. Each arc u → v is given by a special symbol of the form A uv . Note that A uv is one character (the image of which is composed of several other characters)! For example, the graph in the figure on the right is given by the character string A = A 13 A 21 A 32 A 24 A 43 . By the way, this graph contains the only Hamiltonian path starting from the first vertex: 1 → 3 → 2 → 4.Membrane algorithm
The idea of ​​the algorithm is as follows. At the first step, we create (using the division operation) sufficiently large identical membranes in which the conditions of the problem are coded (ie, the graph G). At the second step, a random Hamiltonian path search is performed inside each membrane — a maximum of n-1 iteration is done; at each iteration, an attempt is made to extend the current path by selecting a random outgoing arc from the current vertex. If the attempt is unsuccessful, the process of evolution within this membrane stops. In principle, in this case it would be possible to remove the entire membrane, but we will not be engaged in such nonsense (writing the garbage collector) in order not to clutter up the main idea. Due to the fact that the number of membranes in which the search is performed is quite large, the probability that there is a Hamiltonian path in the graph, and the algorithm did not find it, can be quite small (more precisely, we can control this probability).
Algorithm input data: initially there is only one membrane in which a) the character set A is located, which is a graph in which we are looking for a path from the first vertex; b) the list of unvisited vertices given by the symbols U 2 , U 3 , ..., U n (the first vertex is considered to have already been visited); c) division counter D T. For example, for the graph shown above, the original membrane has the form [D T U 2 U 3 U 3 A 13 A 21 A 32 A 24 A 43 ].
The first step is to create the required number of identical membranes. This is achieved using the following rule:
| 1: [D i ] → [D i-1 ] [D i-1 ], i = T, ..., 1 |
The application of this rule leads to a doubling of each membrane, at the same time, the division counter decreases by one. It is easy to guess that the number of membranes will increase exponentially as a result - 1, 2, 4, 8, etc. After T iterations, we will have 2 T identical membranes, in which the division counter will be equal to D 0 . The appearance of this symbol in the membrane triggers the second step of the algorithm — the construction of the Hamiltonian path. This step is implemented by the following four rules.
| 2: D 0 → X 1 L 1 3: X i A ij → Y j , i, j = 1, ..., n 4: Y j U j → Z j , j = 1, ..., n 5: Z j L k → X j L k + 1 , j = 1, ..., n, k = 1, ..., n-1 |
Important note: when we speak, for example, about rule 3, we mean a whole set of rules for all possible symbols X i and A ij . Those. Under “as if” rule 3, n 2 “real” rules are actually hidden. Now a brief description of what these four rules do. Rule 2: the start of the second step of the algorithm, the current vertex is the first (symbol X 1 ), the symbol L 1 means that the length of the current path is still equal to one. Rule 3: being at the vertex labeled X i , we make a random transition along some arc emanating from this vertex. Rule 4: if the vertex we went to has not been visited yet, then the transition is accepted. Rule 5: change the current vertex and increase by one the length of the current path.
If, as a result of applying rule number 3, we are at the top that has already been visited before, then this membrane will no longer evolve, because none of the rules apply to its character set. This membrane is out of luck. Nothing means lucky others! Unless of course the graph has a Hamiltonian cycle. If there is no such cycle, then in no more than n iterations of the second step, the whole life in our membrane system will freeze. And what happens if a membrane manages to go all the way? In this case, the L n symbol will be generated in this membrane, which in essence means that a path with a length of n vertices has been traversed, and no vertex has been visited twice. This means that the appearance of such a symbol is a signal of a successful search. To simplify the recognition of the answer, add the last rule to the system.
| 6: [L n ] → [] S |
Here S stands for success (from success). So, if after T + n iterations of the algorithm in the environment surrounding our membranes, at least one symbol S appears, then the graph is Hamiltonian, if not, then with some probability P this graph is non-Hamiltonian (we could not be lucky, and despite that the graph is still the desired path, not a single membrane has found it). It was the turn to deal with this probability, and at the same time with the as yet undefined parameter T.
Epic fail and his probability
Now we have to do some math work. Consider the worst case of a failed search, when there is only one Hamiltonian path in the graph. It is more or less obvious that with a random selection of outgoing arcs, the probability of finding this path (for a single membrane) is greater than q = 1 / n n , since at each iteration, we have a maximum of n outgoing arcs, of which at least one enters the desired path. Total iterations n-1, for simplicity of the formula, we will increase this number to n. Then the probability p of not detecting the same path is less than p = 1-1 / n n . It seems that this value is suspiciously similar to one, but still there is a slight gap, which we will use. Recall that we have not one membrane, but immediately M = 2 T of such membranes. And we are interested in the probability that none of them will find our way. We have a series of M experiments performed according to the Bernoulli scheme, with the probability of success q and failure p. It is known that the number of successes in such a series obeys the binomial distribution, in particular, the probability that there will not be a single success (epic fail) is equal to P = p M. And here's a solemn moment - choose M to be equal to Kn n , where K is some positive parameter. Then, P = (1-1 / M) KM . And since M is very large even for small values ​​of n, then the second remarkable limit can be applied and it turns out that P is well described by the formula P = e -K . For example, for K = 100, the probability of not detecting the existing Hamiltonian path will be approximately P = 10 -44 , i.e. This event (epic fail) is almost unbelievable. Yes, this is all fine, but after all, M (the number of membranes) also turns out to be not small. But, remember that M = 2 T , and T is the very parameter that controls the first step of the algorithm. So, from the relation 2 T = Kn n it is easily deduced that T = O (nlog 2 n). And this, in turn, just means that the total complexity of the entire algorithm is linear-logarithmic, and therefore polynomial . What was required to show! At the same time, the probability of incorrect operation of the algorithm is controlled by the parameter K, which practically does not affect the complexity of the algorithm.
Instead of conclusion
First, if we fix some value of n and from this value 1) we calculate T; 2) form a set of rules, as described above, then the membrane system constructed in this way will solve the problem of finding the Hamiltonian path in any graph whose number of vertices does not exceed n. Those. such a system is in fact an algorithm (program), and not a scheme for solving a single instance of the problem. In this case, the alphabet of this system will be polynomial with respect to n.
Secondly, if for a moment we break away from the magic phrase “a polynomial algorithm for solving an NP-complete problem”, then it will immediately become obvious that we simply replaced the temporal exponentiality with the spatial, because each membrane needs its own place
Thank you all for your attention!
')
Source: https://habr.com/ru/post/122295/
All Articles