Среда, 20.01.2021, 23:18
Информатика и ИКТ
Приветствую Вас Гость | RSS
Главная Регистрация Вход
Меню сайта

Yandex_tech

Хабр-news

mail_news

Rambler

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

oszone.net

IT-N-образование

Главная » 2020 » Декабрь » 24 » Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера
19:02
Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

Натан Кляйн и его советники из Вашингтонского университета Анна Карлин и Шаян Гаран впервые за почти полвека смогли найти лучший способ решения задачи коммивояжера. Это одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута через указанные города с последующим возвратом в исходный город.

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

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

Просмотров: 27 | Добавил: niko | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Календарь
«  Декабрь 2020  »
ПнВтСрЧтПтСбВс
 123456
78910111213
14151617181920
21222324252627
28293031

Форма входа

nixp.ru

OpenNet

Новые программы

SLO.ru

Погода
Яндекс.Погода

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Архив записей

    Copyright MyCorp © 2021