Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Нахождение оптимального пути по веткам метро
СообщениеДобавлено: 12 май 2017, 10:43 
Не в сети
Начинающий
Зарегистрирован:
12 май 2017, 10:38
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый день.
Задача: Есть карта метрополитена (Московского к примеру), доступны данные о длинах перегонов, времени, связях станций. Необходимо придумать алгоритм, позволяющий посетить все ветки метрополитена оптимальным способом (минимальное время или расстояние и т.д.). Критерий можно выбрать самому. Для посещения ветки достаточно посетить любую из её станций.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Нахождение оптимального пути по веткам метро
СообщениеДобавлено: 12 май 2017, 12:21 
Не в сети
Beautiful Mind
Зарегистрирован:
02 дек 2016, 23:55
Сообщений: 1083
Cпасибо сказано: 70
Спасибо получено:
194 раз в 176 сообщениях
Очков репутации: 29

Добавить очки репутацииУменьшить очки репутации
Можно попробовать рассмотреть граф,в котором вершины - связи между ветками метро.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Нахождение оптимального пути по веткам метро
СообщениеДобавлено: 12 май 2017, 12:42 
Не в сети
Начинающий
Зарегистрирован:
12 май 2017, 10:38
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Booker48 писал(а):
Можно попробовать рассмотреть граф,в котором вершины - связи между ветками метро.


Так и есть, ток вот если прямо использовать алгоритм Литтла, то найдем оптимальный путь через все пересадки, а по задаче не нужно заходить на пересадку одной и той же линии дважды (хоть и в разных местах).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Нахождение оптимального пути по веткам метро
СообщениеДобавлено: 12 май 2017, 14:58 
Не в сети
Beautiful Mind
Зарегистрирован:
02 дек 2016, 23:55
Сообщений: 1083
Cпасибо сказано: 70
Спасибо получено:
194 раз в 176 сообщениях
Очков репутации: 29

Добавить очки репутацииУменьшить очки репутации
Тогда задачу поточнее сформулируйте, чего там ещё нельзя. Т.к. вот этого
PadawanC писал(а):
по задаче не нужно заходить на пересадку одной и той же линии дважды

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Нахождение кратчайшего пути во взвешенном графе

в форуме Дискретная математика, Теория множеств и Логика

gorinich_igor

0

85

29 ноя 2017, 17:03

Поиск оптимального варианта

в форуме Комбинаторика и Теория вероятностей

FF117

0

95

13 июн 2017, 23:04

Задача по нахождению оптимального заказа

в форуме Исследование операций и Задачи оптимизации

akubonin

2

219

02 фев 2016, 16:53

Выбор оптимального набора продуктов

в форуме Исследование операций и Задачи оптимизации

evch85

0

184

29 окт 2014, 16:41

Задача оптимального производства продукции

в форуме Microsoft Excel

evgeniymx

3

403

03 ноя 2015, 21:13

Простая задача по выбору оптимального алгоритма

в форуме Комбинаторика и Теория вероятностей

Earl_Us

12

641

13 сен 2013, 10:56

Задача оптимального распределения рабочей силы

в форуме Исследование операций и Задачи оптимизации

bobah8

0

124

13 окт 2016, 17:02

Метод оптимального распределения средств +взаимозависимость

в форуме Исследование операций и Задачи оптимизации

jiura

0

101

05 апр 2017, 12:35

Задача оптимального распределения ресурсов между отраслями.

в форуме Исследование операций и Задачи оптимизации

zloba

1

761

04 янв 2014, 16:05

Выбор оптимального метода для решения системы уравнений

в форуме Размышления по поводу и без

granit201z

14

298

12 мар 2017, 16:59


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved