Параллельное программирование


Алгоритм. Пример - часть 2


Если мы и теперь не достигли успеха…

В рассматриваемом примере верхнюю поверхность (где следует искать решение) образуют грани (6.6). Поскольку переименование малого количества граней в соответствии с (6.7) не имеет смысла, составим для этих граней и их нормалей таблицу, включающую матрицу косинусов углов между нормалями. Соответствующие косинусы считаем по (6.9) и (6.10), таблицу строим по образу таблицы 6.1. Матрица S в таблице выделена.

Реализуем первый этап алгоритма поиска вершины, исключив из рассмотрения три последние строки и столбцы.

Выберем грань q1. Максимальные косинусы соответствующей (первой) строки матрицы S указывают на систему граней {q1, q2, q3}. Решаем уравнения граней совместно и проверяем решение на выполнение всех неиспользованных ограничений задачи. Получаем вершину E(13, 8, 4).

Таблица 6.4.

ГраньНормальN1 N2N3N4 N5 N7 N8 N9
q1 N1 l 0,59 0,59 0,067 0,171

0,026

0,09 -0,99
q2N20,5910,9-0,43-0,29-0,560,625-0,56
q3N30,590,91-0,25-0,125-0,280,46-0,84
q4N40,067-0,43-0,2510,99-0,16-0,975-0,16
q5N50,171-0,29-0,1250,991-0,27-0,92-0,27
q7N70,026-0,56-0,28-0,16-0,27100
q8N80,090,6250,46-0,975-0,92010
q9N9-0,99-0,56-0,84-0,16-0,27001

Выберем грань q2. Максимальные косинусы второй строки матрицы указывают на систему граней {q2, q3, q1}, что соответствует уже найденной вершине.

Для грани q3 получаем ту же систему образующих граней, т.е. ту же вершину E.

По строке табл. 6.4 (матрицы S), соответствующей q4, находим систему {q1, q4, q5}, решением которой является вершина L{6, 10, 4}.

Анализируя строку грани q5, вновь получаем ту же вершину.

Таким образом, мы добились успеха без рассмотрения координатных плоскостей. Однако для полноты анализа исследуем матрицу S полностью.

Анализ строк 1, 3, 4, 5 порождает те же результаты. Максимальные косинусы второй строки, соответствующей грани q2, указывают на систему {q2, q3, q8}. Решаем уравнения совместно и проверяем выполнение всех неиспользованных ограничений.


Начало  Назад  Вперед