На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) 1 [2]  все  ( Перейти к последнему сообщению )  
> алгоритм Дейкстры с доп.условием , неориентированные графы
    Цитата m-ch @
    3. По найденному маршруту определяем минимальный вес в маршруте, это и будет ограничение поезда из одного города в другой

    Вот как-то неочевидно.
    Минимальное остовное дерево минимизирует именно вес всего дерева, а не максимальную стоимость ребра этого дерева. Аналогично-обратно и для максимального дерева.

    Цитата m-ch @
    при этом вес поезда будет не менее уже определенного

    Вот! сам говоришь - не меньше! Значит, может быть и больше? А значит, может быть и более одного маршрута, где больше, и у них эти "больше" могут быть разными. И тот, у которого будет самое большое "больше" (да и вообще требующийся в задаче путь), не обязан быть кратчайшим.

    Добавлено

    В теории задача решается экстенсивно (не знаю как будет с производительностью).

    Просто берём и волновым или иным алгоритмом тупо убеждаемся, что узел назначения достижим из исходного узла. Плюя ядовитой слюной на длину и пропускную способность.
    Выбрасываем минимальное по пропускной способности ребро (если использовали не волну, а что-то ещё, и на предыдущем поиске фиксировали путь - выбрасываем минимальное ребро пути и сразу все меньшие рёбра, в путь не входящие). Повторяем.
    Выбрасываем рёбра до тех пор, пока при очередном выбрасывании не получим недостижимость.
    Вот собственно вес этого последнего выброшенного ребра и будет возможным максимумом пропускной способности любого пути от исходного узла до узла назначения. Более того, любой маршрут будет проходить через это ребро.
    Сообщение отредактировано: Akina -
      FasterHarder, посмотри видосик - возможно тебя это заинтересует.
        Цитата FasterHarder @
        Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса.
        Это случаем не построение остова, только не минимального, как принято, а максимального? + при этом фактор протяженности вообще не играет никакой роли, как понимаю, нужно смотреть ТОЛЬКО на тоннаж.
        Или есть какое-то стандартное название алгоритма для такого задания?

        Получилось решить?
        Фактор протяженности влияет, но и дополнительное условие есть.
        Насколько знаю, такая задача называется - Constrained Shortest Path First
        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
        0 пользователей:


        Рейтинг@Mail.ru
        [ Script execution time: 0,0198 ]   [ 15 queries used ]   [ Generated: 28.03.24, 14:36 GMT ]