Проведение секущих плоскостей.

Запомнив координаты первых двух точек, машина выбирает случайно *) п чисел li (i = 1, 2, 3,..., п, где п — размерность пространства рецепторов). Затем машина определяет значение двух сумм:

 

s ⁽¹⁾ = Sl _i x_i ⁽¹⁾ (1)

или

s ⁽²⁾ = Sl _i x_i ⁽²⁾ , (2)

где xi (1) — координаты первой, а xi (2) — координаты второй точки. После этого машина выбирает, также случайным образом, некоторое число l п+1, большее, чем меньшая из сумм s (1) и s (2), но меньшее, чем большая из этих сумм. Если образовать две новые суммы,

 

s ⁽¹⁾ = Sl _i x_i ⁽¹⁾ - l _n+1 (3)

 

s ⁽¹⁾ = Sl _i x_i ⁽²⁾ - l _n+1 (4)

 

то учитывая способ, которым было выбрано число l n+1, легко видеть, что одна из этих сумм обязательно будет отрицательной, а другая — положительной. Геометрически же это означает, что найденные машиной числа, l1, l2,..., ln+1 есть коэффициенты плоскости, разделяющей две наши точки. Действительно, при подстановке в левую часть уравнения этой плоскости

 

Sl _i x_i - l _n+1 = 0 (5)

координат одной из точек получается отрицательный результат, а при подстановке координат другой точки — положительный. Известно, что подобные результаты получаются в том случае, когда точки лежат по разные стороны от плоскости.

 

 

*) Случайный выбор коэффициентов означает, что каждый очередной коэффициент может с равной вероятностью оказаться любым из некоторого конечного или бесконечного ряда чисел. Для осуществления такого выбора в машинах используют специальные датчики случайных чисел.

Условимся обозначать положение данной точки относительно плоскости значком «1», если при подстановке координат этой точки в левую часть уравнения плоскости получается положительное число, и и значком «0» в противном случае. Будем говорить, что точка имеет знак «1» или знак «0» относительно данной плоскости. Представим часть памяти машины после проведения первой разделяющей плоскости (см. рис. 1) в виде таблицы I, которую будем в дальнейшем называть таблицей знаков.

 

Таблица I

Таблица знаков
Номер точки	Образ	Номер плоскости
I
Знак точки
	А В

 

При появлении следующей (третьей) точки (см. рис. 2) машина определяет ее знак относительно первой плоскости и заполняет третью строку таблицы знаков (см.табл. II).

Таблица II

Таблица знаков
Номер точки	Образ	Номер плоскости
I
Знак точки
	А
	В
	А

 

Затем машина производит поиск оппонента, т. е. поочередно сравнивает последнюю строку таблицы с каждой из предыдущих строк. Противоречием считается совпадение строк, относящихся к разным образам. В данном случае противоречие налицо: точка 3, относящаяся к образу А, попала по ту же сторону от плоскости /, что и относящаяся к образу В точка 2.

Машина проводит новую плоскость //, разделяющую точки 2 и 3 (см. рис. 3) и вычисляет знаки всех занесенных в таблицу точек относительно этой плоскости.

Таблица знаков принимает вид таблицы III.

Противоречие ликвидировано.

Появляются точки 4, 5 и 6 (см. рис. 4). После вычисления их знаков приходим к таблице IV.

 

 

Таблица III

Таблица знаков
Номер точки	Образ	Номер плоскости
I	I I
Знак точки
	А
	В
	А

 

 

Таблица IV

Таблица знаков
Номер точки	Образ	Номер плоскости
I	I I
Знак точки
	А
	В
	А
	С
	С
	В

Поиск оппонентов, произведенный после появления точки 4, а затем после появления точки 5, дает отрицательный результат. После появления шестой точки обнаруживается противоречие: точка 6 (образ В) лежит по ту же сторону от плоскостей / и //, что и точки 4 и 5 (образ С). Проводится плоскость ///, разделяющая точки 4 и 6, а затем, после нового поиска оппонента,— плоскость IV, разделяющая точки 6 и 5 (см. рис. 5). Знаки всех точек относительно новой плоскости заносятся в таблицу V.

 

Таблица V

Таблица знаков
Номер точки	Образ	Номер плоскости
I	I I	I I I	IV
Знак точки
	А
	В
	А
	С
	С
	В

 

 

Противоречия вновь ликвидированы.

С появлением новых точек машина продолжает за­полнять таблицу знаков. С каждой новой точкой в таблице появляется новая строка, с каждой плоскостью — новый столбец. После завершения первой части алгоритма таблица знаков имеет вид таблицы VI.

 

Таблица VI

 

Таблица знаков
Номер точки	Образ	Номер плоскости
I	I I	I I I	IV	V	VI	VII
Знак точки
	А
	В
	А
	С
	С
	В
	С
	В
	С
	А

 

По своему содержанию таблица VI эквивалентна рис. 9. Каждая строка таблицы соответствует одной из заштрихованных на рис. 9 частей пространства и пред­ставляет собой своеобразный код такой области — выпуклого n-мерного многогранника, образованного секущими плоскостями *). Этот код указывает, по какую сторону от каждой из секущих плоскостей лежит много­гранник, содержащий данную точку.