The 25 references with contexts in paper V. Ovchinnikov A., В. Овчинников А. (2016) “Систематизация точных методов дискретной оптимизации // Systematization of Accurate Discrete Optimization Methods” / spz:neicon:technomag:y:2015:i:6:p:288-304

1
Нечепуренко М.И., Попков В.К., Майнагашев С.М., Кауль С.Б., Проскуряков В.А., Кохов В.А., Грызунов А.Б. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. Сиб. отд-ние, 1990. 515 с.
Total in-text references: 6
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

  2. In-text reference with the coordinate start=26049
    Prefix
    NP Ветвей и границ Экспоненциальная 2 Определение минимального остовного дерева Установление порядка соединения попарно связанных объектов Взвешенный неориентированный граф P Жадного выбора O(n2) – [5], O(m log log n) –
    Exact
    [1]
    Suffix
    3 Поиск простой цепи с минимальной суммой весов ребер Определение маршрута минимальной длины Взвешенный неориентированный (ориентированный) граф P Дейкстры Для разреженных графов: O(m logn) – [ 7], O(m log logD) – [1], D – максимальная длина 4 Поиск гамильтонова цикла с минимальной суммой весов ребер Определение замкнутого маршрута минимальной длины Взвешенный не

  3. In-text reference with the coordinate start=26253
    Prefix
    дерева Установление порядка соединения попарно связанных объектов Взвешенный неориентированный граф P Жадного выбора O(n2) – [5], O(m log log n) – [1] 3 Поиск простой цепи с минимальной суммой весов ребер Определение маршрута минимальной длины Взвешенный неориентированный (ориентированный) граф P Дейкстры Для разреженных графов: O(m logn) – [ 7], O(m log logD) –
    Exact
    [1]
    Suffix
    , D – максимальная длина 4 Поиск гамильтонова цикла с минимальной суммой весов ребер Определение замкнутого маршрута минимальной длины Взвешенный неориентированный (ориентированный) граф NP Ветвей и границ Экспоненциальная 5 Определение наибольшего паросочетания Распределение преподавателе й по учебным курсам Двудольный неориентированный (ориентированный) граф P Форд

  4. In-text reference with the coordinate start=26644
    Prefix
    цикла с минимальной суммой весов ребер Определение замкнутого маршрута минимальной длины Взвешенный неориентированный (ориентированный) граф NP Ветвей и границ Экспоненциальная 5 Определение наибольшего паросочетания Распределение преподавателе й по учебным курсам Двудольный неориентированный (ориентированный) граф P Форда - Фалкерсо на O(n m) – [7], O(n1/2 m) –
    Exact
    [1]
    Suffix
    , 6 Построение глубинного дерева с одинаковыми весами ребер Выделение из системы подсистемы с заданным приоритетом связей Взвешенный ориентированный граф P Декомпоз иция в глубину с возвращен ием O(n) или O(m) – [7, 11] 7 Разрезание гиперграфа Декомпозиция структуры сложной системы Гиперграф NP Ветвей и границ Экспоненциальная 8 Поиск дополняющего пути в сети Выяв

  5. In-text reference with the coordinate start=27890
    Prefix
    вершин Выявление минимально необходимого количества обслуживающ их аппаратов и объектов их установки Неориентированны й (ориентированный) граф NP Ветвей и границ Экспоненциальная 12 Определение максималь-ного потока Определение максимально возможного потока информации в системе Взвешенный ориентированный граф P Форда - Фалкерсо на O(n m2) – [7], O(n 2 m1/2) –
    Exact
    [1]
    Suffix
    , O(n m log2n) – [1] 13 Установление планарности графа Установление возможности укладки коммуникаций в одной плоскости без их пересечения Неориентированны й граф P Поиск в глубину с возвращен ием (в ширину), динамичес кого программ ирования O(n 3) – [7] Заключение Основными результатами работы являются систематизированное изложение точных методов дискретной оптимизации, их

  6. In-text reference with the coordinate start=27908
    Prefix
    минимально необходимого количества обслуживающ их аппаратов и объектов их установки Неориентированны й (ориентированный) граф NP Ветвей и границ Экспоненциальная 12 Определение максималь-ного потока Определение максимально возможного потока информации в системе Взвешенный ориентированный граф P Форда - Фалкерсо на O(n m2) – [7], O(n 2 m1/2) – [1], O(n m log2n) –
    Exact
    [1]
    Suffix
    13 Установление планарности графа Установление возможности укладки коммуникаций в одной плоскости без их пересечения Неориентированны й граф P Поиск в глубину с возвращен ием (в ширину), динамичес кого программ ирования O(n 3) – [7] Заключение Основными результатами работы являются систематизированное изложение точных методов дискретной оптимизации, их сущности, возможност

