__The problem of the most isolated villages__.

We consider `n` villages (`n` > 1), numbered from 0 through `n`–1; for 0 ≤ `i` < `n` and 0 ≤ `j` < `n`, a computable function f(`i`, `j`) is given, satisfying for some given positive constant M:

**for** `i` ≠ `j` : 0 < f(`i`, `j`) < M

**for** `i` = `j` : f(`i`, `j`) = M .

For the `i`-th village, its isolation degree “id(`i`)” is given by

id(i) = |
minimum | f(i, j) = |
minimum | f(i, j) |

j ≠ i |
j |

(Here f(`i`, `j`) can be interpreted as the distance from `i` to `j`; the rule f(`i`, `j`) = M has been added for the purpose of the above simplification.)

We are requested to determine the set of maximally isolated villages, i.e. the set of all values of `k` such that

(∀ `h`: 0 ≤ `h` < `n`: id(`h`) ≤ id(`k`)) .

The program is expected to deliver this set of values as

miv(miv.lob), ... , miv(miv.hib)

Note that eventually all values 1 ≤ miv.dom ≤ `n` are possible.

A very simple and straightforward program computes the `n` isolation degrees in succession and keeps track of their maximum value found thus far. On account of the bounds for f(`i`, `j`) we can take as the minimum of an empty set the value M and as the maximum of an empty set 0.

**begin glocon** `n`, `M`; **virvar** `miv`; **privar** `max`, `i`;

`miv` **vir** int **array** := (0); `max` **vir** int, `i` **vir** int := 0, 0;

**do** `i` ≠ `n` →

**begin glocon** `n`, `M`; **glovar** `miv`, `max`, `i`; **privar** `min`, `j`;

`min` **vir** int, `j` **vir** int := `M`, 0;

**do** `j` ≠ `n` →

**do** f(`i`, `j`) < `min` → `min`:= f(`i`, `j`) **od**;

`j`:= `j` + 1

**od** {`min` = id(`i`)};

**if** `max` > `min` → skip

▯ `max` = `min` → `miv`:hiext(`i`)

▯ `max` < `min` → `miv`:= (0, `i`); `max`:= `min`

**fi**;

`i`:= `i` + 1

**end**

**od**

**end**

The above is a very unsophisticated program: in the innermost loop the value of `min` is monotonically non-increasing in time, and the following alternative construct will react equivalently to *any* value of `min` satisfying `min` < `max`. Combining these two observations we conclude that there is only a point in continuing the innermost repetition as long as `min` ≥ `max`. We can replace the line “**do** `j` ≠ `n` →” therefore by

“**do** `j` ≠ `n` **and** `min` ≥ `max` →”

and the assertion after the corresponding **od** by

{ id(`i`) ≤ `min` < `max` **or** id(`i`) = `min` ≥ `max `} .

Let us call the above modification “Optimization 1”.

A very different optimization is possible if it is given that

f(`i`, `j`) = f(`j`, `i`)

and —because the computation of f is assumed to be time-consuming— it is requested never to compute f(`i`, `j`) for such values of the argument that f(`j`, `i`) has already been computed. Starting from our original program we can achieve that for each unordered argument pair the corresponding f-value will only be computed once by initializing `j` each time with `i`+1 instead of with 0 —only scanning the upper triangle of the symmetric distance matrix, so to speak—. The program is then only guaranteed to compute `min` correctly provided that we initialize `min` instead of with `M` with

.minimum | f(i, h) |

0 ≤ h < i |
. |

This can be catered for by introducing an array, `b` say, such that for `k` satisfying `i` ≤ `k` < `n`:

for i = 0 : b(k) = |
M | |

for i > 0 : b(k) = |
minimum | f(k, h) |

0 ≤ h < i |

(In words: `b`(`k`) is the minimum distance connecting village `k` that has been computed thus far.)

The result of Optimization 2 is also fairly straightforward.

**begin glocon** `n`, `M`; **virvar** `miv`; **privar** `max`, `i`, `b`;

`miv` **vir** int **array** := (0); `max` **vir** int, `i` **vir** int := 0, 0;

`b` **vir** int **array** := (0); **do** `b`.dom ≠ `n` → `b`:hiext(`M`) **od**;

**end** {all virgin variables at outer level are initialized};

**do** `i` ≠ `n` →

