Marriage Task and Returns Mode

Bektrekinge - a mechanism for solving quasi problems. Allows you to choose either 1 acceptable alternative or the best.

The essence of the return mode is as follows. In the program there are points "forks" - points at which it is necessary to choose one of the behaviors ("alternatives"). In the future, it may be that the chosen option is “unsuccessful” and you need to return to the fork and select some other alternative.

Bektrekkinga feature is that there is a rollback on management, as well as data. When a program is rolled back, the program “forgets” everything that it did as a result of choosing an unsuccessful alternative - the data restores its previous values, all the consequences of choosing an alternative are canceled. After the rollback, take the next alternative and re-perform all the actions. We check which alternatives are acceptable to us. If all alternatives fail in this fork, the failure propagates to the overlying fork.

Bektreking provides:
- rollback control;
- rollback by data;
- enumeration of the list of alternatives.
')
There are actions not subject to rollback. Example: print on screen, printer, etc.

Forks can be divided into local (visible only in its subroutine) and global (even the subroutine is complete, the fork is visible).
Therefore, it is possible rollback entry into the procedure. The procedure is completely restored, all local variables, their values ​​and the history of their values ​​are restored.

Variants of the organization:
- data and actions can be selected as alternatives; (array of procedural labels)

- list of alternatives: fixed, dynamically calculated, may not be stored at all;

- automatic reordering of the set of alternatives.
Predict which alternative will bring success. (prediction requires resources.). but turning over alternatives we will come to the result.

- perhaps the absence of the design “failure”; (there is a design for establishing a fork or not)

- rollback is possible: to the nearest fork, to the specified statically / dynamically, automatic determination of the desired fork;
If we have sifted through all the alternatives, then we are failing to spread to the top.
In order not to roll back in steps, but to the one you want is necessary:
1. mark all fork and roll back
2. rollback to a fork is determined dynamically.

- automatic detection of fork.
Rollback within the program
Rollback to a Called Subroutine
Rollback to complete subroutine.
If it is possible to roll back to the fork after the completion of the procedure, then the outer fork.
Irreversible action - actions that are not canceled during a rollback may exist, may not exist.
- it is possible to disable the return mode, dynamically / statically, fully / partially;

- can be associated with a message failure signal, and the possibility of program analysis.

There are languages ​​that, in their implementation, support bektreking (Prolog, Plener). Within the framework of this article, I will consider emulation of the return mode in languages ​​that do not explicitly support it. In the article for writing listing, I will use Pascal-like pseudocode, so as not to be distracted by the syntax.

Scheme for the implementation of bektrekinga procedurally-oriented language.
In this approach, the forks are emulated using recursion, and enumerating alternatives using a cycle.
procedure TryAlt(N:trazvilka; var uspeh:boolean);
begin
{ }
uspeh:=false;
repeat { }
if { } then begin { }
if { ( )} then
uspeh:=true
else begin
try(N+1;uspeh);{ }
if uspeh then
{ }
{ }
end;
end;
until uspeh or
end.

The problem of stable marriages

Suppose that two disjoint sets A and B are given of equal size n. It is required to find a set of n <a, b> pairs - such that a from A and b from B satisfy some constraints. Distribution criteria may be many. We consider one of them, which is called the rule of stable marriages.
Let A be a set of men, and B a set of women. Every man and woman indicated their preferred partners. If couples are formed in such a way that there are a man and a woman who are husband and wife, but who would prefer each other to their actual spouses, then this distribution will be unstable. If there are no such pairs, then the distribution is stable. It should be noted that the list of distributions remains unchanged even after the distribution is made in pairs.
A possible direction for finding a solution is to try to distribute the pairs of the two sets one by one into pairs until both sets are exhausted. To solve this problem, we use the backtreaming scheme, slightly modifying it in the direction of simplification.

Procedure tryMan (m : man);
Var
R : rang;
Begin
If m < n then
For r := 1 to n do begin
r- m
If then begin
;
Try ( m);
;
End;
end;
else

end;

Baseline data is represented by two matrices indicating the preferences of men and women.
Var
womanForMan : array [1..n,1..n] of woman
manForWoman : array [1..n,1..n] of man
Accordingly, womanForMan [m, r] is a woman in the list of male m in r-th place. Similarly, manForWoman [w, r] is a man in the list of woman w in r-th place.
The result is represented by an array of woman so that woman [m] denotes the spouse of male m. For symmetry, we introduce man such that man [w] denotes the spouse of the man w. In fact, the man array is redundant since it contains information already contained in a woman. Information in the man and woman arrays is needed to determine the stability of the intended set of marriages. Since this set is built step by step by connecting the individuals into pairs and checking the stability after each alleged marriage, the man and woman arrays are needed before all the components are defined. To keep track of which components are already defined, we introduce boolean arrays:
singleMan, SingleWoman: array [1..n] of Boolean
the truth of the component means that the corresponding man (woman) is free.
they can be used to clarify the predicate is admissible as a singleWoman [w] conjunction & the marriage is stable, where the predicate marriage is stable has yet to be defined.

The key task now is to clarify the algorithm for determining stability. The first feature to keep in mind is that, by definition, stability follows from a comparison of ranks (that is, positions in a list of preferences). However, nowhere in our collection of data defined so far, there are no directly accessible ranks of men and women. Of course, they can be calculated from the womanForMan and manForWoman values, but since stability calculation is a very frequent operation, it is advisable to provide more direct access to this information. To do this, we introduce two matrices,
Rmw: array [man, woman] of rang;
Rwm: array [woman, man] of rang;
In this case, rmw [m, w] denotes the rank of a woman w in the list of male m, and rwm [w, m] is the rank of male m in the list of female w. The values ​​of these auxiliary matrices do not change and can be determined at the very beginning by the values ​​of womanForMan and manForWoman.
Now the predicate Marriage is stable can be calculated exactly following its definition. Let me remind you that we need to check the ability to connect by marriage m and w, where w = womanForMan [m, r]. To begin with, suppose that such a marriage is permissible, and then we will try to detect interference with the stability of this marriage. There may be two such interferences:
1) There may be a woman pw with a rank higher than that of w, according to m, and who herself prefers m to her husband;
2) There may be a pm man with a rank higher than that of m, according to w, and who himself prefers w to his wife
To detect interference of the first kind, compare the ranks rwm [pw, m] and rwm [pw, man [pw]] for all women that m prefers w, that is, for all pw = womanForMan [m, i] such that i < r. We are in fact all women pw are already married, since, had any of them not yet been married, m would have chosen her even earlier. To detect interference of the second kind, you need to check all candidates pm, which w prefers over their current pair m, that is, all men pm = manForWoman [w, i], i <rwm [w, m], by analogy with the first case, however Do not forget to miss the comparison with the subject woman [pm], where pm is not yet married. This is ensured by checking pm <m, since we know that all men up to m are married.

The full text of the stability check procedure looks like this.
Function stable(m, w, r : integer) : Boolean;
Var
Pw, pm, I, lim : integer;
S : Boolean;

Begin
I := 0; s := true;
Repeat
Inc(i);
If i<r then begin
Pw := womanForMan[m,i];
If not(singleWoman[pw]) then
S := rwm[pw,m] >rwmn[pw,man[pw]];
End;
Until (i=r) or (not(s));

I := ;0 lim := rwm[w,m];
Repeat
Inc(i);
If I < lim then begin
Pm := manForWoman[w,i];
If pm<m then
S := rmw[pm,w]>rmw[pm,woman[pm]
End;
Until (i=lim) or (nor(s));
End;


Conclusion

This algorithm generates all possible solutions and can be modified in such a way that either the solution is optimal for men, or for women, or average. It all depends on the purpose for which this algorithm is used.