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

Математический форум 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 
Не в сети
Оракул
Зарегистрирован:
02 дек 2016, 23:55
Сообщений: 793
Cпасибо сказано: 47
Спасибо получено:
138 раз в 128 сообщениях
Очков репутации: 25

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

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

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


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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Нахождение оптимального пути по веткам метро
СообщениеДобавлено: 12 май 2017, 14:58 
Не в сети
Оракул
Зарегистрирован:
02 дек 2016, 23:55
Сообщений: 793
Cпасибо сказано: 47
Спасибо получено:
138 раз в 128 сообщениях
Очков репутации: 25

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

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

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

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

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

gorinich_igor

0

25

29 ноя 2017, 17:03

Поиск оптимального решения

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

elgin88

4

430

10 мар 2012, 14:29

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

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

FF117

0

64

13 июн 2017, 23:04

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

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

evch85

0

153

29 окт 2014, 16:41

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

в форуме Microsoft Excel

evgeniymx

3

339

03 ноя 2015, 21:13

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

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

akubonin

2

177

02 фев 2016, 16:53

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

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

bobah8

0

83

13 окт 2016, 17:02

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

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

Earl_Us

12

574

13 сен 2013, 10:56

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

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

jiura

0

59

05 апр 2017, 12:35

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

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

Grigoriy

0

255

24 май 2012, 22:32


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



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

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


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

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

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

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