Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 4 ] |
|
Автор | Сообщение | ||
---|---|---|---|
PadawanC |
|
||
Задача: Есть карта метрополитена (Московского к примеру), доступны данные о длинах перегонов, времени, связях станций. Необходимо придумать алгоритм, позволяющий посетить все ветки метрополитена оптимальным способом (минимальное время или расстояние и т.д.). Критерий можно выбрать самому. Для посещения ветки достаточно посетить любую из её станций. Для решения задачи подходит Алгоритм Литтла (связи станций как вершины графа), но алгоритм даёт возможность посетить все вершины графа по оптимальному маршруту (минимальная длина дуг). В задаче нужно посетить хотя бы одну любую станцию каждой ветки метро. Как здесь можно применить указанный алгоритм, как искать уже посещённые? Какая модификация алгоритма потребуется? (возможно существует иной способ решения). |
|||
Вернуться к началу | |||
Booker48 |
|
||
Можно попробовать рассмотреть граф,в котором вершины - связи между ветками метро.
|
|||
Вернуться к началу | |||
PadawanC |
|
|
Booker48 писал(а): Можно попробовать рассмотреть граф,в котором вершины - связи между ветками метро. Так и есть, ток вот если прямо использовать алгоритм Литтла, то найдем оптимальный путь через все пересадки, а по задаче не нужно заходить на пересадку одной и той же линии дважды (хоть и в разных местах). |
||
Вернуться к началу | ||
Booker48 |
|
||
Тогда задачу поточнее сформулируйте, чего там ещё нельзя. Т.к. вот этого
PadawanC писал(а): по задаче не нужно заходить на пересадку одной и той же линии дважды в исходной формулировке нет. Если это учитывать, то имеем, скорее, задачу о нахождении эйлерова цикла,который, кстати, совершенно необязательно существует в графе московского метрополитена. |
|||
Вернуться к началу | |||
[ Сообщений: 4 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Нахождение кратчайшего пути во взвешенном графе | 0 |
315 |
29 ноя 2017, 16:03 |
|
Нахождение критического пути в сетевом графике | 0 |
112 |
05 май 2022, 01:53 |
|
Человек в метро, куда девается энергия?
в форуме Школьная физика |
4 |
552 |
19 янв 2020, 13:55 |
|
Поиск оптимального варианта
в форуме Комбинаторика и Теория вероятностей |
0 |
230 |
13 июн 2017, 22:04 |
|
Поиск оптимального кол-ва бросков
в форуме Теория вероятностей |
5 |
215 |
12 мар 2020, 12:22 |
|
Выбор оптимального набора продуктов | 0 |
329 |
29 окт 2014, 15:41 |
|
Задача оптимального производства продукции
в форуме Microsoft Excel |
3 |
810 |
03 ноя 2015, 20:13 |
|
Задача по нахождению оптимального заказа | 2 |
467 |
02 фев 2016, 15:53 |
|
Задача оптимального распределения ресурсов | 2 |
87 |
03 окт 2023, 11:40 |
|
Метод оптимального распределения средств +взаимозависимость | 0 |
247 |
05 апр 2017, 11:35 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |