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

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

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

Задача коммивояжера (Золотое кольцо России)

15 января 2012 года в 13:12   Просмотров: 6019

Маршрут по Золотому Кольцу

 

 

Проложить маршрут по Золотому кольцу

 

Описание

Золото́е кольцо́ Росси́и — семейство туристических маршрутов, проходящих по древним русским городам, в которых сохранились уникальные памятники истории и культуры России, центрам народных ремёсел. Количество и состав городов в конкретном маршруте может быть разным. Ниже перечислены населённые пункты, которые входят в разные маршруты. Столица Золотого Кольца — город Ярославль.


Города Золотого кольца принадлежат к пяти областям: Московской, Владимирской, Ивановской, Костромской и Ярославской.

В Золотое кольцо входят шестнадцать основных городов — Александров, Владимир, Гусь-Хрустальный, Иваново, Калязин, Кострома, Москва, Переславль-Залесский, Плёс, Ростов Великий, Рыбинск, Сергиев Посад, Суздаль, Углич, Юрьев-Польский и Ярославль. Остальной список (Боголюбово, Нижний Новгород, Гороховец, Городец, Кидекша, Муром, Палех, Тутаев, Шуя и др.) является дискуссионным.

Автор термина — литератор Юрий Бычков, создавший в 1967 году серию одноимённых очерков для газеты «Советская Культура» (по другим источникам — «Советская Россия»)

Матрица

    Алекс-в Бог-во Владимир Гор.-ц Гусь Хруст Иваново Калязин Кидекша Кострома Москва Муром Палех Пер.- Залеск. Плес Ростов
Рыбинск Сергиев Посад Суздаль Тутаев Углич Шуя Юрьев Поль. Ярос-ль
  Александров 0 170 160 310 230 260 150 190 260 130 290 320 71 320 140 280 56 190 230 220 290 110 190
  Боголюбово   0 10 140 83 110 300 37 220 200 140 150 150 180 180 310 190 35 260 270 130 76 230
  Владимир     0 150 74 110 290 38 220 190 130 160 140 180 200 310 180 35 270 280 140 70 230
  Гороховец         200 180 440 180 280 340 94 120 290 240 320 370 330 170 330 410 150 220 290
  Гусь Хруст         0 190 360 110 290 260 110 210 210 260 270 380 250 110 340 350 190 140 300
  Иваново           0 240 83 110 300 220 66 190 69 130 200 270 80 160 220 34 120 120
  Калязин             0 260 240 190 420 300 120 300 120 130 120 260 150 53 270 200 170
  Кидекша               0 190 220 170 120 140 150 150 280 220 6 230 240 91 66 190
  Кострома                 0 340 330 170 190 73 130 170 270 180 130 190 140 260 84
  Москва                   0 320 350 140 400 210 350 76 220 300 240 330 210 260
  Муром                     0 170 270 290 330 420 310 170 370 410 190 200 340
  Палех                       0 260 110 190 260 330 120 220 280 32 180 180
  Переславль Зал                         0 250 66 210 73 140 160 150 220 74 120
  Плес                           0 190 230 330 150 190 250 100 190 140
  Ростов великий                             0 140 130 150 96 92 160 130 57
  Рыбинск                               0 280 270 48 84 230 270 85
  Сергиев посад                                 0 220 230 160 290 140 190
  Суздаль                                   0 230 240 89 62 190
  Тутаев                                     0 100 190 230 41
  Углич                                       0 250 210 110
  Шуя                                         0 150 150
  Юрьев-Польский                                           0 190
  Ярославль                                             0

Один комментарий

#31
Евгений (гость) пишет:
12:46 8 декабря 2012 года
Для заданной матрицы маршрут:
Переславль Залесский, Москва, Сергиев Посад, Александров, Юрьев Польский, Суздаль, Кидекша
Боголюбово, Владимир, Гусь Хрустальный, Муром, Гороховец, Палех, Шуя, Иваново, Плес, Кострома,
Ярославль, Тутаев, Рыбинск, Углич, Калязин, Ростов Великий, Переславль Залесский
имеет длину 1599(на 44 меньше опубликованного).

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

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