2
Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. 288 с.
Total in-text references: 6
  1. In-text reference with the coordinate start=8150
    Prefix
    Отношение частичного порядка на множестве вершин ориентированного графа позволяет на основе построения глубинного остовного дерева решать, например, такие задачи как:  распознавание сильной связности ориентированного графа, т. е. существования в нем пути из каждой вершины в любую другую
    Exact
    [2]
    Suffix
    ;  отыскание блоков, мостов и расщепляющих вершин [2, 7];  установления ацикличности ориентированного графа [7];  отыскание всех гамильтоновых циклов графа (2). Построение дерева в ширину или b-дерева.

  2. In-text reference with the coordinate start=8202
    Prefix
    Отношение частичного порядка на множестве вершин ориентированного графа позволяет на основе построения глубинного остовного дерева решать, например, такие задачи как:  распознавание сильной связности ориентированного графа, т. е. существования в нем пути из каждой вершины в любую другую [2];  отыскание блоков, мостов и расщепляющих вершин
    Exact
    [2, 7]
    Suffix
    ;  установления ацикличности ориентированного графа [7];  отыскание всех гамильтоновых циклов графа (2). Построение дерева в ширину или b-дерева. Это дерево строится в соответствии со стратегией декомпозиции в ширину.

  3. In-text reference with the coordinate start=16073
    Prefix
    задачи и значений исходных данных. 4.3 Метод ветвей и границ Метод ветвей и границ является универсальным, хотя и достаточно сложным, методом точного решения широкого круга NP-полных комбинаторно-оптимизационных задач. Метод реализует направленный перебор вариантов, используя разумную эвристику – выполнять ветвление вершин не в заданной последовательности, а более перспективных
    Exact
    [2, 5, 8, 10, 12]
    Suffix
    . Вершины выбираются на основе оценки, которая с той или иной степенью достоверности позволяет сделать заключение, что подмножество вариантов, сопоставленных данной вершине дерева декомпозиции, может содержать оптимальное решение.

  4. In-text reference with the coordinate start=18527
    Prefix
    Рассматриваемый метод по сравнению с другими методами точного решения NP полных задач (поиск в ширину и глубину с возвращением) в большей степени направлен на сокращение полного перебора, однако более трудоемок. 4.4 Метод Дейкстры В настоящее время в специальной литературе
    Exact
    [2, 3, 5, 7, 10]
    Suffix
    с разной степенью детализации описан алгоритм Дейкстры поиска маршрута минимальной длины и большинством авторов как метод не трактуется. Поскольку идеи этого алгоритма могут быть использованы для решения довольно широкого круга задач дискретной оптимизации, его общую схему целесообразно рассматривать как метод.

  5. In-text reference with the coordinate start=20362
    Prefix
    Метод может быть использован для определения дополняющего пути максимальной пропускной способности в задаче о максимальном потоке в сети, в задаче поиска максимального паросочетания в двудольном графе и др.
    Exact
    [2, 7]
    Suffix
    . 4.5 Метод Форда-Фалкерсона Этот метод является обобщением широко известного алгоритма тех же авторов. Метод является основой алгоритмов решения задач о максимальном потоке в сети, о максимальном паросочетании в двудольном графе и др. [2, 7].

  6. In-text reference with the coordinate start=20620
    Prefix
    пропускной способности в задаче о максимальном потоке в сети, в задаче поиска максимального паросочетания в двудольном графе и др. [2, 7]. 4.5 Метод Форда-Фалкерсона Этот метод является обобщением широко известного алгоритма тех же авторов. Метод является основой алгоритмов решения задач о максимальном потоке в сети, о максимальном паросочетании в двудольном графе и др.
    Exact
    [2, 7]
    Suffix
    . Сетью является, например, система, состоящая из некоторого множества объектов, связанных каналами передачи сообщений. Один из этих объектов является только источником сообщений (s), другой – только приемником (t).

