Cтраница 3
Решим в качестве примера применения алгоритма I задачу упорядочения девяти чисел, заданных указанным в табл. 2.1 исходным списком. Пусть меньшие числа считаются более предпочтительными. [31]
В последние годы в городах особенно остро встала задача упорядочения библиотечной сети. Это связано с крупными успехами в жилищном строительстве. В городах возникали и быстро росли новые большие жилые районы массовой застройки, куда переселилась значительная часть городского населения. [32]
Следует отметить, что в предыдущем доказательстве ЛФ-полноты задачи упорядочения важную роль играли большие значения времен выполнения. Нам могут возразить, сказав, что действительный размер задачи зависит не от длины строки, в которой записаны времена выполнения, а от суммы величин этих времен выполнения. [33]
Одним из методов оптимизации, применяемых при решении задач упорядочения перебора вариантов, является метод динамического программирования. Этот метод в отличие от методов линейного программирования не зависит от характера целевой функции и не требует линейности исходных зависимостей. Тогда на каждом шаге выбирают такой вариант, при котором выбранная последовательность вариантов была наилучшей с точки зрения заданного критерия оценки. Решение на каждом шаге выбирают, исходя не из узких интересов этого шага - а из интересов задачи в целом, и далеко не всегда стремление к максимальному эффекту на каком-то шаге приводит к максимальному эффекту для всей задачи. [34]
Составление графика капитального ремонта линейной части трубопровода представляет собой задачу упорядочения. Схема процесса упорядочения заключается в следующем. Пусть а есть совокупность последствий при выполнении сначала задачи А, а затем В. Пусть р есть совокупность последствий при выполнении сначала задачи В, а затем А. [35]
Всего лишь одна стадия поразрядной сортировки MSD почти полностью решает задачу упорядочения, как показывает рассматриваемый пример файла произвольной организации, состоящий из 8-разрядных целых чисел. Первая стадия поразрядной сортировки MSD по двум старшим разрядам ( слева) делит исходный файл на четыре подфайла. На следующей стадии каждый такой подфайл делится на четыре подфайла. Поразрядная сортировка MSD по трем старшим разрядам ( справа) делит файл на восемь подфайлов за один проход, на котором также выполняются распределение и подсчет. На следующем уровне каждый из этих подфайлов снова разбивается на восемь частей, при этом в каждой такой части содержатся всего лишь несколько элементов. [36]
Для доказательства этого утверждения предположим, что существует полиномиальный алгоритм решения нашей задачи упорядочения, заданной в виде задачи распознавания. [37]
Процедура TRF является рекурсивной, она имеет в качестве единственного входного параметра задачу упорядочения; результатом ее выполнения оказывается оптимальная перестановка по отношению к входной задаче. Выполнение оператора return выражение, встречающегося в процедуре, заключается в вычислении выражения и возврате в точку вызова процедуры с вьиисленным значением в качестве результата. Результат выполнения процедуры TRF, вообще говоря, не единствен, потому что может существовать более одного р-максимального множества. Однако независимо от выбора такого множества TRF дает оптимальную перестановку. [38]
После того как получена оптимальная точка возврата, отличная от начальной, возникает задача упорядочения элементов информации справа и слева от точки возврата. Упорядочение справа от точки возврата аналогично рассмотренному выше случаю. Упорядочение массива слева от точки возврата выполняется перестановкой двух любых s и q ( s q) элементов информации. [39]
Формулировка должна быть достаточно общей, чтобы охватывать по возможности все практические приложения задач упорядочения. [40]
Перед тем как перейти к результатам, упомянутым ранее, рассмотрим другой тип задач упорядочения, в которых величины времен выполнения способствуют возникновению Л Я-полноты. [41]
В сущности, в настоящее время отсутствуют способы доказательства того, что для решения задачи упорядочения на трех процессорах для системы заданий с единичными временами выполнения или других задач такого типа действительно требуется экспоненциальное время. Однако мы можем сделать следующее: показать, что существует большой класс задач, называемых ЛФ-полными, которые либо все разрешимы за полиномиальное время, либо все неразрешимы за полиномиальное время. В класс ЛТ-полных задач входят многие хорошо известные задачи [86], такие, как задача коммивояжера или общая задача упорядочения п работ на m процессорах, для которых математики и специалисты в области информатики десятилетиями безуспешно ищут решения, требующие менее чем экспоненциального времени. Таким образом, имеются серьезные основания считать, что ни одна из JVP-полных задач неразрешима за полиномиальное время. [42]
Если заданы т пар точек, которые должны быть соединены на плоскости Р, то задача упорядочения сводится к определению последовательности соединения этих т пар точек. От этой последовательности зависит не только общая длина соединений, но также и успех выполнения процесса соединений в целом. [43]
Описанные выше алгоритмы могут быть рекомендованы для решения различных классов ЗПР для ОФХТС в виде задач упорядочения и группировки объектов при учете одновременно многих сложных ( количественных, качественных) КЭ или признаков подобия. [44]
К достоинствам этого метода следует отнести простоту его реализации, поскольку в общем случае решение задачи упорядочения сетевого графика основано либо на использовании специальных программ, либо на достаточно трудоемких графоаналитических вычислениях на бумаге. [45]