Cтраница 1
Экстремальная комбинаторная задача состоит в следующем. [1]
Экстремальная комбинаторная задача называется NP-трудной в сильном смысле, если соответствующая ей задача распознавания является ТУР-трудной в сильном смысле. [2]
Изложены три широких класса экстремальных комбинаторных задач: о разбиениях чисел, о системах множеств и о системах векторов. Продемонстрированы возможности практического использования решений экстремальных комбинаторных задач в информатике и вычислительной технике. [3]
Рассматриваемая задача относится к классу экстремальных комбинаторных задач. [4]
Эта задача относится к классу сложных экстремальных комбинаторных задач транспортного типа. [5]
Глубина матрицы связана с одной из наиболее важных экстремальных комбинаторных задач - задачей о покрытии ( о ней будет идти речь в гл. Аналогично, ширина ( О, 1) - матрицы определяется как такое минимальное число ее столбцов, что сумма элементов в каждой строке образованной ими подматрицы положительна. Ширина ( О, 1) - матрицы А совпадает с глубиной транспонированной матрицы Ат. Ширина связана с известной задачей о минимальной системе представителей, родственной задаче о покрытии. [6]
Модели С1 - С7 являются типичными представителями экстремальных комбинаторных задач. [7]
Вместе с тем использование приближенных методов решения экстремальных комбинаторных задач, таких, как случайный поиск или какое-то приоритетное правило, основанное на особенностях задачи, здесь осложнено тем, что расчет критерия оптимальности для каждого плана-графика Г / требует решения задачи линейного программирования, что в свою очередь связано с огромными вычислительными трудностями. [8]
В главе 5 показаны методы использования результатов решения экстремальных комбинаторных задач о вложимости разбиений чисел при проектировании АСУ. Здесь приведены комбинаторные модели для исследования процессов управления выполнением заданий АСУ и распределения памяти ЭВМ. Демонстрируется применение теорем о вложимости для расчета размера оперативной памяти ЭВМ, приводятся определения ряда новых инженерных понятий, связанных с применением методов комбинаторного анализа для исследования функционирования АСУ. Предлагается новый способ оценки эффективности алгоритмов, характеризуемых экстремальными границами. [9]
Основная цель рассматриваемых в настоящей главе примеров использования тематики экстремальных комбинаторных задач на множестве разбиений чисел состоит в формировании у читателя методических навыков по формализации исследуемых здесь процессов с помощью понятия вложимости разбиений и по использованию экстремальных результатов для решения практических задач. Поэтому в формулировках конкретных практических задач не приводятся подробные определения исследуемых процессов и не описываются их причинно-следственные связи с процессом функционирования АСУ в целом. [10]
В настоящее время среди методов нахождения оп тимального решения экстремальных комбинаторных задач ведущее место занимает метод ветвей и границ, сущность которого состоит в замене случайного перебора целенаправленным. При этом очень важным является наличе априорных критериев, с помощью ко-торых имеется возможность в процессе перебора отбрасывать множества решений, в которых нет оптимального. [11]
Поставленная задача оптимального планирования сроков проведения предупредительного ремонта относится к классу экстремальных комбинаторных задач. [12]
Приведенные примеры показывают, что во многих случаях задачи структурного синтеза являются экстремальными комбинаторными задачами, которые могут быть сведены к задачам дискретного программирования. Оценка трудоемкости получения точных решений задач этого класса позволяет сделать вывод, что при реальном проектировании полупение точных решений либо невозможно, либо требует больших затрат машинного времени. [13]
Другим важным толчком к построению теории дискретного программирования явился новый подход к некоторым экстремальным комбинаторным задачам, разработанный в середине 50 - х годов и основанный на использовании линейного программирования. [14]
Задача объединения электростанций или общая задача определения оптимального подграфа с ограниченными степенями вершин по существу связана с большинством экстремальных комбинаторных задач, для которых известны хорошие алгоритмы решения. Эти алгоритмы хороши в том смысле, что объемы вычислений при их применении растут как степенные функции при увеличении размерности задачи. В случае, когда все di2, мы получаем задачу, очень близкую к задаче коммивояжера. Если этот подграф связен, то мы получим минимальный маршрут коммивояжера при длинах ребер ctj. К сожалению, задача, получаемая после добавления к задаче объединения электростанций дополнительного ограничения связности подграфа, пока не решена. [15]