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

    Прикреплённая картинка
    Прикреплённая картинка

    Поштудировал описание задачи в инете.
    Вот чисто математически + графически я понимаю, как это решается. Т е на бумаге все легко посчитаю, нарисую стрелочки оптимального маршрута и пр. С этим проблем нет. Проблема в том, как это ПРАВИЛЬНО закодировать, а если быть более точным, нужен норм.алгоритм + правильные структуры данных для всего этого.

    Пусть входные данные задаются в виде весовой матрицы, т е матрицы размером N * N (N = 10). На пересечении строки и колонки стоит стоимость перевозки, если между этими городами есть связь.
    1. Ищем решение от конца в начало, т е анализ начинается от города №10 и продвигаемся к №1.
    2. Мне казалось, что здесь пригодится структура данных ОЧЕРЕДЬ.

    Помещаем в очередь вершину №10.
    На следующем этапе помещаем в очередь все вершины, смежные с №10. Это вершины №7, №8 и №9. Одновременно с этим считаем расстояние до каждой из этих вершин из №10. После этого вершину №10 удаляем из очереди и помечаем ее как обработанную.
    На следующем этапе нужно рассмотреть ВСЕ СМЕЖНЫЕ вершины с любой из вершин №7, №8 и №9.
    Тут есть проблемка, т к, например, вершина №5 является одновременно смежной и для №7 и для №8, т е если вершины {7, 8, 9} обрабатываются последовательно, то вершина №5 будет учитываться ДВАЖДЫ, что приведет к чему-то нехорошему). Я прекрасно понимаю, что для вершины №5 рассматривается МИН(5-7, 5-8). Для вершины №6 = МИН(6-8, 6-9).
    ТО ЕСТЬ ОЧЕРЕДЬ ЗДЕСЬ ДЛЯ АНАЛИЗА НЕ НУЖНА, ТАК?? или нужно заводить 2 очереди для разных "групп" вершин. думаю, что это бредовая затея) В принципе, на каких-то переборах очередей в циклах, это все можно реализовать, но, скорее всего, будет крайне неэффективно и неправильно с позиции структур данных.

    Также ведь еще нужно найти все города, входящие в маршрут, т е куда их записывать в процессе анализа.
    И, собственно, про динамическое программирование. Насколько понимаю, ДП требует, чтобы было использовано:
    1. зависимость элементов динамики друг от друга
    2. значение начальных состояний

    ну с п.2 вроде понятно. Стоим в вершине №10 и стоимость перевозки равна 0.
    с п.1, хм. Ну есть зависимость ведь, чтобы перейти к анализу, например №5, сначала анализируем №7 и №8. При анализе №7 анализируем №10.
    Также хочется понять, нужна ли в коде какая-то ядровая функция, которая, на вход принимает номер обрабатываемой вершины, а на выходе, например, выдает минимум затрат для этой вершины или вообще все делается в циклах на стартовой весовой матрице.

    подскажите как быть-то, буду признателен
      Итак, у нас есть множество вершин Vi, множество ребер Eij, для каждого ребра, соединяющего Vi и Vj, задан неотрицательный вес w(i, j), необходимо найти и вывести кратчайший путь из V1 в указанную вершину.

      Поскольку веса ребер неотрицательные, можно использовать алгоритм Дейкстры. Тогда для каждого Vi получим d(i) - стоимость минимального пути V1 -> Vi. Затем нужно построить список узлов, входящих в этот путь.

      Строим путь от конца к началу. Заведем список, состоящий из одной вершины (конечной). Затем в цикле:
      - смотрим на первую вершину в списке (Vk), ищем все вершины Vi, для которых есть ребро Eik;
      - для каждой Vi вычисляем стоимость d(i) + w(i, k), если эта сумма равна d(k), значит мы пришли в Vk именно из этой вершины Vi, заносим ее в начало списка (может получиться, что это условие выполняется для нескольких вершин Vi, тогда неважно, какую из них включать в путь - стоимость результата будет одна и та же);
      - продолжаем, пока в списке не окажется V1 - тогда список и будет искомым путем.
        AVA12, эх, я в первом посте хотел написать, что можно заюзать алгортим Дейкстры, т к он позволяет найти кратчайший путь в графе от заданной вершины до всех остальных, но мне казалось, что здесь его применять нельзя, т к он не использует принципы дин.прог.

        если можно заюзать Дейкстру, тогда мне все сразу понятно и все смогу найти, т к уже не один раз его УСПЕШНО кодировал на практике)

        ТО ЕСТЬ ИСПОЛЬЗОВАТЬ ДЕЙКСТРУ МОЖНО, ДА??)

        P.S. на самом деле я не оч.глубоко понимацию концепт дин.прог., т к там стараются делать упор на рекурсию, мемоизацию, а в дейкстре сплошные циклы и одномерные массивы....
          Странные какие-то задачи. Во всех вместо эффективного метода решения предлагается использовать что-то не совсем подходящее.

          А каковы принципы динамического программирования?

          Ну и алгоритм, отвечающий названным принципам
          Конкретно этот граф можно разбить на слои (точнее он уже разбит).
          В первом слое три города (2, 3, 4).
          Считаем минимальные стоимости доставки до узлов первого слоя из начального узла.
          Во втором слое города 5 и 6.
          Считаем минимальные стоимости доставки до них из городов первого слоя (плюс стоимости доставки до этих городов).
          То же делаем для третьего слоя (7, 8, 9) и для целевого города (10).

          Ну и требования к графу, чтобы динамическое программирование на нём работало:
          Граф должен разбиваться на слои так, чтобы:
          1. Вершины каждого слоя были связаны с вершинами предыдущего и следующего слоя. Не должно быть рёбер внутри слоя или прыгающих через слой.
          2. В двудольном подграфе содержащем соседние слои не должно быть цепей с суммарным весом меньше ребра, соединяющего концы цепи.
          Из-за этих требований обычно динамическое программирование на графах не применяется - проверка условий оказывается сложнее, чем обычные алгоритмы. Однако бывают задачи в которых можно сразу сгенерировать граф, удовлетворяющий этим условиям.
          Первое условие можно немного ослабить в плане перескакивающих рёбер, вставив дополнительную вершину.

          Добавлено
          Если вершины перенумерованы послойно, как в этой задаче, можно их обрабатывать последовательно

          Cost[1] = 0

          Cost[2] = Cost[1] + 7 = 7 # Путь 1-2
          Cost[3] = Cost[1] + 5 = 5 # 1-3
          Cost[4] = Cost[1] + 6 = 6 # 1-4

          Cost[5] = min(Cost[2] + 4, Cost[3] + 6, Cost[4] + 10) = min(11, 11, 16) = 11 # 1-2-5 или 1-3-5
          Cost[6] = min(Cost[2] + 8, Cost[3] + 3, Cost[4] + 9) = min(15, 8, 15) = 8 # 1-3-6

          Cost[7] = Cost[5] + 6 = 17 # 1-2-5-7 или 1-3-5-7
          Cost[8] = min(Cost[5] + 8, Cost[6] + 5) = min(19, 13) = 13 # 1-3-6-8
          Cost[9] = Cost[6] + 4 = 12 # 1-3-6-9

          Cost[10] = min(Cost[7] + 9, Cost[8] + 7, Cost[9] + 11) = min(26, 20, 23) = 20 # путь 1-3-6-8-10
            amk, т е алго Дейкстры использовать нельзя (из-за требований в условии про ДП), так??
            Сообщение отредактировано: FasterHarder -
              FasterHarder, а что вообще такое - "динамическое программирование"? Как именно формулирует этот термин тот, кто задает задачи? Каковы четкие критерии определения "вот тут динамическое программирование, а вот тут - не динамическое (или не программирование)"? Если четких критериев нет, то смело используй Дейкстру с дополнениями, а все возражения посылай в /dev/null.
                Цитата amk @
                сли вершины перенумерованы послойно, как в этой задаче, можно их обрабатывать последовательно

                да, такое описание алгоритма я читал в инете, правда называют их зонами или группами, но это не суть важно, разумеется

                но вернемся к структурам данных.
                на 1-ом этапе нужно получить эти зоны/группы/слои. В этом поможет обход графа В ШИРИНУ (+очередь). "Выпишем" все вершины в графа в одномерный массив по возрастанию/убыванию номеров групп.
                затем обрабатываем вершины из каждой группы последовательно + параллельно отслеживаем связи этих вершин из предыдущей группы.

                это, если коротко и самую суть.

                Добавлено
                Цитата AVA12 @
                а что вообще такое - "динамическое программирование"?

                :) , ну, я думаю, что ты много раз и сам видел всякие определения и рассуждения на эту тему + понимаешь это гораздо лучше меня. В вики целая статья посвящена ДП)
                Кто-то говорит, что ДП - один из методов оптимизации.
                Мне вот эта статейка понравилась

                Добавлено
                Цитата amk @
                Не должно быть рёбер внутри слоя или прыгающих через слой.

                я понял о чем ты говоришь.
                кстати, далеко не факт, что такой ситуации не может возникнуть...
                  Алгоритм Форда-Беллмана тоже метод динамического программирования. Инфа 100%, в какой-то книге читала.
                  Собственно, Беллман и ДП придумал, и этот алгоритм.
                  Граф нужно представить списками инцидентности типа "пред", т.к. для каждой вершины нужно знать список предыдущих "соседок".

                  Добавлено
                  Всем привет!
                  Я - Swetlana, я вернулась :)
                  Даже припомнила, почему там можно применять ДП.

                  ДП основано на чём: на отсутствии у системы последействия.
                  То есть, мы находимся в текущем состоянии и из него ищем оптимальное продолжение.
                  А историю, как мы попали в это состояние - мы не помним.
                  То есть, если кратчайший путь между s и t проходит через вершину v, то он делится на кратчайший путь от s до v и кратчайший путь от v до t.
                  Это не всегда так.
                  Если выполнение поворота требует времени, т.е. удлиняет путь, то на перекрёстке нужно помнить, из какой вершины мы попали в текущую, придётся выполнять поворот или нет.
                    Цитата FasterHarder @
                    на 1-ом этапе нужно получить эти зоны/группы/слои. В этом поможет обход графа В ШИРИНУ (+очередь).
                    Для графов общего вида это не работает.
                      Цитата swf @
                      Алгоритм Форда-Беллмана

                      да, кстати, точняк), правда там не должно быть отрицательных циклов.

                      Цитата swf @
                      Беллман и ДП придумал

                      тоже верно, в 50-е годы
                        https://foxford.ru/wiki/informatika/algoritm-forda-bellmana
                        Алгоритм тот же (что и везде), но вводят функцию с двумя аргументами.
                        Сообщение отредактировано: swf -
                          Цитата
                          я думаю, что ты много раз и сам видел всякие определения и рассуждения на эту тему + понимаешь это гораздо лучше меня. В вики целая статья посвящена ДП

                          Это все хвилософия. Про смысл жизни, к примеру, много тонн макулатуры понаписано, а четкого определения и критериев все нет. В википедии то же самое. Читаю "определения" и в упор не понимаю, как можно применить их на практике для разделения "вот тут - да, а вот тут - нет". Что такое, к примеру, "подзадача меньшего размера"? Та же задача, только использующая часть входных данных? Или же другая задача, выход которой подается на вход переформулированной задачи? Или что?

                          Вот, к примеру, предложенное мной решение состоит из двух этапов: нахождение кратчайших расстояний и построение кратчайшего пути. Второй этап получает на вход данные, полученные на первом - это и есть две "подзадачи меньшего размера" или еще нет? Каждый этап строит решение постепенно, один узел за другим, на каждом шаге мы получаем все увеличивающуюся часть требуемого на этом этапе результата - это и есть "подзадачи меньшего размера"? Чего не хватает этому решению, чтобы можно было гордо налепить бирку "dynamic programming inside"? Или же тут всего хватает? Но оба приема - и поэтапное преобразование входных данных, и постепенное построение результата - используются в программировании повсеместно. Тогда получается, что любой алгоритм - даже, например, решение квадратного уравнения - можно относить к динамическому программированию?
                          Сообщение отредактировано: AVA12 -
                            Я так понимаю, где ДП:
                            1. Система без последействия и обратной связи.
                            2. Решение находят с помощью многошагового процесса принятия решения (строгое определение всех этих слов - в книге Беллмана "Динамическое программирование и современная теория управления", 1969 года издания.).
                            Цитата
                            Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):
                            Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.


                            Как я это понимаю.
                            1. Чтобы выбрать оптимальное управление из текущего состояния на текущем шаге не нужно помнить историю процесса, как мы попали в текущее состояние.
                            Или другими словами. Задача раскладывается на подзадачи, которые можно решать независимо и параллельно, затем объединять их.
                            (В логике это всю жизнь называлось "разложимая система продукций" вообще-то, но не будем приплетать сюда логику.)
                            То есть можно найти оптимальное решение от начала до некоего фиксированного состояния, затем найти оптимальное решение от фиксированного состояния до конечного, сложить их и получить оптимальное решение при условии, что оно проходит через это фиксированное состояние.
                            2. Отсутствие обратной связи, вроде, управление на текущем шаге не меняет предыдущие состояния. Но про обратную связь точно не скажу.

                            Таких задач (без последействия и обратной связи) на самом деле не очень много, все они хорошо изучены и все решаются ДП.
                            Пример, когда одна и та же задача может решаться ДП или не ДП.
                            Набор заданной суммы из заданных слагаемых.
                            ДП за псевдополиномиальное время находит ровно одно решение;
                            алгоритм с возвратом за экспоненциальное время находит все решения.
                              на мой дилетантский взгляд ДП там ярко применимо, где:
                              1. нужно запомнить какое-то решение, чтобы при необходимости извлечь сразу ответ (мемоизация) без повторного решения
                              2. большую задачу можно разбить НА РЯД НЕБОЛЬШИХ, и что самое важное эти подзадачи должны решаться рекурсивно
                                Рекурсией можно что угодно написать, даже сортировку "пузырёк" :)

                                Я выяснила, к ДП в "узком" смысле относят "табличный" способ решения задачи. Там вообще нет рекурсии.
                                И по поводу задания. Чего там хотят.
                                Может, там хотят не оптимизированный алгоритм Ф.-Б., а как здесь первый вариант, с двумерной табличкой
                                https://foxford.ru/wiki/informatika/algoritm-forda-bellmana
                                Сообщение отредактировано: swf -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (3) [1] 2 3  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,1967 ]   [ 18 queries used ]   [ Generated: 19.04.24, 01:21 GMT ]