Темы

Комбинаторная оптимизация

Combinatorial Optimization · 24 статей

  1. Задача коммивояжёра: NP-трудная проблема комбинаторной оптимизации

    Задача коммивояжёра (TSP): поиск кратчайшего маршрута через города. NP-трудная задача комбин. оптимизации, важна в науке о данных и логистике.

    #7547 · 17 мин чтения

  2. Задача о сумме подмножества и её NP-трудность

    Задача о сумме подмножества (SSP) в информатике: NP-трудная проблема поиска подмножества с заданной суммой. Сведение из 3DM. Теория NP-полноты.

    #8625 · 5 мин чтения

  3. Задача о назначениях: комбинаторная оптимизация

    Задача назначения: оптимизация затрат при распределении задач между агентами. Минимизация общей стоимости, поиск оптимального соответствия в графе.

    #45152 · 5 мин чтения

  4. Задачи геометрической упаковки: оптимизация и применение

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

    #60582 · 6 мин чтения

  5. Задача о размещении в контейнеры и её варианты

    Задача о размещении предметов в контейнерах: оптимизация, NP-трудность, алгоритмы решения. Применение в логистике, FPGA и резервном копировании данных.

    #72565 · 9 мин чтения

  6. Целочисленное программирование: оптимизация и NP-полнота

    Целочисленное программирование: математическая оптимизация с целочисленными переменными. ILP, NP-полнота, смешанное целочисленное программирование.

    #93582 · 8 мин чтения

  7. Покрытие вершин графа: свойства и алгоритмы

    Покрытие вершин графа: определение, алгоритмы и сложность. NP-трудная задача оптимизации с простыми 2-аппроксимациями. Теория графов и компьютерные науки.

    #116977 · 6 мин чтения

  8. Приближённые алгоритмы для задач оптимизации

    Приближённые алгоритмы: эффективные решения для сложных задач оптимизации (NP-трудных). Гарантированная точность и полиномиальное время работы.

    #117031 · 5 мин чтения

  9. Схемы полиномиальной аппроксимации: типы и свойства

    Полиномиальная схема аппроксимации (PTAS): алгоритмы для NP-трудных задач оптимизации. Гарантируют решение с точностью до (1+ε) от оптимального за полиномиальное время.

    #131700 · 3 мин чтения

  10. Задача раскроя в исследовании операций

    Оптимизация раскроя материалов: математическая задача в исследовании операций. Минимизация отходов, NP-трудность, целочисленное линейное программирование.

    #148278 · 4 мин чтения

  11. Задача о покрытии множества

    Задача о покрытии множества: определение, примеры и поиск минимального подмножества для покрытия всех элементов. Комбинаторика, информатика, теория сложности.

    #153404 · 4 мин чтения

  12. Задачи о покрытии: обзор и разновидности

    Задачи покрытия в комбинаторике и информатике: определение, примеры (задача о покрытии множества, вершинное покрытие), связь с задачами упаковки и линейным программированием.

    #174662 · 3 мин чтения

  13. Квадратичное назначение: задача комбинаторной оптимизации

    Квадратичное назначение: задача комбин. оптимизации для размещения объектов. Минимизация затрат на основе расстояний и потоков между ними. Математика, логистика.

    #236731 · 1 мин чтения

  14. Задача о секретарше и оптимальная стратегия выбора

    Задача секретаря: оптимальная стратегия выбора лучшего кандидата. Теория оптимальной остановки, правило 37%, принятие решений в условиях неопределенности.

    #269235 · 10 мин чтения

  15. Задача об упаковке множеств: сложность, приближения и варианты

    Задача о покрытии множества: NP-полная проблема комбинаторики. Поиск k непересекающихся подмножеств. Определение и варианты оптимизации/решения.

    #273499 · 4 мин чтения

  16. Классы аппроксимируемых задач

    Класс APX в теории сложности: NP-задачи оптимизации с полиномиальными алгоритмами приближения. Гарантированная точность решения – постоянный фактор.

    #273604 · 3 мин чтения

  17. Полиномиальная схема аппроксимации с полностью полиномиальным временем

    Аппроксимационные схемы FPTAS: алгоритмы для нахождения приближенных решений задач оптимизации. Гарантируют точность в пределах ε. Эффективность и применение.

    #276003 · 2 мин чтения

  18. Гильотинная резка: оптимизация раскроя прямоугольных листов

    Резка гильотиной: производство прямоугольных деталей из листов. Применение в стекольной, металлургической и деревообрабатывающей промышленности. ✂️📏

    #303469 · 4 мин чтения

  19. Точное покрытие множества: определение и применение

    Точное покрытие в комбинаторике: определение, NP-полнота, применение в планировании, облачных вычислениях и проектировании схем. Разделение множеств!

    #341130 · 3 мин чтения

  20. Анализ доминирования для аппроксимационных алгоритмов

    Доминантный анализ аппроксимационных алгоритмов: оценка производительности, альтернатива классическому анализу. Доминантное число и коэффициент – ключевые понятия.

    #367052 · 2 мин чтения

  21. Задача о разбиении множества: NP-полнота и алгоритмы решения

    Задача о разбиении множества: NP-полная проблема в теории чисел и информатике. Динамическое программирование, эвристики и оптимизационные решения.

    #373914 · 6 мин чтения

  22. Планирование заданий на однородных машинах

    Оптимальное распределение задач по машинам: минимизация времени выполнения (makespan) для n задач на m машинах. Теория расписаний и оптимизация.

    #376129 · 1 мин чтения

  23. Одномашинное планирование задач: обзор и алгоритмы

    Одномашинное планирование: оптимизация задач на одном ресурсе. NP-трудные задачи решаются быстро. Обзор, обозначение 1|…|… в теории планирования.

    #398245 · 3 мин чтения

  24. 3-partition problem

    #482793 · 4 мин чтения