**begin glocon** `n`; **glovar** `miv`, `max`, `i`, `b`; **privar** `min`, `j`;

`min` **vir** int, `b`:lopop; `j` **vir** int := `i` + 1;

**do** `j` ≠ `n` →

**begin glocon** `i`; **glovar** `min`, `j`, `b`; **privar** `ff`;

`ff` **vir** int := f(`i`, `j`);

**do** `ff` < `min` → `min`:= `ff` **od**;

**do** `ff` < `b`(`j`) → `b`(`j`)= `ff` **od**;

`j`:= `j` + 1

**end**

**od** {`min` = id(`i`)};

**if** `max` > `min` → skip

▯ `max` = `min` → `miv`:hiext(`i`)

▯ `max` < `min` → `miv`:= (0, `i`); `max`:= `min`

**fi**;

`i`:= `i` + 1

**end**

**od**

**end**

To try to combine these two optimizations presents a problem: in Optimization 1 the scanning of a row of the distance matrix is aborted if `min` has become small enough, in Optimization 2, however, the scanning of the row is also the scanning of a column and that is done to keep the values of `b`(`k`) up to date. Let us apply Optimization 1 and replace the line “**do** `j` ≠ `n` →” by

“**do** `j` ≠ `n` **and** `min` ≥ `max` →” .

The innermost loop can now terminate with `j` < `n`; the values `b`(`k`) with `j` ≤ `k` < `n`, for which updating is still of possible interest are now the ones with `b`(`k`) ≥ `max`, the other ones are already small enough. The following insertion will do the job:

**do** `j` ≠ `n` →

**if** `b`(`j`) < `max` → `j`:= `j` + 1

▯ `b`(`j`) ≥ `max` →

**begin glocon** `i`; **glovar** `j`, `b`; **privar** `ff`;

`ff` **vir** int := f(`i`, `j`);

**do** `ff` < `b`(`j`) → `b`(`j`)= `ff` **od**

`j`:= `j` + 1

**end**

**fi**

**od**

The best place for this insertion is immediately preceding “`i`:= `i` + 1”, but after the adjustment of `max`: the higher `max`, the larger the probability that a `b`(`k`) does not need any more adjustments.

^{*} _{*} ^{*}

The two optimizations that we have combined are of a vastly different nature: Optimization 2 is just “avoiding redoing work known to have been done”, and its effectiveness is known a priori. Optimization 1, however, is a strategy whose effectiveness depends on the unknown values of f: it is just one of the many possible strategies in the same vein.

We are looking for those rows of the distance matrix whose minimum element value S exceeds the minimum elements of the remaining rows and the idea of Optimization 1 is that for that purpose we do not need to compute for the remaining rows the actual minimum if we can find for each row an upper bound B_{i} for its minimum, such that B_{i} < S. In an intermediate stage of computation, for some row(s) the minimum S is known because all its/their elements have been captured; for other rows we only know an upper bound B_{i}. And now the strategic freedom is quite clear: do we first compute the smallest number of additional matrix elements still needed to determine a new minimum, in the hope that it will be larger than the minimum we had and, therefore, may exceed a few more B’s? Or do we first compute unknown elements in rows with a high B in the hope of cheaply decreasing that upper bound? Or any mixture?

My original version combining the two strategies postponed the “updating of the remaining `b`(`k`)” somewhat longer, in the hope that in the mean time `max` would have grown still further, but whether it was a more efficient program than the one published in this chapter is subject to doubt: it was certainly more complicated, needing yet another array for storing a sequence of village numbers. The published version was only discovered when writing this chapter.

In retrospect I consider my ingenuity spent on my original program as wasted: if it was “more efficient” it could only be so “on the average”. But on what average? Such an average is only defined provided that we postulate —quite arbitrarily!— a probability distribution for the distance matrix f(`i`, `j`). On the other hand, it was not my intention to tailor the algorithm to a specific subclass of distance matrices!

The moral of the story is that, in making a general program, we should hesitate to yield to the temptation to incorporate the smart strategy that would improve the performance in cases that might never occur, if such incorporation complicates the program notably: simplicity of the program is a less ambiguous target. (The problem is that we are often so proud of our smart strategies that it hurts to abandon them.)

__Remark__. Our final program combines two ideas and we have found it by first considering —as “stepping stones”, so to speak— two programs, each incorporating one of them, but not the other. In many instances I found such stepping stones most helpful. (End of remark.)