3
Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы: пер. с англ. М.: Издат. дом Вильямс, 2001. 384 с.
Total in-text references: 3
  1. In-text reference with the coordinate start=12701
    Prefix
    Он заключается в том, что на каждом уровне дерева решений в соответствии с некоторой оценкой, определяемой спецификой задачи, выбирается одно подмножество, отсекая` все остальные, до тех пор, пока не получим решение. Таким образом, здесь формируется только одна ветвь дерева решений. Отметим, что для этого метода часто используют термин «жадный алгоритм»
    Exact
    [3, 7, 9]
    Suffix
    . Свойства задач, определяющие возможность получения точного решения данным методом: – задача может быть разбита на подзадачи, имеющие альтернативные варианты решения; – для подзадачи уровня справедлив принцип оптимальности, т. е. для вершин одного уровня дерева декомпозиции существует отсекающая оценка; – подзадачи можно сформировать только после выбора подзадачи предыдущего

  2. In-text reference with the coordinate start=18527
    Prefix
    Рассматриваемый метод по сравнению с другими методами точного решения NP полных задач (поиск в ширину и глубину с возвращением) в большей степени направлен на сокращение полного перебора, однако более трудоемок. 4.4 Метод Дейкстры В настоящее время в специальной литературе
    Exact
    [2, 3, 5, 7, 10]
    Suffix
    с разной степенью детализации описан алгоритм Дейкстры поиска маршрута минимальной длины и большинством авторов как метод не трактуется. Поскольку идеи этого алгоритма могут быть использованы для решения довольно широкого круга задач дискретной оптимизации, его общую схему целесообразно рассматривать как метод.

  3. In-text reference with the coordinate start=23388
    Prefix
    Вычислительная сложность алгоритмов, построенных на основе этого метода, не хуже О(n m2) [7]. 5 Метод динамического программирования Динамическое программирование применим для решения задач, для которых характерны следующие свойства
    Exact
    [3, 7]
    Suffix
    : – задачу можно разбить на независимые подзадачи, эти подзадачи на более мелкие и так далее; – вид подзадач можно определить заранее, анализируя структуру задачи; – оценка качества решения подзадачи является локальным критерием оптимальности; – для задачи в целом справедлив принцип оптимальности; – число подзадач полиномиально зависит от размера входа задачи, а число вари

5
Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов: пер. с англ. М.: Мир, 1981. 368 с.
Total in-text references: 5
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

  2. In-text reference with the coordinate start=13360
    Prefix
    Метод обеспечивает получение точного решения за полиномиальное время. Этот метод лежит в основе, например, алгоритма Прима определения минимального остовного дерева. Асимптотическая оценка вычислительной сложности этого алгоритма не хуже O(n 2 )
    Exact
    [5]
    Suffix
    . 4.2 Поиск в ширину и в глубину с возвращением Последовательное получение решений при декомпозиции как в ширину, так и в глубину с возвращением, позволяет реализовать поиск оптимального решения в процессе декомпозиции и, возможно, избежать полного перебора для NP-полных задач [9, 10].

  3. In-text reference with the coordinate start=16073
    Prefix
    задачи и значений исходных данных. 4.3 Метод ветвей и границ Метод ветвей и границ является универсальным, хотя и достаточно сложным, методом точного решения широкого круга NP-полных комбинаторно-оптимизационных задач. Метод реализует направленный перебор вариантов, используя разумную эвристику – выполнять ветвление вершин не в заданной последовательности, а более перспективных
    Exact
    [2, 5, 8, 10, 12]
    Suffix
    . Вершины выбираются на основе оценки, которая с той или иной степенью достоверности позволяет сделать заключение, что подмножество вариантов, сопоставленных данной вершине дерева декомпозиции, может содержать оптимальное решение.

  4. In-text reference with the coordinate start=18527
    Prefix
    Рассматриваемый метод по сравнению с другими методами точного решения NP полных задач (поиск в ширину и глубину с возвращением) в большей степени направлен на сокращение полного перебора, однако более трудоемок. 4.4 Метод Дейкстры В настоящее время в специальной литературе
    Exact
    [2, 3, 5, 7, 10]
    Suffix
    с разной степенью детализации описан алгоритм Дейкстры поиска маршрута минимальной длины и большинством авторов как метод не трактуется. Поскольку идеи этого алгоритма могут быть использованы для решения довольно широкого круга задач дискретной оптимизации, его общую схему целесообразно рассматривать как метод.

  5. In-text reference with the coordinate start=26028
    Prefix
    – граф решетки NP Ветвей и границ Экспоненциальная 2 Определение минимального остовного дерева Установление порядка соединения попарно связанных объектов Взвешенный неориентированный граф P Жадного выбора O(n2) –
    Exact
    [5]
    Suffix
    , O(m log log n) – [1] 3 Поиск простой цепи с минимальной суммой весов ребер Определение маршрута минимальной длины Взвешенный неориентированный (ориентированный) граф P Дейкстры Для разреженных графов: O(m logn) – [ 7], O(m log logD) – [1], D – максимальная длина 4 Поиск гамильтонова цикла с минимальной суммой весов ребер Определение замкнутого маршрута минимально

6
Дивеев А.И., Северцев Н.А. Метод выбора оптимального варианта технической системы. М.: ВЦ РАН, 2003. 106 с.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

7
Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2000. 960 с.
Total in-text references: 23
  1. In-text reference with the coordinate start=1965
    Prefix
    Цель работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы
    Exact
    [2– 4, 7–12]
    Suffix
    , в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей [1, 5, 6, 13– 26], связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводитс

  2. In-text reference with the coordinate start=3837
    Prefix
    Все это в целом затрудняет специалистам выбор метода решения новых прикладных задач структурного синтеза и обучение курсам дискретной оптимизации. 1. Стратегии поиска решения комбинаторно-оптимизационных задач Можно выделить две основные стратегии поиска решения задач дискретной оптимизации. Первая из них основана на двух идеях
    Exact
    [7, 8, 10]
    Suffix
    : – декомпозиция пространства решений; – исследование множества возможных решений, т. е. поиск в процессе декомпозиции оптимального решения на основе некоторой оценки его качества. Вторая стратегия реализует следующие три идеи [7]: – разбиение задачи на подзадачи; – оценка значения локального критерия качества решения подзадач и определение оптимального варианта подзадач; – получение ре

  3. In-text reference with the coordinate start=4069
    Prefix
    Первая из них основана на двух идеях [7, 8, 10]: – декомпозиция пространства решений; – исследование множества возможных решений, т. е. поиск в процессе декомпозиции оптимального решения на основе некоторой оценки его качества. Вторая стратегия реализует следующие три идеи
    Exact
    [7]
    Suffix
    : – разбиение задачи на подзадачи; – оценка значения локального критерия качества решения подзадач и определение оптимального варианта подзадач; – получение решения композицией (объединением) этих подзадач.

  4. In-text reference with the coordinate start=5432
    Prefix
    Сопоставив каждому подмножеству вершину графа и соединив ребром вершины, соответствующие подмножествам Mi и Mj, если подмножество Mj получено непосредственным разбиением подмножества Mi, получим дерево решений или дерево декомпозиции. Существует две стратегии декомпозиции, отличающиеся порядком получения вершин дерева решений
    Exact
    [2 – 5, 7, 9, 10]
    Suffix
    :  в ширину;  в глубину с возвращением. Декомпозиция в ширину. Все множество возможных вариантов решения M в соответствии с принципом формирования результата разбивается на подмножества первого уровня 1 Mi такие, что  1 Mi= M.

  5. In-text reference with the coordinate start=8202
    Prefix
    Отношение частичного порядка на множестве вершин ориентированного графа позволяет на основе построения глубинного остовного дерева решать, например, такие задачи как:  распознавание сильной связности ориентированного графа, т. е. существования в нем пути из каждой вершины в любую другую [2];  отыскание блоков, мостов и расщепляющих вершин
    Exact
    [2, 7]
    Suffix
    ;  установления ацикличности ориентированного графа [7];  отыскание всех гамильтоновых циклов графа (2). Построение дерева в ширину или b-дерева. Это дерево строится в соответствии со стратегией декомпозиции в ширину.

  6. In-text reference with the coordinate start=8259
    Prefix
    порядка на множестве вершин ориентированного графа позволяет на основе построения глубинного остовного дерева решать, например, такие задачи как:  распознавание сильной связности ориентированного графа, т. е. существования в нем пути из каждой вершины в любую другую [2];  отыскание блоков, мостов и расщепляющих вершин [2, 7];  установления ацикличности ориентированного графа
    Exact
    [7]
    Suffix
    ;  отыскание всех гамильтоновых циклов графа (2). Построение дерева в ширину или b-дерева. Это дерево строится в соответствии со стратегией декомпозиции в ширину. Вершины и ребра графа включаются в дерево (просматриваются) один раз.

  7. In-text reference with the coordinate start=9147
    Prefix
    Просмотр графа в ширину составляет основу алгоритмов решения, например таких задач как: определения длины кратчайшего пути (в указанном выше смысле) от некоторой вершины до каждой из достижимых
    Exact
    [7]
    Suffix
    ; построение остовного дерева минимального веса [7] и др. Просмотр графа как в глубину с возвращением, так и ширину требует (n + m) операций, где n = X , m =U. Если локальная степень вершин неориентированного графа (или сумма полустепеней исхода и захода в ориентированном) ограничена константой, то асимптотическая оценка построения d - и b-деревьев будет равна О(n). 3

  8. In-text reference with the coordinate start=9197
    Prefix
    Просмотр графа в ширину составляет основу алгоритмов решения, например таких задач как: определения длины кратчайшего пути (в указанном выше смысле) от некоторой вершины до каждой из достижимых [7]; построение остовного дерева минимального веса
    Exact
    [7]
    Suffix
    и др. Просмотр графа как в глубину с возвращением, так и ширину требует (n + m) операций, где n = X , m =U. Если локальная степень вершин неориентированного графа (или сумма полустепеней исхода и захода в ориентированном) ограничена константой, то асимптотическая оценка построения d - и b-деревьев будет равна О(n). 3 Отсечение или выбор вариантов В практике проектиро

  9. In-text reference with the coordinate start=10418
    Prefix
    Существование некоторой оценки, которая с той или иной степенью достоверности позволяет судить о том, содержит ли подмножество вариантов оптимальное решение, обеспечило бы возможность избежать полного перебора
    Exact
    [7, 8, 10]
    Suffix
    . В общем случае оценка – это значение функции F(Mi) на вершинах дерева решений, как правило, исключая корень, равная в его конечных вершинах значению целевой функции для соответствующего варианта решения, а в остальных – нижней Fн или верхней Fв границе целевой функции для вариантов, входящих в это множество.

  10. In-text reference with the coordinate start=12701
    Prefix
    Он заключается в том, что на каждом уровне дерева решений в соответствии с некоторой оценкой, определяемой спецификой задачи, выбирается одно подмножество, отсекая` все остальные, до тех пор, пока не получим решение. Таким образом, здесь формируется только одна ветвь дерева решений. Отметим, что для этого метода часто используют термин «жадный алгоритм»
    Exact
    [3, 7, 9]
    Suffix
    . Свойства задач, определяющие возможность получения точного решения данным методом: – задача может быть разбита на подзадачи, имеющие альтернативные варианты решения; – для подзадачи уровня справедлив принцип оптимальности, т. е. для вершин одного уровня дерева декомпозиции существует отсекающая оценка; – подзадачи можно сформировать только после выбора подзадачи предыдущего

  11. In-text reference with the coordinate start=14694
    Prefix
    Нижняя Fн или верхняя Fв границы наиболее просто вычисляются в тех задачах, в которых необходимо найти оптимальное решение по минимуму или максимуму суммы весов ребер. Примером такой задачи является симметричная или несимметричная задача коммивояжера (поиск гамильтонова цикла)
    Exact
    [2– 4, 7]
    Suffix
    . Как известно, для ее решения не существует алгоритма с полиномиальной оценкой вычислительной сложности. В связи с этим отсечение вариантов на основе использования опорного решения при поиске в ширину или глубину с возвращением может оказаться весьма полезным.

  12. In-text reference with the coordinate start=18527
    Prefix
    Рассматриваемый метод по сравнению с другими методами точного решения NP полных задач (поиск в ширину и глубину с возвращением) в большей степени направлен на сокращение полного перебора, однако более трудоемок. 4.4 Метод Дейкстры В настоящее время в специальной литературе
    Exact
    [2, 3, 5, 7, 10]
    Suffix
    с разной степенью детализации описан алгоритм Дейкстры поиска маршрута минимальной длины и большинством авторов как метод не трактуется. Поскольку идеи этого алгоритма могут быть использованы для решения довольно широкого круга задач дискретной оптимизации, его общую схему целесообразно рассматривать как метод.

  13. In-text reference with the coordinate start=20362
    Prefix
    Метод может быть использован для определения дополняющего пути максимальной пропускной способности в задаче о максимальном потоке в сети, в задаче поиска максимального паросочетания в двудольном графе и др.
    Exact
    [2, 7]
    Suffix
    . 4.5 Метод Форда-Фалкерсона Этот метод является обобщением широко известного алгоритма тех же авторов. Метод является основой алгоритмов решения задач о максимальном потоке в сети, о максимальном паросочетании в двудольном графе и др. [2, 7].

  14. In-text reference with the coordinate start=20620
    Prefix
    пропускной способности в задаче о максимальном потоке в сети, в задаче поиска максимального паросочетания в двудольном графе и др. [2, 7]. 4.5 Метод Форда-Фалкерсона Этот метод является обобщением широко известного алгоритма тех же авторов. Метод является основой алгоритмов решения задач о максимальном потоке в сети, о максимальном паросочетании в двудольном графе и др.
    Exact
    [2, 7]
    Suffix
    . Сетью является, например, система, состоящая из некоторого множества объектов, связанных каналами передачи сообщений. Один из этих объектов является только источником сообщений (s), другой – только приемником (t).

  15. In-text reference with the coordinate start=22140
    Prefix
    и добавляется обратный канал с пропускной способностью, равной передаваемому потоку; – если пропускная способность канала равна передаваемому потоку, то данный канал удаляется и добавляется обратный канал с пропускной способностью, равной передаваемому потоку. Дополняющий путь – это простая цепь из истока s в сток t в остаточной сети. В классическом изложении метода
    Exact
    [7]
    Suffix
    способ определения дополняющего пути не декларируется. Метод в целом заключается в следующем: 1) Задается начальное состояние сети: значение передаваемого потока f для всех каналов устанавливается равным нулю.

  16. In-text reference with the coordinate start=23239
    Prefix
    основной сети, то поток через него увеличивается на ∆f; – если канал дополняющего пути является обратным, то поток в сети по соответствующему прямому каналу уменьшается на ∆f. 4) Определяется остаточная сеть. Процесс повторяется с п. 2 до тех пор, пока существует дополняющий путь. Вычислительная сложность алгоритмов, построенных на основе этого метода, не хуже О(n m2)
    Exact
    [7]
    Suffix
    . 5 Метод динамического программирования Динамическое программирование применим для решения задач, для которых характерны следующие свойства [3, 7]: – задачу можно разбить на независимые подзадачи, эти подзадачи на более мелкие и так далее; – вид подзадач можно определить заранее, анализируя структуру задачи; – оценка качества решения подзадачи является локальным критерием о

  17. In-text reference with the coordinate start=23388
    Prefix
    Вычислительная сложность алгоритмов, построенных на основе этого метода, не хуже О(n m2) [7]. 5 Метод динамического программирования Динамическое программирование применим для решения задач, для которых характерны следующие свойства
    Exact
    [3, 7]
    Suffix
    : – задачу можно разбить на независимые подзадачи, эти подзадачи на более мелкие и так далее; – вид подзадач можно определить заранее, анализируя структуру задачи; – оценка качества решения подзадачи является локальным критерием оптимальности; – для задачи в целом справедлив принцип оптимальности; – число подзадач полиномиально зависит от размера входа задачи, а число вари

  18. In-text reference with the coordinate start=24817
    Prefix
    Вычислительная сложность алгоритмов, реализующих метод динамического программирования, не хуже O(n2). Метод динамического программирования используется при решении задачи оптимальной триангуляции выпуклого многоугольника, наибольшей общей подпоследовательности и др.
    Exact
    [7]
    Suffix
    . 6 Примеры задач дискретной оптимизации и вычислительная сложность алгоритмов, реализующих точные методы их решения В таблице 1 приведены некоторые задачи дискретной оптимизации, соответствующие примеры практических задач и вычислительная сложность некоторых описанных в литературе алгоритмов их решения.

  19. In-text reference with the coordinate start=26630
    Prefix
    4 Поиск гамильтонова цикла с минимальной суммой весов ребер Определение замкнутого маршрута минимальной длины Взвешенный неориентированный (ориентированный) граф NP Ветвей и границ Экспоненциальная 5 Определение наибольшего паросочетания Распределение преподавателе й по учебным курсам Двудольный неориентированный (ориентированный) граф P Форда - Фалкерсо на O(n m) –
    Exact
    [7]
    Suffix
    , O(n1/2 m) – [1], 6 Построение глубинного дерева с одинаковыми весами ребер Выделение из системы подсистемы с заданным приоритетом связей Взвешенный ориентированный граф P Декомпоз иция в глубину с возвращен ием O(n) или O(m) – [7, 11] 7 Разрезание гиперграфа Декомпозиция структуры сложной системы Гиперграф NP Ветвей и границ Экспоненциальная 8 Поиск дополняющего

  20. In-text reference with the coordinate start=26850
    Prefix
    Распределение преподавателе й по учебным курсам Двудольный неориентированный (ориентированный) граф P Форда - Фалкерсо на O(n m) – [7], O(n1/2 m) – [1], 6 Построение глубинного дерева с одинаковыми весами ребер Выделение из системы подсистемы с заданным приоритетом связей Взвешенный ориентированный граф P Декомпоз иция в глубину с возвращен ием O(n) или O(m) –
    Exact
    [7, 11]
    Suffix
    7 Разрезание гиперграфа Декомпозиция структуры сложной системы Гиперграф NP Ветвей и границ Экспоненциальная 8 Поиск дополняющего пути в сети Выявление каналов увеличения потока информации в системе Взвешенный ориентированный граф P Поиск в ширину О(n2) – [7] 9 Установление изоморфизма графов Определение идентичности структур систем Взвешенные ультра- или ориент

  21. In-text reference with the coordinate start=27145
    Prefix
    связей Взвешенный ориентированный граф P Декомпоз иция в глубину с возвращен ием O(n) или O(m) – [7, 11] 7 Разрезание гиперграфа Декомпозиция структуры сложной системы Гиперграф NP Ветвей и границ Экспоненциальная 8 Поиск дополняющего пути в сети Выявление каналов увеличения потока информации в системе Взвешенный ориентированный граф P Поиск в ширину О(n2) –
    Exact
    [7]
    Suffix
    9 Установление изоморфизма графов Определение идентичности структур систем Взвешенные ультра- или ориентированный граф NP Модифика ция метода ветвей и границ Экспоненциальная 10 Нахождение наибольшего независимого множества вершин Определение максимальног о количества параллельных процессов Неориентированны й граф NP Поиск в глубину с возвращен ием Экспоненциальная

  22. In-text reference with the coordinate start=27872
    Prefix
    доминирующего множества вершин Выявление минимально необходимого количества обслуживающ их аппаратов и объектов их установки Неориентированны й (ориентированный) граф NP Ветвей и границ Экспоненциальная 12 Определение максималь-ного потока Определение максимально возможного потока информации в системе Взвешенный ориентированный граф P Форда - Фалкерсо на O(n m2) –
    Exact
    [7]
    Suffix
    , O(n 2 m1/2) – [1], O(n m log2n) – [1] 13 Установление планарности графа Установление возможности укладки коммуникаций в одной плоскости без их пересечения Неориентированны й граф P Поиск в глубину с возвращен ием (в ширину), динамичес кого программ ирования O(n 3) – [7] Заключение Основными результатами работы являются систематизированное изложение точных методов дискр

  23. In-text reference with the coordinate start=28129
    Prefix
    потока информации в системе Взвешенный ориентированный граф P Форда - Фалкерсо на O(n m2) – [7], O(n 2 m1/2) – [1], O(n m log2n) – [1] 13 Установление планарности графа Установление возможности укладки коммуникаций в одной плоскости без их пересечения Неориентированны й граф P Поиск в глубину с возвращен ием (в ширину), динамичес кого программ ирования O(n 3) –
    Exact
    [7]
    Suffix
    Заключение Основными результатами работы являются систематизированное изложение точных методов дискретной оптимизации, их сущности, возможностей и особенностей задач, для решения которых они могут быть использованы.

