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

    Как известно, алгоритм Прима позволяет получить минимальное остовное дерево. С точки зрения мат.модели и алгоритма вроде там все понятно: берем произвольную вершину, затем берем смежную с минимальным ребром, потом среди отобранных снова смежную с мин. ребром и т.д., пока не будут взяты все вершины. Тут вроде все достаточно просто...

    Программу я написал ("чистый" Си, стандарт С89) и вроде все прекрасно работает:
    Прикреплённая картинка
    Прикреплённая картинка



    пока не переходим на big data, я бы даже сказал medium data). Решил потестировать программу на нормальном кол-ве вершин, вот свел результаты теста в таблицу _ диаграмма:
    Прикреплённая картинка
    Прикреплённая картинка


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


    Мне хотелось обсудить некоторые детали по алгоритму Прима.
    Говорится, что Прима будет работать на взвешенном неориентированном связном графе.

    вопрос №1: То есть, перед тем, как запускать построение мин.остова надо убедиться, что граф связный? То есть содержит ровно 1 компоненту связности. Если компонент связности БОЛЬШЕ 1ой, то решения нет? Или для каждой компоненты строим мин.остов. Склоняюсь к тому, что решения нет.

    момент №2: Если граф является ориентированным, то Прима не сможет работать всегда! Т к алгоритм может легко уйти в тупик, взяв минимальный вес, а там тупик) Понятно, что можно подобрать конфигурации орграфа, когда Прима построить верный миностов, но в данном случае алгоритм не соот-ет свойству массовости ---> не является алгоритмом...

    вопрос №3: Хорошо, когда веса все уникальны! В этом случае, как понимаю, миностов существует в единственном экземпляре. А, если есть дубликатные веса...Ну, например, 3 ребра имеют равный вес = 17, а остальные все уникальные. Ведь в этом случае существует более одного миностова. Здесь ведь какая-то комбинаторика замешана, вроде? Может перестановки с повторениями или около того? Есть формула, которая позволяет узнать, сколько всего возможно миностовов, зная частотности появления весов? (или просто перемножить эти частотности, хм...) Кстати, если пытаться получить ВСЕ возможные миностовы (когда есть дубликаты весов), то, ИМХО, сложность решения по экспоненте увеличивается) (хотя может и нет и там все на рекурсии как-то мутить надо)

    момент №4: Как известно, многие графовые алгоритмы чувствительны к отрицательным величинам (весам). Как понимаю, Приму побоку это. Прекрасно отработает.

    момент №5: Допустим, что граф взвешенный, связный, неорграф и веса любые целые числа (как +, так и -). Если рассматривать задание графа через матрицу весов, то отсутствие веса, как можно обозначить, например, если данные считываются из файла текстового?? Например, в текущей программе я ставлю 0, но у меня все веса НАТУРАЛЬНЫЕ числа и проблем никаких...Брать какое-то +inf/-inf, но теоретически вес может иметь любое допустимое разрешенное типом данных число, в том числе и пограничные значения. 0 ставить тоже нельзя, т к допустимы отрицательные веса. Вижу решение проблемы только через переход структуры данных, отвечающей за весовую матрицу на тип дробный (например, double), double >> long int > int. Но в этом случае резко возрастает объем динамической памяти, т к sizeof(double) / sizeof(int) >= 2. Или вообще надо работать через списки смежности в этом случае и про задание через весовую матрицу следует забыть??

    Скрытый текст
    Просмотрел около 20 материалов на тему "Алгоритм Прима"! Как-то у них там по коду совсем все просто получается, юзают всякие STL-ские приблуды, приоритетные очереди и кода строчке 20-25 (код в большинстве случаев, конечно, плох, с точки зрения проектировки, ИМХО), у меня в прожке под 200 строк кода и под 8 функций. Но код на Си и как бы все приходится кодить на низком уровне, но это и хорошо) + нет даже близко ни одного материала, который в деталях поясняет все тонкости. А вообще с одной стороны вроде много материала на эту тему, а вот исчерпывающего ни одного даже близко!

    и приложу главную функцию программы (С89). Если что-то оптимизировать, то придется там копаться, но не факт:
    ExpandedWrap disabled
      // нахождение номера очередной вершины, которая будет добавлена в минимальный остов и до нее минимальный вес
      // pselected - содержит номера вершин, уже добавленных в мин.остов
      // pweight_matrix - весовая матрица графа
      // pvertex_count - кол-во вершин графа
      // pnumber_vertex_parent - отвечат за номер вершины, которая будет смежной для новой добавленной в мин.остов (нужна для восстановления маршрута)
      unsigned short Get_next_vertex(
                                      const unsigned short* const pselected,
                                      const int** const pweight_matrix,
                                      const unsigned short pvertex_count,
                                      unsigned short* const pnumber_vertex_parent)
      {
          unsigned short iselected, vertex_number, ivertex;
          int min_weight = INT_MAX, current_weight;
       
          for(iselected = 0; iselected < pvertex_count; iselected++)
          {
              if(pselected[iselected] == TRUE)
              {
                  for(ivertex = 0; ivertex < pvertex_count; ivertex++)
                  {
                      if((pweight_matrix[iselected][ivertex] != 0) && (pselected[ivertex] == FALSE))
                      {
                          current_weight = pweight_matrix[iselected][ivertex];
                          if(current_weight < min_weight)
                          {
                              min_weight = current_weight;
                              vertex_number = ivertex + 1;
                              *pnumber_vertex_parent = iselected + 1;
                          }
                      }
                  }
              }
          }
       
          return vertex_number;
      }


    Добавлено
    забыл еще дописать, что, когда тестировалось на разном кол-ве вершин, то появление ребра (веса) было с вероятностью 50%. Т е каждая вершина графа связывалась с половиной всех вершин остальных...наверное, можно считать, что неорграф сильно связный, но НЕ полный. Вероятность того, что при генерации весов будет больше 1ой компоненты связности ----> 0 при увеличении числа вершин
    Сообщение отредактировано: FasterHarder -
      В общем понял (прочитав в одном материале), что надо напрочь отказываться от весовой матрицы и переходить на список смежности.
      Колоссальной оптимизации можно добиться, если построить список смежности, упорядочив внутри по весу по неубыванию...

      На рис.показал, что из себя будет представлять такой список смежности (один из вариантов реализации, далеко не факт, что оптимальный):
      Прикреплённая картинка
      Прикреплённая картинка


      То есть, если подается на вход весовая матрица (например, считыванием из файла + с клавиатуры обычно не вводят весовые матрицы - неудобно абсолютно+долго), то строим список смежности, добавляя по блоку информации в нужный ЛОС, не теряя при этом отсортированности. По факту возможны 3 операции вставки в ЛОС: в начало, в конец и в "средину". Придется каждую из них программить, эх...итоговая программа вообще разрастется уже до 300+ строк кода

      Если происходит ввод с клавиатуры, то требуем формат: <1ая смежная вершина> <2ая смежная вершина> <вес ребра между ними>, то есть 3 числа. И также после этого происходит добавление в таблицу списка смежности, не теряя упорядоченности.

      Получив "отсортированный" список смежности, операция поиска минимального веса будет выполняться за время O(n) (n - кол-во вершин графа). Это может в "миллиарды" раз ускорить алгоритм). Правда после этого, надо производить удаление соответствующего узла из начало списка + ведь еще придется удалить симметричного близнеца(!), который будет стоять не в начале списка. Вот эта перестройка списка смежности может быть не оч.быстрой, хотя...

      Также благодаря списку смежности и удалению узлов в конце концов может не остаться ни одного элемента в конкретном ЛОС - и это замечательно, в этом случае вершина больше вообще не участвует в обработке (об этом писал ранее).

      Единственный момент, если обрабатывается ПОЛНЫЙ ГРАФ, то вроде в этом случае нецелесообразно вообще получать список смежности, хотя...Ведь на построение уйдет кучу времени, но потом это будет окупаться при поиске наименьшего. Здесь непонятка, стоит ли овчинка выделки. С др.стороны ведь неизвестно, какого типа подается на вход граф и надо убедиться, что он является полным + очевидно, что в 99.99% граф будет подаваться неполным, поэтому, независимо от конфигурации графа (полный, разреженный, плотный и пр.) надо всегда получать список смежности и это ДОЛЖНО РЕЗКО увеличить производительность выполнения прожки, вроде)

      p.s. тут сплошная динамика и все это надо закодить корректно и будет несколько сотен строк кода...в их примерчиках по 25-30 строк, правда 19 программ из 20, которые я видел были на С++ (в связке с СТЛ-кой приблудой) + на весовых матрицах (без построения списка смежности). Пусть попробуют на Си покодить, создавая с нуля велосипеды))
        Ты что-то странное делаешь. Поиск минимального ребра лучше делать с помощью кучи, т.к. она позволяет брать минимум из элементов за О(1). Как при этом хранится сам граф - не так уж и важно. Т.е. алгоритм примерно такой выходит:
        1) Добавляешь любую вершину в дерево, а все её рёбра в кучу.
        2) Достаёшь из кучи минимальное ребро до тех пор, пока не достанешь ребро, ведущее в вершину, ещё не лежащую в дереве.
        3) Добавляешь это ребро в дерево, а все рёбра из добавленной вершины, которые ведут в вершины, не лежащие в дереве - в кучу.
        4) Если остались ещё вершины не в дереве - идём в п. 2, иначе выходим.
          В общем, немого полазив по зарубежным материалам (самую малость) сделал такие выводы (возможно, что ошибочные, но это и не важно) ) - на данный момент НЕ существует оптимального решения с тз кодирования (структур данных) алгоритма Прима...

          Как только не делают: и через весовую матрицу, и через список смежности (тут вообще масса подвидов), и через КЧД (red-black tree, это ведь они), и через кучи, и даже вроде что-то на хешировании есть и пр. пр.
          Оценка сложности различная и типа, если есть что-то O(n^2 + n*m), то, задействовав что-то, могут получить O(n^2 + nlog(m)) и это считается прогрессом и пр. Как делается оценка сложности - без понятия...

          Я реализовал 2 дополнительных программы через список смежности:
          1. получая отсортированные списки по весу
          2. произвольные списки весов

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

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

          В общем, я вроде хорошо понял, как работать с алгоритмом Прима через весовую матрицу (это считается самым тупым и медленным способом), буду считать, что знаю, что такое алгоритм Прима. И так сойдет (с) 8-)

          Скрытый текст
          На мой дилетантский взгляд: работать с графами через матрицу смежности/весов гораздо приятнее, чем через список смежности. Используя обращение m[i][j] моментально получаешь доступ к нужной тебе информации. Когда список смежности, то, например, на элементарный вопрос: "А существует ли связь между вершина №3 и №11?" моментально ответ хрен дашь - надо что-то там сканировать, проверять и пр. пр. (речь про язык Си). Конечно, если юзать стл-ские контейнеры, то значительно упрощается процесс кодирования всего этого (vector - вообще сказка) ), но это не отменяет того факта, что понимать при этом алгоритм все равно нужно максимально...

          2. Мне не попался на глаза (возможно, плохо искал) ни один материал, который бы всеобъемлюще исследовал Прима, рассказывая об алгоритмах, а также об используемых структурах данных(!!), проводил замеры скорости работы в зависимости от выбранного подхода, от конфигурации графа и пр. пр. Даже близко не встречал ни одного материала, который бы закрывал все нюансы на 10% хотя бы...Одни отрывки + реализация на С++...
          Сообщение отредактировано: FasterHarder -
            Цитата FasterHarder @
            Программу я написал ("чистый" Си, стандарт С89) и вроде все прекрасно работает:
            пока не переходим на big data, я бы даже сказал medium data).

            А что вы хотели от квадратичного алгоритма? Ну соптимизируете пару копеек на представлении данных. Это почти ничто.

            С матрицей смежности вам тупо памяти не хватит на серьёзный граф. Переходите на списки.
            Сообщение отредактировано: scrambrella -
              с постом №5 в принципе соглы

              Кстати, Кормен (который из Дармутского колледжа), так, шутя интересуется

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

              читая такие вопросы, как будто оказываешься в другом мире (параллельном сложном мире IT )) )
              Сорри, Томас, без понятия абсолютно ни на один вопрос, без шансов, тотальный провал, ничего, ноль, void...
              Сообщение отредактировано: FasterHarder -
                Остовное дерево это не IT. Это разводка печатных плат.
                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0931 ]   [ 22 queries used ]   [ Generated: 29.03.24, 12:49 GMT ]