Содержание
37 отношения: NP-полная задача, RAND (корпорация), Карп, Ричард Мэннинг, Комбинаторика, Комбинаторная оптимизация, Приближенная схема полиномиального времени, Принстонский университет, Полный граф, Полный перебор, Оптимизация, Оптимизация (математика), Алгоритм ближайшего соседа в задаче коммивояжёра, Алгоритм имитации отжига, Алгоритм Гомори, Национальный исследовательский ядерный университет «МИФИ», Трансвычислительная задача, Транспортная логистика, Уитни, Хасслер, Эвристический алгоритм, Экспоненциальная сложность, Муравьиный алгоритм, Математическая модель, Минимальное остовное дерево, Исследование операций, Измеримое множество, Задача Штейнера о минимальном дереве, Знание (издательство, Москва), Граф (математика), Гамильтон, Уильям Роуэн, Гамильтонов граф, Данциг, Джордж, Дискретная математика, 1950-е годы, 1960-е годы, 1963 год, 1990-е годы, 2006 год.
- NP-трудные задачи
- Алгоритмы на графах
- Вычислительные задачи теории графов
- Гамильтоновы пути и циклы
- Комбинаторная оптимизация
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Посмотреть Задача коммивояжёра и NP-полная задача
RAND (корпорация)
Отделение в Питтсбурге RAND (РЭНД — аббревиатура от Research and Development — «Исследования и разработка») — американский стратегический исследовательский центр.
Посмотреть Задача коммивояжёра и RAND (корпорация)
Карп, Ричард Мэннинг
Ричард Мэннинг Карп (Richard Manning Karp, 3 января 1935 года, Бостон, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.
Посмотреть Задача коммивояжёра и Карп, Ричард Мэннинг
Комбинаторика
Комбинато́рика (комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка).
Посмотреть Задача коммивояжёра и Комбинаторика
Комбинаторная оптимизация
Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности.
Посмотреть Задача коммивояжёра и Комбинаторная оптимизация
Приближенная схема полиномиального времени
В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач.
Посмотреть Задача коммивояжёра и Приближенная схема полиномиального времени
Принстонский университет
При́нстонский университет (Princeton University) — частный исследовательский университет, один из старейших и известнейших университетов в США.
Посмотреть Задача коммивояжёра и Принстонский университет
Полный граф
По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.
Посмотреть Задача коммивояжёра и Полный граф
Полный перебор
Полный перебор (или метод «грубой силы», brute force) — метод решения математических задач.
Посмотреть Задача коммивояжёра и Полный перебор
Оптимизация
Оптимизация — процесс максимизации выгодных характеристик, соотношений (например, оптимизация производственных процессов и производства), и минимизации расходов.
Посмотреть Задача коммивояжёра и Оптимизация
Оптимизация (математика)
Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.
Посмотреть Задача коммивояжёра и Оптимизация (математика)
Алгоритм ближайшего соседа в задаче коммивояжёра
Алгоритм ближайшего соседа — один из простейших эвристических методов решения задачи коммивояжёра.
Посмотреть Задача коммивояжёра и Алгоритм ближайшего соседа в задаче коммивояжёра
Алгоритм имитации отжига
Алгори́тм имита́ции о́тжига (Simulated annealing) — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации.
Посмотреть Задача коммивояжёра и Алгоритм имитации отжига
Алгоритм Гомори
Алгори́тм Го́мори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования.
Посмотреть Задача коммивояжёра и Алгоритм Гомори
Национальный исследовательский ядерный университет «МИФИ»
Национа́льный иссле́довательский я́дерный университет «МИФИ́» (Московский инженерно-физический институт) — один из первых двух национальных исследовательских университетов России (наряду с МИСиС), образован 8 апреля 2009 года на базе Московского инженерно-физического института (государственного университета).
Посмотреть Задача коммивояжёра и Национальный исследовательский ядерный университет «МИФИ»
Трансвычислительная задача
Трансвычисли́тельная зада́ча (Transcomputational problem) — в теории сложности вычислений задача, для решения которой требуется обработка более чем 1093 бит информации.
Посмотреть Задача коммивояжёра и Трансвычислительная задача
Транспортная логистика
Транспортная логистика — это система по организации доставки, а именно по перемещению каких-либо материальных предметов, веществ и пр.
Посмотреть Задача коммивояжёра и Транспортная логистика
Уитни, Хасслер
Ха́сслер Уи́тни (Hassler Whitney, 23 марта 1907 — 10 мая 1989) — американский математик.
Посмотреть Задача коммивояжёра и Уитни, Хасслер
Эвристический алгоритм
Эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи.
Посмотреть Задача коммивояжёра и Эвристический алгоритм
Экспоненциальная сложность
Экспоненциальная сложность — в теории сложности алгоритмов, сложность задачи, ограниченная экспонентой от полинома от размерности задачи, то есть ограничена функцией \exp(P(n)), где P — некоторый многочлен, а n — размер задачи.
Посмотреть Задача коммивояжёра и Экспоненциальная сложность
Муравьиный алгоритм
300px Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, ant colony optimization, ACO) — один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также решения аналогичных задач поиска маршрутов на графах.
Посмотреть Задача коммивояжёра и Муравьиный алгоритм
Математическая модель
Математи́ческая моде́ль — математическое представление реальности, один из вариантов модели как системы, исследование которой позволяет получать информацию о некоторой другой системе.
Посмотреть Задача коммивояжёра и Математическая модель
Минимальное остовное дерево
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
Посмотреть Задача коммивояжёра и Минимальное остовное дерево
Исследование операций
Исследование операций (ИО, operations research — OR, также management science — наука управления или decision science — наука о решениях) — дисциплина, занимающаяся разработкой и применением методов нахождения оптимальных решений на основе математического моделирования, статистического моделирования и различных эвристических подходов в различных областях человеческой деятельности.
Посмотреть Задача коммивояжёра и Исследование операций
Измеримое множество
Измеримое множество — в математике множество, имеющее измеримую характеристическую функцию (т. е. функцию, равную 1 на этом множестве и равную 0 на дополнении этого множества).
Посмотреть Задача коммивояжёра и Измеримое множество
Задача Штейнера о минимальном дереве
Минимальное дерево Штейнера для точек ''A'', ''B'' и ''C'', где ''S'' — точка Ферма треугольника ''ABC''. Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости.
Посмотреть Задача коммивояжёра и Задача Штейнера о минимальном дереве
Знание (издательство, Москва)
«Знание» — издательство в Москве, в советское время — издательство Всесоюзного общества «Знание».
Посмотреть Задача коммивояжёра и Знание (издательство, Москва)
Граф (математика)
Неориентированный граф с шестью вершинами и семью рёбрами Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
Посмотреть Задача коммивояжёра и Граф (математика)
Гамильтон, Уильям Роуэн
Сэр Уи́льям Ро́уэн Га́мильтон (William Rowan Hamilton; 4 августа 1805 — 2 сентября 1865) — ирландский, -теоретик, -теоретик, «один из лучших математиков XIX века».
Посмотреть Задача коммивояжёра и Гамильтон, Уильям Роуэн
Гамильтонов граф
Гамильтонова линия для додекаэдра, предложенная Гамильтоном для замены его игры «вокруг света» на додекаэдре на задачу для плоского графа. Гамильто́нов граф — математический объект теории графов.
Посмотреть Задача коммивояжёра и Гамильтонов граф
Данциг, Джордж
Джордж Бернард Данциг (George Bernard Dantzig; 8 ноября 1914 — 13 мая 2005) — американский, известен как разработчик алгоритма, применяемого в решениях задач симплекс-методом.
Посмотреть Задача коммивояжёра и Данциг, Джордж
Дискретная математика
Дискре́тная матема́тика — часть математики, изучающая дискретные математические структуры, такие, как графы и утверждения в логике.
Посмотреть Задача коммивояжёра и Дискретная математика
1950-е годы
1950-е годы — десятилетие, включающее года с 1950 по 1959.
Посмотреть Задача коммивояжёра и 1950-е годы
1960-е годы
1960-е годы — десятилетие, включающее года с 1960 по 1969.
Посмотреть Задача коммивояжёра и 1960-е годы
1963 год
Почтовая марка СССР, 1963 год.
Посмотреть Задача коммивояжёра и 1963 год
1990-е годы
мавзолея 1990-е годы (одна тысяча девятьсот девяностые; девяностые) — десятилетие, включающее года с 1990 по 1999.
Посмотреть Задача коммивояжёра и 1990-е годы
2006 год
* Международный год пустынь и опустынивания (резолюция № 58/211 ООН).
Посмотреть Задача коммивояжёра и 2006 год
См. также
NP-трудные задачи
- NP-трудность
- Задача коммивояжёра
- Квадратичная задача о назначениях
- Раскраска графов
Алгоритмы на графах
- A*
- PageRank
- Алгоритм Беллмана — Форда
- Алгоритм Борувки
- Алгоритм Брона — Кербоша
- Алгоритм Гавела — Хакими
- Алгоритм Дейкстры
- Алгоритм Джонсона
- Алгоритм Диница
- Алгоритм Каргера
- Алгоритм Косарайю
- Алгоритм Краскала
- Алгоритм Прима
- Алгоритм Тарьяна
- Алгоритм Флойда — Уоршелла
- Алгоритм Форда — Фалкерсона
- Алгоритм Хопкрофта — Карпа
- Алгоритм Эдмондса — Карпа
- Алгоритм ближайшего соседа в задаче коммивояжёра
- Алгоритм для дерева сочленений
- Алгоритм проталкивания предпотока
- Алгоритм распространения доверия
- Алгоритм сжатия цветков
- Альфа-бета-отсечение
- Вложение графа
- Вырожденность (теория графов)
- Двунаправленный поиск
- Задача изоморфности графов
- Задача коммивояжёра
- Задача о самом длинном пути
- Задача о ходе коня
- Задача поиска изоморфного подграфа
- Изоморфизм графов
- Лексикографический поиск в ширину
- Минимакс
- Модель Барабаши — Альберт
- Обход дерева
- Поиск в глубину
- Поиск в ширину
- Теорема Курселя
- Топологическая сортировка
- Транзитивное замыкание
- Транзитивное сокращение
Вычислительные задачи теории графов
- Гамильтонова цепь
- Доматическое число
- Доминирующее множество
- Доминирующее множество рёбер
- Задача Штейнера о минимальном дереве
- Задача изоморфности графов
- Задача коммивояжёра
- Задача о клике
- Задача о кликовом покрытии
- Задача о кратчайшем пути
- Задача о максимальном потоке
- Задача о размещении объектов
- Задача о самом длинном пути
- Задача поиска изоморфного подграфа
- Максимальный разрез графа
- Наименьший k-разрез
- Обобщённая задача коммивояжёра
- Остовное дерево
- Паросочетание
- Проблема размера — диаметра
- Проверка планарности
- Разбиение графа
- Разрезающее циклы множество вершин
- Разрезающий циклы набор рёбер
- Раскраска графов
- Рёберное покрытие
- Связное доминирующее множество
Гамильтоновы пути и циклы
- Гамильтонова цепь
- Гамильтоново дополнение
- Гипогамильтонов граф
- Гипотеза Барнетта
- Гипотеза Ловаса о гамильтоновом цикле
- Граф Татта
- Граф Хершеля
- Задача коммивояжёра
- Задача о самом длинном пути
- Задача о ходе коня
- Икосиан
- Панциклический граф
- Подгамильтонов граф
- Показатель короткости
- Теорема Гринберга
- Теорема Оре
Комбинаторная оптимизация
- A*
- Алгоритм Дейкстры
- Венгерский алгоритм
- Весовая функция
- Задача коммивояжёра
- Задача о 1-центре
- Задача о назначении целей
- Задача о назначениях
- Задача о наименьшей окружности
- Задача о рюкзаке
- Задача раскроя
- Квадратичная задача о назначениях
- Комбинаторная оптимизация
- Линейная задача о назначениях в узких местах
- Максимальный разрез графа
- Метод ветвей и границ
- Метод эллипсоидов
- Наименьший k-разрез
- Обобщённая задача о назначениях
- Паросочетание
- Теорема Форда — Фалкерсона
- Целочисленное программирование
Также известен как Эластичная сеть, Метод эластичной сети, Коммивояжёра задача, Задача о коммивояжере.