8
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 480 с.
Total in-text references: 5
  1. In-text reference with the coordinate start=1965
    Prefix
    Цель работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы
    Exact
    [2– 4, 7–12]
    Suffix
    , в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей [1, 5, 6, 13– 26], связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводитс

  2. In-text reference with the coordinate start=3837
    Prefix
    Все это в целом затрудняет специалистам выбор метода решения новых прикладных задач структурного синтеза и обучение курсам дискретной оптимизации. 1. Стратегии поиска решения комбинаторно-оптимизационных задач Можно выделить две основные стратегии поиска решения задач дискретной оптимизации. Первая из них основана на двух идеях
    Exact
    [7, 8, 10]
    Suffix
    : – декомпозиция пространства решений; – исследование множества возможных решений, т. е. поиск в процессе декомпозиции оптимального решения на основе некоторой оценки его качества. Вторая стратегия реализует следующие три идеи [7]: – разбиение задачи на подзадачи; – оценка значения локального критерия качества решения подзадач и определение оптимального варианта подзадач; – получение ре

  3. In-text reference with the coordinate start=4841
    Prefix
    Методы декомпозиции пространства решений В процессе декомпозиции множество М возможных вариантов решения задачи в соответствии с принципом формирования результата разбивается на подмножества Mi такие, что Mi = M
    Exact
    [8, 10]
    Suffix
    . Далее, используя тот же принцип, полученные подмножества вновь разбиваются на подмножества, включающие в себя меньшее число вариантов. После некоторого шага разбиения каждое множество содержит по одному варианту решения.

  4. In-text reference with the coordinate start=10418
    Prefix
    Существование некоторой оценки, которая с той или иной степенью достоверности позволяет судить о том, содержит ли подмножество вариантов оптимальное решение, обеспечило бы возможность избежать полного перебора
    Exact
    [7, 8, 10]
    Suffix
    . В общем случае оценка – это значение функции F(Mi) на вершинах дерева решений, как правило, исключая корень, равная в его конечных вершинах значению целевой функции для соответствующего варианта решения, а в остальных – нижней Fн или верхней Fв границе целевой функции для вариантов, входящих в это множество.

  5. In-text reference with the coordinate start=16073
    Prefix
    задачи и значений исходных данных. 4.3 Метод ветвей и границ Метод ветвей и границ является универсальным, хотя и достаточно сложным, методом точного решения широкого круга NP-полных комбинаторно-оптимизационных задач. Метод реализует направленный перебор вариантов, используя разумную эвристику – выполнять ветвление вершин не в заданной последовательности, а более перспективных
    Exact
    [2, 5, 8, 10, 12]
    Suffix
    . Вершины выбираются на основе оценки, которая с той или иной степенью достоверности позволяет сделать заключение, что подмножество вариантов, сопоставленных данной вершине дерева декомпозиции, может содержать оптимальное решение.

