Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

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

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Записи с тегом "NP"

26 января 2012 года в 08:20

Любопытную статью The Problem of the Traveling Politician о применении задачи коммивояжера опубликовала газета New York Times. Мы наблюдаем новую волну интереса к проблеме TSP. Приводим ее полностью.

22 июля 2011 года в 18:07

В Информатике, задача о вершинном покрытии является NP-полной задачей в области теории графов. Также часто используется в теории сложности для доказательства NP-полноты более сложных задач.

31 мая 2011 года в 18:57

Полный перебор (или метод «грубой силы» от англ. brute force) — метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

3 мая 2011 года в 08:41

Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. В общем случае задача ставится так: задано некоторое множество работ (требований) с определенным набором характеристик: стоимость обработки требования, длительность обработки требования, момент поступления требования.

2 мая 2011 года в 09:57

Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1]

1 мая 2011 года в 19:28

Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик.

26 апреля 2011 года в 16:50

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

23 апреля 2011 года в 17:28

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

14 апреля 2011 года в 09:59

Задачи тысячелетия (Millennium Prize Problems) составляют семь математических проблем, охарактеризованных как «важные классические задачи, решение которых не найдено вот уже в течение многих лет». За решение каждой из этих проблем институтом Клэя предложен приз в 1 000 000 долларов США. Анонсируя приз, институт Клэя провёл параллель со списком проблем Гильберта, представленным в 1900 году и оказавшим существенное влияние на математиков XX века. Из 23 проблем Гильберта большинство уже решены, и только одна — гипотеза Римана — вошла в список Проблем тысячелетия.

По состоянию на сентябрь 2010 года только одна из семи проблем тысячелетия (гипотеза Пуанкаре) решена. Приз за её решение присужден российскому математику Г. Я. Перельману[1], который, впрочем, отказался от денежного приза.

13 апреля 2011 года в 12:25

В математической области теории графов, клики в неориентированного графа подмножество его вершин, что каждые две вершины подмножества соединена ребром. Клик являются одним из основных понятий теории графов и используются во многих других математических задач и сооружений на графах. Клик изучались также в области компьютерных наук: поиск, есть ли клики заданного объема в графе (клики задачи) NP-полной, но несмотря на это твердость результате многие алгоритмы для нахождения клики были изучены.


Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта