SVIBO game - A-Optimi:

Conducting search a game optimal solution

(Quick Start Guide)

In the game SVIBO - A-OPTIMI conducting search of the optimal gaming solution, equal to the minimum sum, can be carried by various algorithms that are used in the assignment problem optimization.

The main disadvantage of using any algorithms for assignment problem solving is following: player can’t assert/insist that he/she receive the best solution if pre-specified value of the game search criterion is absent. Application of full or partial search through all solutions is not effective for game matrices dimensions of 7x7 and more.

Game creator suggested the following idea of the algorithm for searching the minimum sum in assignment problem. The player picks any support solution. Then the player must construct an improving permutation relatively to the reference solution. The first element of improving permutation should always be an element for which the change search criteria will be less than zero. Thus, if the matrix shown in Figure 1 is given and reference solution is selected, then the player can start constructing improving permutation, for example, from the entry [(6,4) - 9]. This construction arrow is highlighted in red in figure 1.

Further player introduces sequentially new elements (4,3), (5,2) and (1,1) in improving permutation, while at each step of constructing improving permutation changing search criterion should be less than zero. Appropriate construction of introducing new elements in improving permutation highlighted in figure. 1 by black arrows.

Figure.1.

The process of constructing this improving the permutation can be presented as follows:

Step 1: { [(6,1) - 17] → [(6,4) - 9] }, this construction corresponds the following changing of a search criterion value equal

(9-17) = (-8)

Step 2: { [(6,1) - 17] → [(6,4) - 9], [(4,4) - 5] → [(4,3) - 9] }, this construction corresponds the following changing of a search criterion value equal

( -8) + (9 - 5) = (-8) + 4 = (-4)

Step 3: { [(6,1) - 17] → [(6,4) - 9], [(4,4) - 5] → [(4,3) - 9], [(5,3) - 25] → [(5,2) - 19] }, this construction corresponds the following changing of a search criterion value equal

(-8) + (+4) + (19 - 25) = (-8) + 4 - (-6) = (-10)

Step 4: { [(6,1) - 17] → [(6,4) - 9], [(4,4) - 5] → [(4,3) - 9], [(5,3) - 25] → [(5,2) - 19], [(1,2) - 6] → [(1,1) - 9] }, this construction corresponds the following changing of a search criterion value equal

(-8) + 4 + (-6) + (9 - 6) = (-8) + 4 - (-6) + 4 = (-6)

New principle of local optimization assignment problem bases on construction mechanism of improving permutations in which the requirement - on each construction step of improving permutation a changing of search criteria value is less than zero. The essence of this local optimization principle is following if there is a permutation for that changing of the search criterion value is less than zero, it means that the total change in the search criterion consists of positive and negative numbers, or negative numbers only.

By Kheifets theorem, if there is a sequence of positive and negative numbers whose sum is less than zero, then there is always a negative number in the sequence, from which at each step sequel summing the sum will be less than zero.

As applied to SVIBO games it means that if it is impossible to construct the improving permutation relatively the current reference solutions as at each construction step value of the search criterion changing is less than zero, then this reference solution is optimal.

In SVIBO games practice this means the following:

1. If the player does not reached the target value of the game search – Goal, then there is always at least one or more improving permutations, allowing to pass to the game optimal solution.

2. If the game is conducted under the condition that the value of "Goal" is unknown, then, if the player can not construct any improving permutation on each step of them sum of search criterion changing will be less than zero, and then this reference solution is optimal. Naturally, with increasing gaming matrix dimension number of search operations may increase depending on the ratio of elements in the gaming matrix.

From a practical point of view, all the above-described means that the player must keep the direct search of permutations at each construction step the value of search criterion changing will be less than zero. If the player has managed to build a improving permutation of, he makes the transition to a new support solution.

If the player is not able to construct improving permutation, for which at every construction step the value of search criterion changing will be less than zero, and such Improving permutation for current reference solution doesn’t exist, it means that the player has successfully completed the game.

Copyright ©2013 Boris Kheifets. All right received

No part of this document can be reproduced, transferred, distributed or stored in any format without the prior written permission of Boris Kheifets.