Мы работаем над восстановлением приложения Unionpedia в Google Play Store
ИсходящиеВходящий
🌟Мы упростили наш дизайн для улучшения навигации!
Instagram Facebook X LinkedIn

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

Индекс Комбинаторная оптимизация

Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности.

Содержание

  1. 20 отношения: NP-полная задача, Класс P, Паросочетание, Остовное дерево, Оптимизация (математика), Равенство классов P и NP, Симплекс-метод, Удовлетворение ограничений, Целочисленное программирование, Матроид, Минимальное остовное дерево, Задача раскроя, Задача коммивояжёра, Задача о ранце, Задача о восьми ферзях, Задача о максимальном потоке, Задача о назначениях, Задача о назначении целей, Граф (математика), Линейное программирование.

  2. Теоретическая информатика
  3. Теория сложности вычислений

NP-полная задача

NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).

Посмотреть Комбинаторная оптимизация и NP-полная задача

Класс P

В теории алгоритмов классом P (от polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных).

Посмотреть Комбинаторная оптимизация и Класс P

Паросочетание

В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.

Посмотреть Комбинаторная оптимизация и Паросочетание

Остовное дерево

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

Посмотреть Комбинаторная оптимизация и Остовное дерево

Оптимизация (математика)

Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

Посмотреть Комбинаторная оптимизация и Оптимизация (математика)

Равенство классов P и NP

Вопрос о равенстве классов сложности ''P'' и ''NP'' (в русских источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий.

Посмотреть Комбинаторная оптимизация и Равенство классов P и NP

Симплекс-метод

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Посмотреть Комбинаторная оптимизация и Симплекс-метод

Удовлетворение ограничений

Одной из важных задач искусственного интеллекта (ИИ) является задача удовлетворения ограничений (УО) (constraint satisfaction problem).

Посмотреть Комбинаторная оптимизация и Удовлетворение ограничений

Целочисленное программирование

Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами.

Посмотреть Комбинаторная оптимизация и Целочисленное программирование

Матроид

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

Посмотреть Комбинаторная оптимизация и Матроид

Минимальное остовное дерево

Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Посмотреть Комбинаторная оптимизация и Минимальное остовное дерево

Задача раскроя

Задача раскроя — это NP-полная задача оптимизации, по существу, сводимая к задаче о ранце.

Посмотреть Комбинаторная оптимизация и Задача раскроя

Задача коммивояжёра

43589145600 вариантов. Задача коммивояжёра (Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.

Посмотреть Комбинаторная оптимизация и Задача коммивояжёра

Задача о ранце

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

Посмотреть Комбинаторная оптимизация и Задача о ранце

Задача о восьми ферзях

Задача о восьми ферзях.Одно из решений: a7, b4, c2, d8, e6, f1, g3, h5:(87) Зада́ча о восьми́ фе́рзя́х — широко известная задача по расстановке фигур на шахматной доске.

Посмотреть Комбинаторная оптимизация и Задача о восьми ферзях

Задача о максимальном потоке

Максимальный поток в транспортной сети. Числа обозначают потоки и пропускные способности. В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.

Посмотреть Комбинаторная оптимизация и Задача о максимальном потоке

Задача о назначениях

Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций.

Посмотреть Комбинаторная оптимизация и Задача о назначениях

Задача о назначении целей

Задача о назначении целей — это класс задач комбинаторной оптимизации.

Посмотреть Комбинаторная оптимизация и Задача о назначении целей

Граф (математика)

Неориентированный граф с шестью вершинами и семью рёбрами Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Посмотреть Комбинаторная оптимизация и Граф (математика)

Линейное программирование

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Посмотреть Комбинаторная оптимизация и Линейное программирование

См. также

Теоретическая информатика

Теория сложности вычислений