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



Оценка сложности


Алгоритм поиска вершины многогранника допустимых решений предполагает ряд этапов.

  1. Определение верхней (нижней) поверхности многогранника. Он заключается в проверке выполнения всех ограничений для точки начала координат. Сложность этого этапа можно оценить как O(nm). Число r граней-границ, образующих одну поверхность, не превышает m - 1,

    r

    m - 1 (6.12)

  2. Нахождение матрицы S косинусов углов между нормалями к действительным и возможным граням поверхности. Число таких косинусов для симметричной матрицы с учетом известных углов между осями координат составляет

     \begin{equation} \frac{1}{2}((r+n)^2- r - n^2). \end{equation}

    (6.13)

    Каждый косинус отыскивается в результате скалярного произведения единичных векторов нормалей, имеющего сложность O(6n). С учетом (6.12) можно оценить сложность алгоритма нахождения матрицы S как

    O(3m2n + mn2). (6.14)

  3. Выделение n максимальных косинусов в каждой строке матрицы S. Сложность этой операции упорядочения по одной строке можно оценить как

    O((m + n)2) (6.15)

  4. Наконец, для выделенных граней необходимо решить систему n линейных уравнений, соответствующих этим граням. Сложность алгоритма такого решения составляет O(n3). Общая сложность выполнения этого этапа для всех строк составляет

    O(mn3 + n4). (6.16)

Как видим, сложность нахождения вершины (точнее, всех возможных вершин) полиномиальная. Сумма степеней основных параметров n и m в составе членов полинома не превышает четырех.

В заключение отметим, что наметился общий прием распараллеливания решения задач оптимизации. Это не просто прием распараллеливания вычислений. Он определяет стратегию коллективного поведения компьютеров вычислительной системы или вычислительной сети при совместном решении задачи.

Алгоритм решения задачи предполагает, на разных этапах или глобально, варианты поиска промежуточных или окончательных решений. Компьютеры "расходятся" по отдельным вариантам поиска. Отдельный компьютер может достичь или не достичь успеха, реализуя стратегию "проб и ошибок". Тот компьютер, что достиг успеха, оперативно извещает другие компьютеры, которые прерывают свои действия. Все компьютеры используют успех одного для продолжения выполнения задачи.

Такой прием используется для поиска смежной вершины (по разным ребрам) с "лучшим" значением целевой функции при решении задачи ЛП. Такой же прием может применяться и для нахождения опорного плана решения этой же задачи. Ведь грани верхней (нижней) поверхности многогранника допустимых решений могут распределяться между компьютерами. Компьютер может для взятой на обработку грани найти все косинусы между ее нормалью и нормалями с другими гранями, и здесь не следует бояться повторения счета отдельных косинусов на разных компьютерах. Затем компьютер может выбрать n максимальных косинусов и проверить выделенную таким образом точку. Как только вершина найдена, работа других компьютеров по аналогичному поиску может быть прервана.

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

Все сказанное наилучшим образом согласуется с SPMD-технологией "одна программа — много потоков данных ".

Вместе с тем, отметим, что здесь предлагается "инженерное" решение задачи на основе ее "физического смысла". Работа по обоснованию и строгому доказательству основных положений должна быть продолжена. Скорее всего, мы наблюдаем интересные свойства выпуклого многогранника допустимых решений задачи ЛП, не всегда умея их строго доказать.




Содержание  Назад