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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Нахождение оптимального пути по веткам метро
СообщениеДобавлено: 12 май 2017, 11:21 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

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

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

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


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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Нахождение оптимального пути по веткам метро
СообщениеДобавлено: 12 май 2017, 13:58 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

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

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

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

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

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

gorinich_igor

0

315

29 ноя 2017, 16:03

Нахождение критического пути в сетевом графике

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

baton

0

112

05 май 2022, 01:53

Человек в метро, куда девается энергия?

в форуме Школьная физика

Alexander Mashtakov

4

553

19 янв 2020, 13:55

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

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

FF117

0

230

13 июн 2017, 22:04

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

в форуме Теория вероятностей

Zura69

5

215

12 мар 2020, 12:22

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

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

evch85

0

329

29 окт 2014, 15:41

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

в форуме Microsoft Excel

evgeniymx

3

810

03 ноя 2015, 20:13

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

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

akubonin

2

467

02 фев 2016, 15:53

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

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

DmitryRUS90

2

87

03 окт 2023, 11:40

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

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

jiura

0

247

05 апр 2017, 11:35


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



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

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


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

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

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

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