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

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

Войдите или зарегистрируйтесь
Лаборатория 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 со ссылкой на анонимный источник.

Классические задачи. Описание и комментарии

11 апреля 2012 года в 15:32

“Paul Goldsman used the spacefilling curve heuristic to solve the same instance [15,112 cities in Germany]. Our solution was about 34% longer.

27 января 2012 года в 12:06

Вот еще одна любопытная статья нашлась в New York Times на нашу любимую TSP-тему (и не только). Совершенно свежая - 27 января.

18 августа 2011 года в 17:01

При описании структуры сетей метрополитена, как правило, исследователи используют ряд простых показателей (число действующих линий, общая протяженность и плотность сети), которые, однако, не могут передать всю сложность пространственной композиции (устройства) каждой сети отдельно. Иногда при описании конфигурации таких сетей используют разные морфологические типологии. Так Л.И. Василевский в 1970-е годы выделял такие типы конфигураций сетей (Василевский,1971,с.35-36; 1976, с.24): линейный, радиальный, радиально-полукольцевой, радиально-кольцевой и древовидный, тогда как К. Иваничка (1987,с.235-238) – одотропный, моноцентрический, многоосевой, полицентрический, конвергентный, веерный. А.М. Якшин (1946, с.10-13) разделял сети на линейные, трехлучевые, четырехлучевые, многолучевые, с двойными связями (по две параллельные магистрали), сложные и очень сложные. А. Полесе (Polese,1974,p.286), изучив конфигурации всех сетей метрополитена мира, обобщил их в следующие типы: сквозной диаметр с ветками, два касающихся диаметра, два пересекающихся диаметра с ветками, кольцо с ветками, треугольник с 6 ветками, прямо-угольная решетка, радиально-кольцевая структура, прямоугольно-диагональная сеть. Эта последняя типология чаще всего и используется для описания структуры сетей метрополитена и линий скоростного трамвая (например, см. Light Rail ,2001, p.81-91).

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

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

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

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

6 мая 2011 года в 15:29

Как найти кратчайшую сеть отрезков прямых линий, соединяющих произвольное множество, скажем из 100, точек? Эта задача не поддаётся ни самым быстродействующим компьютерам, ни самым изобретательным математическим умам

4 мая 2011 года в 06:11

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

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

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

1 мая 2011 года в 17:50

Составление кольцевых маршрутов в первом приближении может осуществляться методом, известным как алгоритм Свира или алгоритм дворника-стеклоочистителя. Зададим положение потребителя материального потока в полярной системе координат. Полюс системы - точку 0, разместим в месте дислокации распределительного склада. Выберем первоначальное, нулевое, положение полярной оси f = 0. Положение потребителя определяется расстоянием от центра и углом f, который образован полярной осью, т.е. лучом, исходящим из точки 0 и направленным на потребителя.

29 апреля 2011 года в 08:57

Задачи маршрутизации транспорта (Vehicle Routing Problems, VRP) — задачи комбинаторной оптимизации, в которых для парка транспортных средств, расположенных в одном или нескольких депо, должен быть определен набор маршрутов до нескольких отдаленных точек-потребителей. Интерес к VRP вызван ее практической значимостью при значительной сложности.


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