rm rw number of evaluations of stability solution male optimal solutionsolution female optimal solution table result of the stable marriage problem the solution with the least value rm is called the male-optimal stable solutionthe one with the smallest rw is the female-optimal stable solution it lies in the nature of the chosen search strategy that good solutions from the men' point of view are generated first and the good solutions from the women' perspective appear toward the end in this sensethe algorithm is based toward the male population this can quickly be changed by systematically interchanging the role of men and womeni by merely interchanging mwr with wmr and interchanging rmw with rwm we refrain from extending this program further and leave the incorporation of search for an optimal solution to the next and last example of backtracking algorithm the optimal selection problem the last example of backtracking algorithm is logical extension of the previous two examples represented by the general schema first we were using the principle of backtracking to find single solution to given problem this was exemplified by the knight' tour and the eight queens then we tackled the goal of finding all solutions to given problemthe examples were those of the eight queens and the stable marriages now we wish to find an optimal solution to this endit is necessary to generate all possible solutionsand in the course of generating them to retain the one that is optimal in some specific sense assuming that optimality is defined in terms of some positive valued function ( )the algorithm is derived from the general schema of try by replacing the statement print solution by the statement if (solutionf(optimumthen optimum :solution end the variable optimum records the best solution so far encountered naturallyit has to be properly initializedmoreverit is customary to record to value (optimumby another variable in order to avoid its frequent recomputation an example of the general problem of finding an optimal solution to given problem followswe choose the important and frequently encountered problem of finding an optimal selection out of given set of objects subject to constraints selections that constitute acceptable solutions are gradually built up by investigating individual objects from the base set procedure try describes the process of investigating the suitability of one individual objectand it is called recursively (to investigate the next objectuntil all objects have been considered we note that the consideration of each object (called candidates in previous exampleshas two possible outcomesnamelyeither the inclusion of the investigated object in the current selection or its exclusion this makes the use of repeat or for statement inappropriateinsteadthe two cases may as well be explicitly written out this is shownassuming that the objects are numbered -