Chat C algorithm package: exhaustion
Abstract algorithm is independent, can't be fresh in C : STL encapsulates a lot of efficient, robust, flexible generic components and corresponding basic algorithms, high technology, strong applicability, non-ordinary me Easy and. It is not planned here (also no ability to intend to intend to discuss the algorithm package with industrial-grade requirements such as STL, only because of the recent masters, the level of the reader is limited, only sniffing to the fur, the sensibility, the feelings are booming: also Want to try the taste of "packaging". Choosing the easiest exhaustion algorithm, drawing its skeleton, can make a Class, set up a practical example, the RUN of the view, the abstraction is quite low, the efficiency loss is scored; however, it also consciously has cute, Wen is in writing. Sincere and fear, it is easy to add "chat" before the name, if the fruit is embarrassed because the technical problem is hurt, try this two words as a guard, chat and a gear.
It is well known that the exhaustive law can be seen as the simplest search: that is, in a stateful full-time full-to-use state, it is sequentially traversed for all elements, and determines if it is a feasible state. For example, you want to design a exhaustive algorithm such as "Finding Blue Apple from a bunch of apples", defined:
(1) Complete Works: A bunch of apples
(2) Feasible state: blue apple
Oh, good, we have drawn two basic concepts, can't wait to start exhaust, but ... how to do? The key to exhaustion is "sequentially travers", that is, it is not heavy, no leakage. Hey, we can let the apples who are obedient, put them in the "Arch of Apple", then, we can follow the No. 0 Apple, 1 Apple, No. 2 Apple, ..., N, Apple. Successful traversal. Ok, we solve the problem of traversing Apple ... Slow, we are now designing an algorithm's abstract model. If all the objects to be treated, it is already living there, and of course it is possible to collect all them and queue, but If we don't know if we don't know all objects that are exhausted, such as we may have to make a life-like planet outside the entire universe through a computer that is installed in the exploration spaceship, then our computer may As the front of the spacecraft can constantly get the information of the new planet, it will get the star information of the whole universe when they stop in the earth (even if the memory may, the memory may not be able to install such a large amount of data - even if the universe is true It is limited "big"). Therefore, we should not request exhaustion to get all the states in the full concentration, so that our "Apple Array" plan will declare abortion. Now look at our exciting planet search plan: it does not queue all the planets, then where is the key to success? Whether the spacecraft can "patron" all the planets in an appropriate path; we will strengthen this condition: the spacecraft reaches a planet every time, you will see a directional mark on the planet, indicate the orientation of the next planet; Such marking ensures that the spacecraft can fly all the planets in the universe. Ah ... Do you think I am doing this is a whim? Oh, it doesn't matter, it's too much not to search for the stars, and many real-world exhaustions outside this can meet this reinforcement. Well, I admit that this article discusses a slightly narrow exhaustive exhaustion of this strengthening condition: it must guarantee a new state in the premise of knowing a state, and such "status chain" is just over the entire state. We call it from the current state and go to the next state to "status jump" (I want to use "state transfer", hey, unfortunately it is confused with the term of the dynamic planning algorithm): (3) state Jump: According to the current Apple, obtain the next apple according to a certain "over-calendar algorithm"; this algorithm guarantees that all the apples in the apple bore is not heavy, as long as the first apple taken is defined according to the algorithm Given
Obviously, for different exhaustive tasks, there will be different traversal algorithms, so we have to achieve it to the users who call us "Poverty Algorithm". However, it is indeed decided by the diversity of problems, so this requirement should be reasonable.
Well, now we already have Apple source, target apple, and even more apple's program (providing), next to a judgment standard, this is simple:
(4) Judgment criteria: Whether Apple is a blue apple
Next, we can consider the specific implementation of the "The Class Of Poor Algorithm". We define this Class's name as Walkthrough.
First, let us notice that "status" is a very important concept: different exhaustions have different states, in Apple issues, "Status" is Apple, which contains Apple color or more information In the Planet Search Plan, "Status" is a planet, which may contain the volume, mean density, temperature, whether there is an atmosphere, whether to detect a series of amazing information such as water and star table activity. Therefore, different status corresponds to different data types, so that Walkthrough can handle them, it is necessary to use templates, so our initial definition is as follows: Template
Class Walkthrough
{
}
Everything is difficult, but now we have obviously have a good head, um, continue. Before considering the specific implementation, what kind of service can be provided for users - of course, its job work is found and returned, so it seems to have a member function similar to getFilter (). The problem is that if the feasible status is more than one, the getfilter () should return a feasible state or all the feasible state? It is not difficult to imagine that it is not true to return all feasible states because: 1. Sometimes users only need one, or a few feasible states, at this time, all feasible states are poor, obviously inefficient, not The necessary; 2. Even the number of feasible status of some problems is unlimited, such as the number of pixels, and return all status at this time is certainly impossible. At the same time, considering that the user's requirements may be more than one can solve, we now know, a function of getNextFilter () instead of getfilter (): When you call it, return it from the initial state, sequentially traversal The first feasible state; and since the call will continue to traverse the above call as the starting point, return to the next feasible state. It should be noted that if the full set of states have been traversed, it is clear that this function is not called, so it should return a flag that feeds back to the user. It has been completed. We define this function as BOOL. If the call is valid, return True, and villain returns false if it has been completed. Obviously, we need a private State object variable Curstate, which is used to store the current status value.
Will we add a State reference parameter to getNextFilter to return a feasible state of each exhaustive? Here we did not do this. Imagine that users will want to get the feasible state traversed by the 5th traversal, then he certainly wants to call 5 getNextFilter (), but before 4 times he does not require the feasible status of the search. So, we will "find the next feasible state" and "get the currently found feasible status", add a getState () member function, it returns a State object, notice that getState () operation does not affect the Walkthrough object The internal state, so it should also be declared as a Const member function.
Accordingly, we need a setState () member function that is used to change the current status value, such as setting the initial state, it is possible to use. It has a const state & type parameter to specify the State value to be set. Since State may be a large type, use the reference delivery energy guarantee efficiency, while adding the const restriction to ensure that the function does not change the The value of the incoming reference object itself.
At the same time, the user may need to know, for a exhaustive object, whether the exhaustion has been completed, of course, he can call getNextFilter () and check the return value, but if the travers, getNextFilter () has an additional except for the last return. Perform search and change the current state to the next feasible state, this additional work may not be desired to be desirable. So we will add a member function isover (), it does not have a parameter, return a BOOL value: If traverside has been completed, return true, and return false. Accordingly, we need a private bool variable overflag, which is used to store Isover The status value required. At this point, Walkthrough is defined as follows:
Template
Class Walkthrough
{
PUBLIC:
Void setState (const state) {curState = s;}
State getState () const {return curState;}
Bool getNextFilter ();
Bool isover () const {return overflag;}
Private:
State Curstate;
BOOL overflag;
}
After we take the constructor with the destructor, we will first consider the implementation of the GetNextFilter () of the key role. First, getNextFileter () is jumped by the current state to the next state, and then determines if the new state is feasible. If it is feasible, stop the jump and return TRUE, otherwise, continue jump, repeat the above steps. On the other hand, if it has been traversed, it has not found a feasible state, set overflag to false and returns false.
We deliver the jump operation, determine if the user is put to the user to implement: the user provides two functions, and then incorporates the WALKTHROUGH object to the GetNextFileter () call. So what kind of interface form should these two functions? Let's take a look at the jump function, a very intuitive implementation is incoming a State object (or its const reference), then return "Next" State object, but at least return, the value transfer will generate a copy operation of the State object. (Specific compilers, such as language standards such as NRV optimization, are not discussed), when the State object is relatively large, the overhead is not worth it. We should consider the introduction of the reference to the State object, and then "all right to delegate" the jump function to change directly - "change" into a state. Some people may have doubt whether to violate the package principles, but even if it is abandoned the trade-off of efficiency, this is also reasonable. Jump functions - may wish to be deemed to be responsible for "state transformation" function, like a refining furnace - there is right, even obligations so, its responsibility is "transformation status" rather than "Get State". Oh ... I feel that I am too abdicated to the language. Well, in addition to the state of transformation, the jump function should promptly tell the getNextFilter () after the completion of the traversal is found, otherwise the getNextFilter () decentralized to the unobstructed. So our jump function interface is: accept a reference to a reference, returns a BOOL value. If the traversal is not completed, the STATE reference will become a subsequent state after the function is executed, and the function returns true; otherwise the state is constant, the function returns false.
The function interface that determines whether it is a feasible state is well defined: it accepts a const state type reference as a state of the to be determined, returns the BOOL value, where true indicates that the state is a feasible state, and false indicates that the state is not a feasible state. We define the type of jump function and the function of the determination function to be Statejumper and Matcher, respectively, because the user may also use these function pointer types, we will be added to the public domain:
PUBLIC:
Typedef Bool (* Statejumper) (State &);
Typedef Bool (* Matcher) (Const State &);
// Others ...
And, in the private domain, add the function pointer variables of StateJumper and Matcher, and store the address provided by the corresponding function provided by the user:
Private:
// Others ...
Statejumper Jumper;
Matcher ismatch;
Accordingly, inline definition public member functions:
Void setjumper (const statejumper j) {jumper = j;}
Void setMatcher (const matcher m) {ismatch = m;}
A function pointer value used to set Jumper and ISMATCH, respectively.
Now all member variables have already surfaced, we can define the constructor and the paced functions, we don't intend to limit the creation of Walkthrough's creation and inheritance, so they are added in the public domain. First look at the constructor, it is necessary to define a default constructor:
Walkthrough (): Overflag (false), jumper (0), ismatch (0) {}
This constructor does not specify any initial conditions, including the current state. You can use a series of SET member function definitions when needed.
Next, define a "full function" constructor:
Walkthrough (const state & s, statejumper j = 0, matcher m = 0)
: Overflag (False), Curstate (s), Jumper (j), ismatch (m) {}
In addition to Overflag, all properties can be set in this constructor (of course, it allows the default). Since there is no exhaustive operation, it is reasonable to force Overflag to false.
For copy constructor, since we do not involve memory allocation, there is no "deep copy", therefore does not make a definition, using the default bit copy can have a good efficiency. Similarly, there is no business in the destructive function, but considering that this Walkthrough may be used for inheritance, and there is a case where the DELETE base class pointer to delete the derived object, it defines an empty false argument function to avoid causing arguments. error:
Virtual ~ walkthrough () {}
Finally, we will implement the only one-to-end, which is getnextfilter (), gives a complete Walkthrough definition before given the implementation:
Template
Class Walkthrough
{
PUBLIC:
Typedef Bool (* Statejumper) (State &);
Typedef Bool (* Matcher) (Const State &);
Walkthrough (): Overflag (false), jumper (0), ismatch (0) {}
Walkthrough (const state & s, statejumper j = 0, matcher m = 0): Overflag (false), curState (s), jumper (j), ismatch (m) {}
Virtual ~ walkthrough () {}
Void setjumper (const statejumper j) {jumper = j;}
Void setMatcher (const matcher m) {ismatch = m;}
Void setState (const state) {curState = s;}
State getState () const {return curState;}
Bool getNextFilter ();
Bool isover () const {return overflag;}
Private:
State Curstate;
BOOL overflag;
Statejumper Jumper;
Matcher ismatch;
}
Template
Bool Walkthrough
{
If (overflag) // If traverses have been completed, return directly
Return False;
If (! jumper ||! ismatch) // If the user does not define the Jumper or ISMATCH function, return
{
Overflag = true; // This will not define the exhaustion of Jumper or ISMATCH as traversal completion
Return false; // However, if you think it's absolutely equal, you can throw an exception
}
While (! (overflag =! jumper (curstate) &&! ismatch (curstate))
; // Get the next state until you find a feasible state or traversal
if (overflag) / / Decide the return value based on the transaction completion
Return False;
Else
Return True;
}
Call ... Xiaolong, it is finally possible to be small. However, if you turn off your computer, you suddenly lose your power when you go to the climax, too uncomfortable. - After you have been so long, should I try it for a try to give an example?
no problem. Apple is too simple, so we choose a legendary "and 50" superpolar, what is "and 50" superpolation? Please listen: the so-called "and 50" superpolation is in an additional calculation of the integer of 0 to 99, finding and is a 50 calculation, considering the order of addition, like 0 50, 1 49 Ah, ..., 49 1 ah, 50 0 ... (Hello, I know you may want to kill, but please don't let the eyes match the eyes toward me ...) For such a superpolate, we have been studying Decided to use ... exhaustion method to achieve (where so many tomatoes?).
First of all, we have studied the status of this problem - two plus numbers, not, they are sequential, and can take an integer of 0 to 99. So, we define the state class as follows (Note: There are similar things in STL, but as a complete example, we personally create):
Class Pair
{
PUBLIC:
Pair (int mx = 0, int my = 0): x (mx), y (my) {} int x, y;
}
Although Pair belongs to one of the world's most deepest Class, I don't have to explain more than a wisdom. Then let's take a look at the implementation of the jump function - of course, it should comply with the StateJumper type defined in Walkthrough:
Bool Counter (Pair & Pair)
{
IF (pair.y <99)
Pair.y;
Else
{
IF (Pair.x <99)
{
Pair.x;
Pair.y = 0;
}
Else
Return False;
}
Return True;
}
The role of Counter is to attempt to increase Pair.y, but if pair.y has reached the upper limit 99, add PAIR.X 1, and PAIR.Y 0 continues the next round; but if Pair.x has arrived 99, So, oh, explaining the end of the traversal. - Well, this is indeed an effective traversal method, right. It is actually similar to the following two cycles:
For (; pair.x <= 99; pair.x)
For (pair.y = 0; pair.y <= 99; pair.y)
...
Only, the loop requires all problems in the cycle, and our "solving all problems" is in another function, and the Counter cannot be able to use the loop directly.
Next is a function that determines if it is a valid state, it is the easiest:
Bool Match (Const Pair & Pair)
{
Return (Pair.x Pair.y) == 50;
}
Everything you can write, you can write main:
int main ()
{
Walkthrough
While (sf50.getnextfilter ())
COUT << sf50.getState (). x << " "
<< sf50.getState (). Y << "= 50" << Endl;
Return 0;
}
Be sure to note that there is a "next" in getnextfilter (), that is, if the first state in the full concentration is used as the configuration parameters, - this topic is Pair (0, 0) - is a feasible state If getNextFilter () will not judge that it directly determines the "next" state, it is Pair (0, 1). In order to make it fully judged, we can't let Pair (0, 0) as the first state, but as a state reaching after the first runNextFilter (). Thus, when constructing the initial state, we must use the "front" state pair (0, -1) as a constructive parameter (although it is not in the state of this question, it makes getnextfilter () from Pair (0, 0) Start judgment.
Well, ok, don't forget to don't forget to open the STD name space before running (using namespace std;), don't forget to stick / contain the full definition of Walkthrough's Walkthrough ... Compile, run, Ok, this super puzzle is solved by us. My compilation platform is Redhat Linux 9, GNU C 3.2.2. Finally, we analyze the exhaustive algorithm after the package is encapsulated. First of all, the efficiency - Yes, I know this "and is 50" superpolation algorithms are very bad - I refer to the efficiency loss when using our packaged exhaustion class under the premise of the same algorithm: Initialization and a series of SET / GET functions do not affect efficiency, main sales derived from getNextFilter () itself calls and GetNextFilter's additional overhead of two users to provide functions. Imagine if the same algorithm is used, but only the two flies is poor, then tens of thousands of functions, and clear the stack operation. The exhaustive law itself is not an efficient search idea, so the efficiency change of the inner layer code is the most sensitive, this is the biggest shortcoming of the exhaustive class we packaged.
However, there is still a good benefit. For example, after the package, the design poor algorithm is decomposed into a relatively independent design state class, the status jump function, the state judgment function, and the coupling degree of the three is relatively low. In addition, the process of this design makes us more understanding of object-based abstract abilities, um, and so on. Oh ... maybe this is an academic value greater than the practical value design, huh, huh.
