[МРО] Методичка МРО
.pdf
|
Следует обратить внимание на то, что с увеличением числа |
||||||||||
|
введенных в машину объектов и количества секущих плос- |
||||||||||
|
костей противоречия будут возникать между объектами и |
||||||||||
|
оппонентами, лежащими все ближе и ближе к границам областей |
||||||||||
|
А, В, С. Область пространства, в которой возможны противо- |
||||||||||
|
речия, все время сужается, и вероятность возникновения проти- |
||||||||||
|
воречия при появлении нового объекта становится все меньше и |
||||||||||
|
меньше, так как убывает число неправильно поименованных |
||||||||||
|
областей. Частота возникновения противоречий может, таким |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
Н |
|
образом, служить критерием завершения первой части алгоУ- |
||||||||||
|
ритма. Закончим первую часть алгоритма проведением плоско- |
||||||||||
|
стиVII. Сложившаясяситуацияприведенанарис. 1.12. Т |
||||||||||
|
|
|
|
|
|
|
|
II |
Б |
||
|
|
|
|
IV |
|
|
|
|
III |
|
|
|
|
|
|
|
|
|
|
й |
|
I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
и |
|
|
|
|
|
|
|
|
|
3 |
р |
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
Y |
о |
|
|
|
|
|||
|
|
|
|
|
|
|
|
||||
|
|
|
|
10 |
|
|
|
|
|
||
|
|
|
|
т |
|
8 |
|
|
|
VI |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
1 |
|
9 |
|
Z |
|
|
|
|
|
|
и |
|
|
|
|
|
VI I |
||
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
4 |
|
7 |
|
|
V |
||
|
|
з |
|
|
5 |
|
|
||||
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|||
|
о |
|
|
|
|
|
|
|
|
|
|
|
п |
|
Рис. 1.12. Разбиение пространства на ряд областей |
||||||||
е |
|
|
|
|
|
|
|
|
|
|
|
Р |
Пространство разбито на ряд областей. Некоторые из них |
сод ржат хотя бы одну точку и отнесены машиной к соответствующим образам. Эти области отмечены на рис. 1.12 различ-
11
|
ной штриховкой. Остальные области (их горазо больше, чем |
|||||||
|
первых) остались «пустыми» и ни к какому образу не отнесены. |
|||||||
|
Совершенно ясно, что на этом нельзя заканчивать процесс |
|||||||
|
обучения. Подлежащая определению новая точка может попасть |
|||||||
|
в «пустую» область, и ее нельзя будет отнести ни к какому |
|||||||
|
образу. Необходимо каким-то способом поименовать все без |
|||||||
|
исключения области пространства. Продолжение первой части |
|||||||
|
алгоритма, разумеется, не может привести к этой цели, так как |
|||||||
|
число «пустых» областей будет все быстрее и быстрее опережать |
|||||||
|
|
|
|
|
|
|
|
Н |
|
число появившихся точек. Обратимся к основной нашей идееУ– |
|||||||
|
предположению о компактности множеств точек, соответствую- |
|||||||
|
щих образам. Исходя из этого предположения естественноТотне- |
|||||||
|
|
|
|
|
|
|
|
Б |
|
сти «пустые» области к тем же образам, что и какая-нибудь из |
|||||||
|
соседних поименованных областей. При этом такая манипу- |
|||||||
|
ляция с «пустыми» областями, окруженными одноименными |
|||||||
|
частями пространства, будет совершенно однозначна и не при- |
|||||||
|
|
|
|
|
областями |
|
||
|
ведет к ошибкам (например, пустая область y на рис. 1.12 вполне |
|||||||
|
определенноотноситсякобразу А). |
й, лежащими у границ |
||||||
|
Только |
при |
операциях с |
|
|
|||
|
множеств, будутвозможнынеоднозначностьиошибки. «Пустая» |
|||||||
|
область z (см. рис. 1.12), нап |
|
, может быть ошибочно отне- |
|||||
|
сенакобразуС. |
т |
имер |
|
|
|||
|
Расширение поимен ванных частей пространства можно |
|||||||
|
костей, ра |
деляющие одноименные области. Оставшиеся пос- |
||||||
|
представить как выбрасываниео |
кусков плоскостей, отделяю- |
||||||
|
з |
|
|
|
|
|
|
|
|
щих «пустые» облас и от соседних поименованных. Разуме- |
|||||||
|
ется, как л шн |
, могут выбрасываться также и куски плос- |
||||||
|
о |
|
|
|
|
|
|
|
|
ле так й |
перации куски плоскостей и образуют искомую |
||||||
|
разделяющую гиперповерхность. |
|
|
|||||
|
Весьма важно выбрасывать куски плоскостей более или менее |
|||||||
Р |
равномерно по пространству. Не соблюдая этого правила, можно |
|||||||
прийти к заведомо неправильной разделяющей поверхности. |
||||||||
|
Если, например, начав с некоторой поименованной области, |
|||||||
еприсоединить к ней все соседние «пустые», к образовавшейся |
области – все «пустые», соседние с ней и т. д., можно почти все
12
|
пространство отнести к тому же образу, что и исходная область, |
|||||||
|
ибо после окончания первой части алгоритма поименованные |
|||||||
|
области, как редкие островки, «затеряны» среди областей не |
|||||||
|
поименованных. На рис. 1.13 заштрихована область, которую |
|||||||
|
можно отнести к образу С, если действовать таким методом, |
|||||||
|
начинаясоднойизпоименованныхобластейэтогообраза. |
У |
||||||
|
|
|||||||
|
|
|
|
|
|
|
Т |
|
|
|
|
|
|
|
Н |
|
|
|
|
|
|
|
|
Б |
|
|
|
|
|
|
|
й |
|
|
|
|
|
|
|
и |
|
|
|
|
|
|
|
|
р |
|
|
|
|
|
|
Рис. 1.13. Область, отнесенная к образу С |
|
|
||||
|
Для того чтобы обеспеч ть более ли менее равномерное |
|||||||
|
|
|
плоскости |
|
|
|
|
|
|
выбрасывание куск в пл ск стей, можно прибегнуть к следую- |
|||||||
|
|
ят |
|
|
|
|
|
|
|
щему приему. Вначале следует выяснить, нет ли плоскостей, |
|||||||
|
которые целиком с с |
из лишних кусков, и, если такие най- |
||||||
|
|
и |
. Затем сначала выбросить «лиш- |
|||||
|
дутся, выброси ь э |
|
||||||
|
ние» куски одной з ос авшихся плоскостей, потом другой и т.д. |
|||||||
|
Можно дока ать, что при этом поименованными окажутся все |
|||||||
|
частипространства. |
|
|
|
|
|
|
|
|
п |
зИсключение лишних плоскостей |
|
|
||||
е |
|
|
|
|
|
|
|
|
|
Вернемсяок рис. 1.12. Легко видеть, что плоскости I, III и V |
|||||||
Р |
могут быть исключены целиком. Они не содержат кусков, |
выбрасывание которых привело бы к появлению противоречий. Исключив последовательно эти три плоскости, придем к ситуации, изображенной на рис. 1.14. Ни одна из оставшихся плос-
13
костей не может быть выброшена целиком. Каждая из них содержит хотя бы один кусок, исключение которого привело бы кпротиворечию.
|
|
|
|
|
|
IV |
|
|
|
II |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
M |
|
|
|
|
|
|
У |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
N |
3 |
|
|
|
|
7 |
|
|
Т |
|
|
|
|
|
|
|
|
10 |
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Н |
|
|||
|
|
|
|
|
|
|
|
8 |
|
|
|
VI |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
9 |
|
|
|
VI I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
5 |
|
|
Б |
|
|
|
|
|
|
|
|
|
|
|
|
й |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
Рис. 1.14. Исключение лишних плоскостей |
|
|
|
||||||||
|
|
|
|
|
|
|
|
куски |
|
|
|
|
|||
|
|
|
Исключение лишн х кусков плоскостей |
|
|
||||||||||
|
|
|
|
|
|
|
разделено |
|
|
|
|
|
|||
|
|
Проверяя поочередно все |
|
|
плоскости II, затем все куски |
||||||||||
|
плоскости IV и т. д. и выб асывая те куски, исключение |
||||||||||||||
|
|
|
|
|
|
о |
ечиям, придем к ситуации, при |
||||||||
|
которых не приводит к п |
тив |
|||||||||||||
|
|
|
|
|
т |
|
|
|
|
на поименованные области |
|||||
|
которой все пространство |
|
|
|
|||||||||||
|
(рис. 1.15). |
и |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
з |
|
|
|
|
|
|
B |
|
|
|
|
|
|
|
о |
|
A |
|
|
|
|
2 |
|
|
|
|
||
|
п |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
||
е |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
||
Р |
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
C
Рис. 1.15. Исключение лишних кусков плоскостей
14
|
|
Процесс обучения закончен. Теперь, чтобы узнать оче- |
|||||||||||
|
|
редной объект, машине достаточно определить, в какой из |
|||||||||||
|
|
областей пространства лежит соответствующая ему точка. |
|||||||||||
|
|
Впрочем, машина может и ошибиться. Как видно из рис. 1.15, |
|||||||||||
|
|
разбиение получилось далеко не идеальным. Значительная |
|||||||||||
|
|
часть области В отнесена к образу С, а «кусочки» областей А |
|||||||||||
|
|
и С попали в образ В. Это произошло потому, что в ходе |
|||||||||||
|
|
обучения машины не встретились точки, расположенные в |
|||||||||||
|
|
этих частях пространства. По всей видимости, если процесс |
|||||||||||
|
|
обучения был бы более длительным, относительная площадьУ |
|||||||||||
|
|
неправильно поименованных кусков (а значит, и вероятность |
|||||||||||
|
|
в будущем ошибок при распознавании) была бы меньшеТ. Од- |
|||||||||||
|
|
нако увеличение длительности обучения приводит к расши- |
|||||||||||
|
|
рению требуемого |
|
объема памяти машины. Есть |
другие |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Н |
|
|
|
способы повышения надежности распознавания. О них будет |
|||||||||||
|
|
сказано далее. |
|
|
|
|
|
|
Б |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Описан е алгор тма |
|
|
||||
|
|
Машина, естественно, опе |
|
й |
|
||||||||
|
|
ует в действительности не с |
|||||||||||
|
|
чертежами, а с числами. П |
|
|
действия машины на том |
||||||||
|
|
же примере (см. рис. 1.1). |
оследим |
|
|
||||||||
|
|
|
|
|
|
|
|
р |
|
|
|
||
|
|
|
|
|
Проведение секущих плоскостей |
|
|||||||
|
|
|
|
|
|
|
о |
|
|
|
|
||
|
|
Запомн в коорд на ы первых двух точек, машина выбирает |
|||||||||||
|
|
|
|
|
т |
|
|
|
|
|
|
||
|
|
случайно п ч сел |
λi (ii = 1, 2, 3,..., п, где п – размерность |
||||||||||
|
|
|
|
|
рецепторов). Затем машина определяет значение |
||||||||
|
|
двухсумм: |
и |
|
|
|
|
|
|
|
|||
|
|
|
з |
|
|
|
|
|
|
|
|
||
|
|
пространства |
|
|
σ(1) = Σλi |
x ξi (1) |
|
(1.1) |
|||||
|
|
или |
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
|
|
|
|
|
|
|
|
|
|
|
|
|
Случайный выбор коэффициентов означает, что каждый очередной ко- |
|||||||||||
|
эффициент может с равной вероятностью оказаться любым из некоторого |
||||||||||||
е |
|
|
|
|
|
|
|
|
|
|
|
||
Р |
конечного или бесконечного ряда чисел. Для осуществления такого выбо- |
||||||||||||
ра в машинах используют специальные датчики случайных чисел. |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
σ(2) = Σλi x ξi (2), |
(1.2) |
||||||
|
где xξi(1) – координаты первой, а ξi(2) – координаты второй точки. |
||||||||||||
|
После этого машина выбирает, также случайным образом, неко- |
||||||||||||
|
торое число λп+1, большее, чем меньшая из сумм σ(1) и σ(2), но |
||||||||||||
|
меньшее, чем большая из этих сумм. Если образовать две новые |
||||||||||||
|
суммы |
|
|
|
|
|
|
|
|
|
|
Т |
|
|
|
|
|
|
σ(1) = Σλi x ξi (1) – λn+1; |
||||||||
|
|
|
|
|
(1.3) |
||||||||
|
|
|
|
|
σ |
(2) |
= Σλi x ξi |
(2) |
– |
λn+1, |
У |
||
|
|
|
|
|
|
|
|
(1.4) |
|||||
|
то, учитывая способ, которым было выбрано число λn+1, легко |
||||||||||||
|
видеть, что одна из этих сумм обязательно будет отрицательной, |
||||||||||||
|
а другая – положительной. Геометрически же этоНозначает, что |
||||||||||||
|
|
|
|
|
|
|
|
|
|
этой |
|
||
|
найденные машиной числа λ1, λ2 ,..., λn+1 есть коэффициенты |
||||||||||||
|
плоскости, |
разделяющей две |
|
точки.БДействительно, при |
|||||||||
|
|
|
|
|
|
|
|
|
наши |
плоскости |
|||
|
подстановкевлевуючастьуравнен я |
|
|||||||||||
|
|
|
|
|
|
|
р |
|
|
|
|
||
|
|
|
|
|
|
Σλi x ξi – |
λn+1 |
= 0 |
(1.5) |
||||
|
координатоднойизт чекп лучаетсяотрицательныйрезультат, а |
||||||||||||
|
|
|
|
т |
|
|
|
|
|
|
положительный. |
||
|
при подстановке к |
рдинат другой точки – |
|||||||||||
|
Известно, что под бные результаты полу-чаются в том случае, |
||||||||||||
|
|
|
|
и |
|
|
|
|
|
|
|
|
|
|
когдаточкилежатпооразныестороныотплоскости. |
||||||||||||
|
|
|
з |
|
|
|
|
|
|
|
|
|
|
|
|
Условимся обознача ь положение данной точки относительно |
|||||||||||
|
плоскости |
начком «1», если при подстановке координат этой |
|||||||||||
|
|
о |
|
|
|
|
|
|
|
|
|
||
|
точки в левую часть уравнения плоскости получается положи- |
||||||||||||
|
тельн е число, и значком «0» в противном случае. Будем |
||||||||||||
|
п |
|
|
|
|
|
|
|
|
|
|
|
|
|
г в рить, что точка имеет знак «1» или знак «0» относительно |
||||||||||||
е |
|
|
|
Представим часть |
памяти |
машины после |
|||||||
|
данн й л скости. |
||||||||||||
Р |
роведения первой разделяющей плоскости (см. рис. 1.2) в виде |
табл. 1.1, которую будем в дальнейшем называть таблицей знаков.
16
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а 1.1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
Таблица знаков |
|
|
|
|
|
|
|
|
|||||
|
|
Номер |
|
|
Образ |
|
Номер плоскости |
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
точки |
|
|
|
I |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Знак точки |
|
|
У |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
1 |
|
|
|
А |
|
|
0 |
|
|
|
|
|
|
Т |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
2 |
|
|
|
В |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Н |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
Б |
|
|
|
|
|
||
|
|
При появлении следующей (третьей) точки (см. рис. 1.3) |
||||||||||||||||||
|
машина определяет ее знак относительно первой плоскости и |
|||||||||||||||||||
|
заполняет третью строку таблицы знаков (табл. 1.2). |
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
й |
Т а б л и ц а 1.2 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
Табл ца знаков |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
р |
|
|
|
Номер плоскости |
|
|
||||||
|
|
Номер |
|
|
|
|
|
и |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
I |
|
|
|
|
|
|
|
||||
|
|
точки |
|
|
|
|
Об аз |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
Знак точки |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
и |
оА |
|
|
|
0 |
|
|
|
|
|
|
|
|||||
|
|
з |
|
|
|
В |
|
|
|
1 |
|
|
|
|
|
|
|
|||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
3 |
|
|
|
|
|
А |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
оочередно сравнивает последнюю строку таблицы |
|
с каждой |
|
|
||||||||||||||
|
|
|
|
|||||||||||||||||
|
|
Затем машина производит поиск оппонента, т. е. |
||||||||||||||||||
е |
|
|
|
|
Противоречием считается совпадение |
|||||||||||||||
Р |
из редыдущих строк. |
|||||||||||||||||||
пстрок, относящихся к |
|
разным |
образам. В данном случае |
|||||||||||||||||
|
|
противоречие налицо: точка 3, относящаяся к образу А, попала по ту же сторону от плоскости I, что и относящаяся к образу В точка 2 .
17
Машина проводит новую плоскость II, разделяющую точки 2 и 3 (см. рис. 1.4) и вычисляет знаки всех занесенных в таблицу точек относительно этой плоскости.
Таблица знаков принимает вид табл. 1.3.
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а 1.3 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
Таблица знаков |
|
|
|
|
|
||||
|
|
Номер |
|
|
Образ |
|
Номер плоскости |
У |
|||||||
|
|
|
|
|
I |
|
II |
|
|
|
|||||
|
|
точки |
|
|
|
|
|
|
|
|
|
Н |
|
|
|
|
|
|
|
|
|
|
|
|
|
Знак точки |
Т |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
1 |
|
|
А |
|
|
|
|
0 |
|
1 |
|
|
|
|
|
2 |
|
|
В |
|
|
|
|
1 |
Б |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
||||
|
|
3 |
|
|
А |
|
|
|
|
1 |
1 |
|
|
|
|
|
|
Противоречие ликвидировано. |
й |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
рис |
|
|
|
|
|
|
|
|
Появляются точки 4, 5 и 6 (см. |
. 1.5). После вычисления |
||||||||||||
|
их знаков приходим к табл. 1.4. |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
р |
|
|
Т а б л и ц а 1.4 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
Таблица знаков |
|
|
|
|
|
||||
|
|
Номер |
|
|
т |
|
|
|
Номер плоскости |
|
|
||||
|
|
|
и |
|
|
|
I |
|
II |
|
|
|
|||
|
|
|
|
|
Образ |
|
|
|
|
|
|
|
|||
|
|
точки |
|
|
о |
|
|
Знак точки |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
з |
А |
|
|
|
0 |
|
1 |
|
|
|
|||
|
|
1 |
|
|
|
|
|
|
|
|
|
||||
|
|
о |
|
|
В |
|
|
|
1 |
|
0 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
||||
|
|
3 |
|
|
А |
|
|
|
1 |
|
1 |
|
|
|
|
|
п |
|
|
С |
|
|
|
0 |
|
0 |
|
|
|
||
|
4 |
|
|
|
|
|
|
|
|
|
|||||
|
5 |
|
|
С |
|
|
|
0 |
|
0 |
|
|
|
||
Р |
|
6 |
|
|
В |
|
|
|
0 |
|
0 |
|
|
|
|
|
Поиск оппонентов, произведенный после появления точки 4, а |
||||||||||||||
езатем после появления точки 5, дает отрицательный результат. |
После появления шестой точки обнаруживается противоречие: 18
точка 6 (образ В) лежит по ту же сторону отплоскостей I иII, что и точки 4 и 5 (образ С). Проводится плоскость III, разделяющая точки 4 и 6, а затем, после нового поиска оппонента, – плоскость IV, разделяющая точки 6 и 5 (см. рис. 1.6). Знаки всех точек относительноновойплоскостизаносятсявтабл. 1.5.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а 1.5 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
Таблица знаков |
|
|
|
|
|
Т |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
У |
|||||||||
|
|
|
Номер |
|
|
|
|
|
|
|
|
|
|
Номер плоскости |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
Образ |
|
I |
|
|
II |
|
Н |
|
|
|
|
|
||||||||
|
|
|
точки |
|
|
|
|
|
|
|
|
|
|
|
Знак точки |
|
|
|
|
|
|
||||||
|
|
|
1 |
|
|
|
|
А |
|
|
|
0 |
|
1 |
|
|
Б |
|
1 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
||||||||
|
|
|
2 |
|
|
|
|
В |
|
|
|
1 |
|
0 |
|
|
|
1 |
|
|
0 |
|
|
|
|||
|
|
|
3 |
|
|
|
|
А |
|
|
|
1 |
|
1 |
|
|
|
1 |
|
|
1 |
|
|
|
|||
|
|
|
4 |
|
|
|
|
С |
|
|
|
0 |
|
й |
|
1 |
|
|
1 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
||||||||
|
|
|
5 |
|
|
|
|
С |
|
|
|
0 |
|
0 |
|
|
|
0 |
|
|
1 |
|
|
|
|||
|
|
|
6 |
|
|
|
|
В |
|
|
|
0 |
|
0 |
|
|
|
0 |
|
|
0 |
|
|
|
|||
|
|
|
Противоречия вновь ликв д |
ованы. |
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
вид табл. 1.6. |
|
|
точек |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
С появлением новых |
|
машина |
продолжает заполнять |
|||||||||||||||||||||
|
|
таблицу знаков. С кажд й н в й точкой в таблице появляется |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
новая строка, с кажд й плрскостью – новый столбец. После |
|||||||||||||||||||||||||
|
|
|
|
|
и |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
завершения первой час и алгоритма таблица знаков имеет |
|||||||||||||||||||||||||
|
|
|
|
з |
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а 1.6 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
Таблица знаков |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
Н мер |
Образ |
|
|
|
|
|
|
Номер плоскости |
|
|
|
|
|
|
|||||||||||
|
|
|
I |
|
|
II |
|
III |
|
IV |
|
V |
|
VI |
|
VII |
|
||||||||||
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
точкио |
|
|
|
|
|
|
|
|
|
Знак точки |
|
|
|
|
|
|
|
|
|||||||
Р |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
п1 |
2 |
|
|
3 |
|
4 |
|
5 |
|
|
6 |
|
|
7 |
|
8 |
|
|
9 |
|
|
|||||
|
|
1 |
А |
|
0 |
|
1 |
|
1 |
|
|
1 |
|
|
0 |
|
1 |
|
|
1 |
|
|
|||||
|
|
2 |
В |
|
1 |
|
0 |
|
1 |
|
|
0 |
|
|
0 |
|
1 |
|
|
0 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
Окончание табл. 1.6 |
||||
|
2 |
|
|
|
|
|
|
|
|
|
1 |
3 |
4 |
5 |
6 |
|
7 |
8 |
9 |
||
3 |
А |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
|
4 |
С |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
|
5 |
С |
0 |
0 |
0 |
1 |
|
1 |
0 |
У |
|
|
1 |
|
||||||||
6 |
В |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
|
7 |
С |
0 |
0 |
0 |
0 |
|
1 |
Т |
|
|
|
0 |
1 |
|
|||||||
8 |
В |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
|
9 |
С |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
|
10 |
А |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
|
|
По своему содержанию табл. 1.6 эквивалентна рис. 1.12. Каж- |
|||||||
|
дая строка таблицы соответствует одной из заштрихованныхН |
на |
||||||
|
|
|
|
|
|
й |
|
|
|
рис. 1.12 частей пространства и представляет собой своеобраз- |
|||||||
|
ный код такой области – выпуклого n-мерногоБмногогранника, |
|||||||
|
|
|
|
|
и |
|
||
|
образованного секущими плоскостями . Этот код указывает, по |
|||||||
|
|
|
|
р |
|
|
||
|
какую сторону от каждой из секущ х плоскостей лежит много- |
|||||||
|
гранник, содержащийданнуюточку. |
|
||||||
|
|
|
|
о |
|
|
|
|
|
|
|
Исключение лишних плоскостей |
|
||||
|
стр ки со всемизаполненияостальными. «Выбрасывание» столбца означает, |
|||||||
|
После |
аблицы знаков машина переходит |
ко |
|||||
|
второй части алгор |
ма. В начале из таблицы знаков «выбра- |
||||||
|
|
|
з |
|
|
|
|
|
|
сывается» столбецт, соответствующий плоскости I. Затем произ- |
|||||||
|
водится по ск прот воречий, т.е. поочередное сравнение каждой |
|||||||
|
|
его |
|
|
|
|
||
|
п |
цифры при этом не учитываются. Если противоречий не |
||||||
|
что |
|||||||
|
обнаруживается, т. е. не находится одинаковых строк, отно- |
|||||||
е |
|
|
|
|
|
|
||
|
сящихся к разным образам, столбец исключается из памяти |
|||||||
Р |
машины. В противном случае столбец «восстанавливается», т. е. |
|||||||
го цифры учитываются в последующих операциях. Машина |
||||||||
|
Мы называем многогранниками как замкнутые, так и незамкнутые области пространства, границы которых состоят из кусков плоскостей.
20