9
Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001. 304 с.
Total in-text references: 4
  1. In-text reference with the coordinate start=1965
    Prefix
    Цель работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы
    Exact
    [2– 4, 7–12]
    Suffix
    , в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей [1, 5, 6, 13– 26], связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводитс

  2. In-text reference with the coordinate start=5432
    Prefix
    Сопоставив каждому подмножеству вершину графа и соединив ребром вершины, соответствующие подмножествам Mi и Mj, если подмножество Mj получено непосредственным разбиением подмножества Mi, получим дерево решений или дерево декомпозиции. Существует две стратегии декомпозиции, отличающиеся порядком получения вершин дерева решений
    Exact
    [2 – 5, 7, 9, 10]
    Suffix
    :  в ширину;  в глубину с возвращением. Декомпозиция в ширину. Все множество возможных вариантов решения M в соответствии с принципом формирования результата разбивается на подмножества первого уровня 1 Mi такие, что  1 Mi= M.

  3. In-text reference with the coordinate start=12701
    Prefix
    Он заключается в том, что на каждом уровне дерева решений в соответствии с некоторой оценкой, определяемой спецификой задачи, выбирается одно подмножество, отсекая` все остальные, до тех пор, пока не получим решение. Таким образом, здесь формируется только одна ветвь дерева решений. Отметим, что для этого метода часто используют термин «жадный алгоритм»
    Exact
    [3, 7, 9]
    Suffix
    . Свойства задач, определяющие возможность получения точного решения данным методом: – задача может быть разбита на подзадачи, имеющие альтернативные варианты решения; – для подзадачи уровня справедлив принцип оптимальности, т. е. для вершин одного уровня дерева декомпозиции существует отсекающая оценка; – подзадачи можно сформировать только после выбора подзадачи предыдущего

  4. In-text reference with the coordinate start=13640
    Prefix
    Асимптотическая оценка вычислительной сложности этого алгоритма не хуже O(n 2 ) [5]. 4.2 Поиск в ширину и в глубину с возвращением Последовательное получение решений при декомпозиции как в ширину, так и в глубину с возвращением, позволяет реализовать поиск оптимального решения в процессе декомпозиции и, возможно, избежать полного перебора для NP-полных задач
    Exact
    [9, 10]
    Suffix
    . Метод целесообразно применять, если: – задача может быть разбита на подзадачи, которые можно сформировать только после выбора подзадачи предыдущего уровня; – отсекающей оценкой является опорное решение, т.е. значение целевой функции уже полученного варианта решения, или условие, связанное со структурой либо свойствами решения.

10
Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 288 с.
Total in-text references: 8
  1. In-text reference with the coordinate start=1965
    Prefix
    Цель работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы
    Exact
    [2– 4, 7–12]
    Suffix
    , в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей [1, 5, 6, 13– 26], связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводитс

  2. In-text reference with the coordinate start=3837
    Prefix
    Все это в целом затрудняет специалистам выбор метода решения новых прикладных задач структурного синтеза и обучение курсам дискретной оптимизации. 1. Стратегии поиска решения комбинаторно-оптимизационных задач Можно выделить две основные стратегии поиска решения задач дискретной оптимизации. Первая из них основана на двух идеях
    Exact
    [7, 8, 10]
    Suffix
    : – декомпозиция пространства решений; – исследование множества возможных решений, т. е. поиск в процессе декомпозиции оптимального решения на основе некоторой оценки его качества. Вторая стратегия реализует следующие три идеи [7]: – разбиение задачи на подзадачи; – оценка значения локального критерия качества решения подзадач и определение оптимального варианта подзадач; – получение ре

  3. In-text reference with the coordinate start=4841
    Prefix
    Методы декомпозиции пространства решений В процессе декомпозиции множество М возможных вариантов решения задачи в соответствии с принципом формирования результата разбивается на подмножества Mi такие, что Mi = M
    Exact
    [8, 10]
    Suffix
    . Далее, используя тот же принцип, полученные подмножества вновь разбиваются на подмножества, включающие в себя меньшее число вариантов. После некоторого шага разбиения каждое множество содержит по одному варианту решения.

  4. In-text reference with the coordinate start=5432
    Prefix
    Сопоставив каждому подмножеству вершину графа и соединив ребром вершины, соответствующие подмножествам Mi и Mj, если подмножество Mj получено непосредственным разбиением подмножества Mi, получим дерево решений или дерево декомпозиции. Существует две стратегии декомпозиции, отличающиеся порядком получения вершин дерева решений
    Exact
    [2 – 5, 7, 9, 10]
    Suffix
    :  в ширину;  в глубину с возвращением. Декомпозиция в ширину. Все множество возможных вариантов решения M в соответствии с принципом формирования результата разбивается на подмножества первого уровня 1 Mi такие, что  1 Mi= M.

  5. In-text reference with the coordinate start=10418
    Prefix
    Существование некоторой оценки, которая с той или иной степенью достоверности позволяет судить о том, содержит ли подмножество вариантов оптимальное решение, обеспечило бы возможность избежать полного перебора
    Exact
    [7, 8, 10]
    Suffix
    . В общем случае оценка – это значение функции F(Mi) на вершинах дерева решений, как правило, исключая корень, равная в его конечных вершинах значению целевой функции для соответствующего варианта решения, а в остальных – нижней Fн или верхней Fв границе целевой функции для вариантов, входящих в это множество.

  6. In-text reference with the coordinate start=13640
    Prefix
    Асимптотическая оценка вычислительной сложности этого алгоритма не хуже O(n 2 ) [5]. 4.2 Поиск в ширину и в глубину с возвращением Последовательное получение решений при декомпозиции как в ширину, так и в глубину с возвращением, позволяет реализовать поиск оптимального решения в процессе декомпозиции и, возможно, избежать полного перебора для NP-полных задач
    Exact
    [9, 10]
    Suffix
    . Метод целесообразно применять, если: – задача может быть разбита на подзадачи, которые можно сформировать только после выбора подзадачи предыдущего уровня; – отсекающей оценкой является опорное решение, т.е. значение целевой функции уже полученного варианта решения, или условие, связанное со структурой либо свойствами решения.

  7. In-text reference with the coordinate start=16073
    Prefix
    задачи и значений исходных данных. 4.3 Метод ветвей и границ Метод ветвей и границ является универсальным, хотя и достаточно сложным, методом точного решения широкого круга NP-полных комбинаторно-оптимизационных задач. Метод реализует направленный перебор вариантов, используя разумную эвристику – выполнять ветвление вершин не в заданной последовательности, а более перспективных
    Exact
    [2, 5, 8, 10, 12]
    Suffix
    . Вершины выбираются на основе оценки, которая с той или иной степенью достоверности позволяет сделать заключение, что подмножество вариантов, сопоставленных данной вершине дерева декомпозиции, может содержать оптимальное решение.

  8. In-text reference with the coordinate start=18527
    Prefix
    Рассматриваемый метод по сравнению с другими методами точного решения NP полных задач (поиск в ширину и глубину с возвращением) в большей степени направлен на сокращение полного перебора, однако более трудоемок. 4.4 Метод Дейкстры В настоящее время в специальной литературе
    Exact
    [2, 3, 5, 7, 10]
    Suffix
    с разной степенью детализации описан алгоритм Дейкстры поиска маршрута минимальной длины и большинством авторов как метод не трактуется. Поскольку идеи этого алгоритма могут быть использованы для решения довольно широкого круга задач дискретной оптимизации, его общую схему целесообразно рассматривать как метод.

11
Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 423 с.
Total in-text references: 2
  1. In-text reference with the coordinate start=1965
    Prefix
    Цель работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы
    Exact
    [2– 4, 7–12]
    Suffix
    , в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей [1, 5, 6, 13– 26], связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводитс

  2. In-text reference with the coordinate start=26850
    Prefix
    Распределение преподавателе й по учебным курсам Двудольный неориентированный (ориентированный) граф P Форда - Фалкерсо на O(n m) – [7], O(n1/2 m) – [1], 6 Построение глубинного дерева с одинаковыми весами ребер Выделение из системы подсистемы с заданным приоритетом связей Взвешенный ориентированный граф P Декомпоз иция в глубину с возвращен ием O(n) или O(m) –
    Exact
    [7, 11]
    Suffix
    7 Разрезание гиперграфа Декомпозиция структуры сложной системы Гиперграф NP Ветвей и границ Экспоненциальная 8 Поиск дополняющего пути в сети Выявление каналов увеличения потока информации в системе Взвешенный ориентированный граф P Поиск в ширину О(n2) – [7] 9 Установление изоморфизма графов Определение идентичности структур систем Взвешенные ультра- или ориент

12
Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: учеб. пособие. М.: ФИЗМАТЛИТ, 2002. 240 с.
Total in-text references: 2
  1. In-text reference with the coordinate start=1965
    Prefix
    Цель работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы
    Exact
    [2– 4, 7–12]
    Suffix
    , в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей [1, 5, 6, 13– 26], связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводитс

  2. In-text reference with the coordinate start=16073
    Prefix
    задачи и значений исходных данных. 4.3 Метод ветвей и границ Метод ветвей и границ является универсальным, хотя и достаточно сложным, методом точного решения широкого круга NP-полных комбинаторно-оптимизационных задач. Метод реализует направленный перебор вариантов, используя разумную эвристику – выполнять ветвление вершин не в заданной последовательности, а более перспективных
    Exact
    [2, 5, 8, 10, 12]
    Suffix
    . Вершины выбираются на основе оценки, которая с той или иной степенью достоверности позволяет сделать заключение, что подмножество вариантов, сопоставленных данной вершине дерева декомпозиции, может содержать оптимальное решение.

13
Артюхин В.В. Прогнозирование чрезвычайных ситуаций с помощью дискретной оптимизации и современных программных средств // Технологии гражданской безопасности. 2014. Т. 11, No 1 (39). С. 86-91.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

14
Ведерников Ю.В., Гарькушев А.Ю., Сазыкин А.М. Математическая формализация задачи оптимального построения информационно-управляющего комплекса мониторинга критически важных объектов // Вопросы оборонной техники. Сер. 16: Технические средства противодействия терроризму. 2014. No 1-2. С. 26-31.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

15
Джамрад М., Романченко О.А., Толстикова О.Н. Размещение объекта обслуживания населения на основе метода дискретной оптимизации // Управление большими системами: сб. тр. 2006. No 14. С. 123-134.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

16
Домке Э.Р., Жесткова С.А., Акимова В.Ю. Особенности решения задачи маршрутизации транспорта методом «ветвей и границ» // Вестник Московского автомобильно-дорожного государственного технического университета (МАДИ). 2012. No 2. С. 76-79.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

17
Дюбин Г.Н., Корбут А.А. Асимптотика жадных методов для задач о ранце: обзор и новые результаты // Обозрение прикладной и промышленной математики. 2008. Т. 15, No 4. С. 744a-746.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

18
Забиняко Г.И., Котельников Е.А. Параллельные вычисления в некоторых задачах дискретной оптимизации // Математическое моделирование. 2009. Т. 21, No 9. С. 99107.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

19
Иванко Е.Е. Метод динамического программирования в минимаксной задаче распределения заданий с равноценными исполнителями // Вестник Южно-Уральского государственного университета. Сер. Математическое моделирование и программирование. 2013. Т. 6, No 1. С. 124-133.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

20
Колпаков Р.М., Посыпкин М.А. Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце // Дискретная математика. 2010. Т. 22, No 1. С. 5873.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

21
Мещеряков Г., Дроженко В. Применение методов дискретной оптимизации для синтеза структур систем менеджмента // РИСК: Ресурсы, информация, снабжение, конкуренция. 2012. No 1. С. 39-41.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

22
Посыпкин М.А., Си Ту Тант Син. Сравнительный анализ эффективности различных вариантов метода динамического программирования для решения оптимизационных задач на этапе размещения элементов микросхем // Всероссийская научнотехническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС)»: сб. тр. Ч. 2. 2014. С. 97-100.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

23
Салий Я.В. Влияние условий предшествования на вычислительную сложность решения маршрутных задач методом динамического программирования // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2014. No 1. С. 76-86.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

24
Табуров Д.Ю. Решение задач оптимизации вычислительного процесса в локальных сетях информационно-измерительных и управляющих систем с использованием метода ветвей и границ // Приборы. 2010. No 7. С. 50-56.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

25
Dzieli ́nski A., Przemysław M. Computer algorithms for solving optimization problems for discrete-time fractional systems // Proc. of the 2013 European Control Conference (ECC), July 17-19, 2013, Zürich, Switzerland. P. 4009-4014.
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени

26
Pardalos P.M., Rodgers G.P. Computational aspects of a branch and bound algorithm for quadratic zero-one programming // Computing. 1990. Vol. 45, iss. 2. P. 131-144. DOI: 10.1007/BF02247879
Total in-text references: 1
  1. In-text reference with the coordinate start=2073
    Prefix
    работы – систематизировать описанные в различных источниках комбинаторные методы дискретной оптимизации, охарактеризовать их возможности и указать свойства задач, для решения которых могут быть использованы соответствующие методы. Анализ учебно-методической литературы [2– 4, 7–12], в которой описываются точные методы комбинаторной оптимизации, монографий и научных статей
    Exact
    [1, 5, 6, 13– 26]
    Suffix
    , связанных с их использованием, позволяет сделать следующие выводы: – непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем; – во многих источниках не излагается сущностная схема метода, а приводится его иллюстрация на алгоритме решения конкретной задачи; – отсутствует систематизация точных методов решени