На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Правила раздела:
1. Название темы - краткое описание кто/что против кого/чего
2. В первом сообщении - список параметров, по которым идет сравнение.
3. Старайтесь аргументировать свои высказывания. Фразы типа "Венда/Слюникс - ацтой" считаются флудом.
4. Давайте жить дружно и не доводить обсуждение до маразма и личных оскорблений.
Модераторы: Модераторы, Комодераторы
Страницы: (7) 1 [2] 3 4 ...  6 7 все  ( Перейти к последнему сообщению )  
> Первая дуэль., Наичистейший С++ vs С++ + stl + boost
    Цитата Sazabis @
    Не давайте лучше решать задачу динамического программировния, а не статического. Иначе требования по времени будут не актуальны.

    Так вводим или нет? И если вводим - то какие?

    Добавлено
    Кстати, судя по приведенному примеру исходного файла, граф может быть цикличный? Т. е. между двумя перекрестками могут быть две дороги, идущие в разных направлениях?
    "Математики думают, что Бог в уравнениях, нейрологи уверены, что Бог в мозге, а программисты уверены, что Бог — один из них."
    Морган Фриман
    Реализация шаблонов Jinja2 для C++ Jinja2 C++
      Цитата Flex Ferrum @
      Так вводим или нет? И если вводим - то какие?

      мы же не задачу олимпиадную решаем. _Старайтесь_ решить ее используя память O(N) где N кол-во вершин графа. Считайте что вы на собеседовании, фирма делает игры :) . Как хотите, так решайте, только одинаково, мы же, еще раз, не задачу решаем, а сравниваем подход к решению. Я не против того, если оба участника будут вкурсе оптимальной эвристики.

      Добавлено
      Цитата Flex Ferrum @
      Т. е. между двумя перекрестками могут быть две дороги, идущие в разных направлениях?

      могут

      Добавлено
      но смысла возвращаться назад нету ;)
      Dixi et ahinam levavi.
        Кстати, а кто будет секундантами?
        "Математики думают, что Бог в уравнениях, нейрологи уверены, что Бог в мозге, а программисты уверены, что Бог — один из них."
        Морган Фриман
        Реализация шаблонов Jinja2 для C++ Jinja2 C++
          Тогда получается, что тестируются два прогера, а не C++ vs C++/stl/boost. Думаю, что после всего можно "всем вместе" (детали потом) отредактировать код и посмотреть, что получилось лучше по заданным критериям.

          Добавлено
          З.Ы. Чтобы не тратить ресурсы впустую, можно выложить оптимальный алгоритм решения задачи, а Флексу и нвм пусть остается сама реализация.
            Цитата Тайлер @
            З.Ы. Чтобы не тратить ресурсы впустую, можно выложить оптимальный алгоритм решения задачи, а Флексу и нвм пусть остается сама реализация.

            Способ решения - известен. Поиск кратчайшего пути на помеченном ориентированном цикличном графе. Оптимальные алгоритмы собственно поиска - тоже (Дейкстры или Бельмана-Форда, но в данном случае достатчно Дейкстры). Так что задача сводится именно к реализации оных алгоритмов.
            "Математики думают, что Бог в уравнениях, нейрологи уверены, что Бог в мозге, а программисты уверены, что Бог — один из них."
            Морган Фриман
            Реализация шаблонов Jinja2 для C++ Jinja2 C++
              ОК, а как насчет моего первого замечания
                Дабы действительно не изобретать по крайней мере математических велосипедов приведу текст оного алгоритма:
                Цитата

                The following is the pseudo-code for Dijkstra's single-source shortest paths algorithm. w is the edge weight, d is the distance label, and p is the predecessor of each vertex which is used to encode the shortest paths tree. Q is a priority queue that supports the DECREASE-KEY operation. The visitor event points for the algorithm are indicated by the labels on the right.

                ExpandedWrap disabled
                  DIJKSTRA(G, s, w)
                    for each vertex u in V
                      d[u] := infinity
                      p[u] := u
                      color[u] := WHITE
                    end for
                    color[s] := GRAY
                    d[s] := 0
                    INSERT(Q, s)
                    while (Q != Ø)
                      u := EXTRACT-MIN(Q)
                      S := S U { u }
                      for each vertex v in Adj[u]
                        if (w(u,v) + d[u] < d[v])
                          d[v] := w(u,v) + d[u]
                          p[v] := u
                          if (color[v] = WHITE)
                            color[v] := GRAY
                            INSERT(Q, v)
                          else if (color[v] = GRAY)
                            DECREASE-KEY(Q, v)
                        else
                          ...
                      end for
                      color[u] := BLACK
                    end while
                    return (d, p)


                Взято отсюда: dijkstra_shortest_paths.
                Добавлено
                Цитата Тайлер @
                ОК, а как насчет моего первого замечания

                См. пост №22 (предыдущий).
                "Математики думают, что Бог в уравнениях, нейрологи уверены, что Бог в мозге, а программисты уверены, что Бог — один из них."
                Морган Фриман
                Реализация шаблонов Jinja2 для C++ Jinja2 C++
                  Цитата Flex Ferrum @
                  Кстати, а кто будет секундантами?

                  общественность :) неплохо было бы развести базара как в теме trainer'a

                  Цитата Тайлер @
                  ОК, а как насчет моего первого замечания

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

                  Добавлено
                  Только пусть хоть что то решают! а то nvm придеться реализовывать только vector<> ;) , что имхо не очень интересно.
                  Dixi et ahinam levavi.
                    Цитата Sazabis @
                    Только пусть хоть что то решают! а то nvm придеться реализовывать только vector<> , что имхо не очень интересно.

                    Ну, от алгоритма на псевдоязыке до его реализации на конкретом ЯВУ путь бывает очень длинным... Или очень коротким... :)
                    "Математики думают, что Бог в уравнениях, нейрологи уверены, что Бог в мозге, а программисты уверены, что Бог — один из них."
                    Морган Фриман
                    Реализация шаблонов Jinja2 для C++ Jinja2 C++
                      Цитата Flex Ferrum @
                      Способ решения - известен. Поиск кратчайшего пути на помеченном ориентированном цикличном графе. Оптимальные алгоритмы собственно поиска - тоже (Дейкстры или Бельмана-Форда, но в данном случае достатчно Дейкстры). Так что задача сводится именно к реализации оных алгоритмов.

                      Что-то мне кажется, что задача не сводится к обычному поиску пути - ведь скорость зависит от того, откуда пришли в вершину.

                      Даже динамическое программирование как-то тут непонятно, где применить
                      Может, по-простому, полный перебор путей с отсечением ветвей по Парето?

                      -юсртыхэю
                      Цитата Sazabis @
                      считаю вполне нормально, если весь граф будет в памяти. Вообще то больше памяти больше не надо?

                      В общем случае выбор между памятью и быстродействием можно предоставлять разработчику.
                      Можно позволить занимать до 400 Мб памяти (типичный объем на слабых машинах).
                        Цитата nvm @
                        Что-то мне кажется, что задача не сводится к обычному поиску пути - ведь скорость зависит от того, откуда пришли в вершину.

                        :yes:
                        полный перебор по любому, или получите приблеженный ответ, в задаче нужен единственно верный. Обещаеться что верный будет один.

                        Добавлено
                        Цитата nvm @
                        Можно позволить занимать до 400 Мб памяти (типичный объем на слабых машинах).

                        Если Вы будите для этой задачи использовать 400 Мб, то грош Вам цена ;) Надеюсь подобных эксцессов не будет :)
                        Dixi et ahinam levavi.
                          Цитата Sazabis @
                          Если Вы будите для этой задачи использовать 400 Мб, то грош Вам цена ;) Надеюсь подобных эксцессов не будет :)

                          Я бы не стал так резко высказываться..

                          Соотношение между используемой памятью и временем работы должно быть разумным: это значит, что при разумном ограничении на объем памяти (512 Мб) и время работы (10 минут) должен максимизироваться допустимый размер исходных данных.

                          Это самый логичный критерий: имеющимися ресурсами решить как можно больше задач.

                          -юсртыхэю
                          Цитата Sazabis @
                          Цитата Flex Ferrum @
                          Т. е. между двумя перекрестками могут быть две дороги, идущие в разных направлениях?

                          могут но смысла возвращаться назад нету ;)

                          Вообще говоря, есть. Легко построить пример.
                            Yes!
                            Цитата

                            Working time for 10000 iterations: 47 msecs.
                            0 5 2 3 1

                            Sazabis, давай еще тестовых файликов.

                            Исходный код в аттаче.

                            PS: Исходный текст буквально с колес, пока что особо не причесывал. Компилилось на VC 7.1
                            Прикреплённый файлПрикреплённый файлpath_find.zip (1.64 Кбайт, скачиваний: 120)
                            "Математики думают, что Бог в уравнениях, нейрологи уверены, что Бог в мозге, а программисты уверены, что Бог — один из них."
                            Морган Фриман
                            Реализация шаблонов Jinja2 для C++ Jinja2 C++
                              Цитата Тайлер @
                              Тогда получается, что тестируются два прогера, а не C++ vs C++/stl/boost. Думаю, что после всего можно "всем вместе" (детали потом) отредактировать код и посмотреть, что получилось лучше по заданным критериям.

                              Добавлено
                              З.Ы. Чтобы не тратить ресурсы впустую, можно выложить оптимальный алгоритм решения задачи, а Флексу и нвм пусть остается сама реализация.

                              Человеческий фактор в любом случае будет существенен. Но в этом и есть суть затеи (судя по названию).

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

                              Добавлено
                              Flex Ferrum,
                              ну ты и быстро - еще даже секунданты флажком не махнули.. :blink:

                              Добавлено
                              Flex Ferrum
                              Неужели этот алгоритм применим?!
                              А как насчет таких входных данных:

                              4 4 2
                              0 1 1 1
                              1 2 0 8
                              1 3 10 1
                              3 1 0 1

                              Какой выдает ответ?

                              Добавлено
                              Кстати, в условии кратные ребра исключены, а петли - нет.

                              Добавлено
                              Пример можно тогда сократить:
                              3 3 2
                              0 1 1 1
                              1 2 0 9
                              1 1 10 1

                              Жду ответа на примеры - сам проверить не могу из-за отсутствия библиотек.
                              Сообщение отредактировано: nvm -
                                Флекс, CodeWarrior матерится на строку
                                ExpandedWrap disabled
                                  Edge& e = *cur_info.m_CurIter;
                                и без const компилировать отказывается. :)
                                Цитата
                                C/C++ Error 10129

                                non-const '&' reference initialized to temporary

                                The compiler found that the initializer for a non-const reference is not an appropriate lvalue.

                                long &r = 40000;

                                Fix

                                Use a real variable to initialize reference or use a const reference.

                                long x = 4000;
                                long &y = x;
                                const long &z = 40000;
                                и typename'ов хочет(warning'и дает). :)
                                ExpandedWrap disabled
                                      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
                                      typedef typename graph_traits<Graph>::edge_descriptor Edge;
                                      typedef typename graph_traits<Graph>::out_edge_iterator EdgeIterator;
                                Но по скорости имеет MSVC7.1 в 1.5 раза. :) Правда, и исполнимый файл во столько же раз больше. :)

                                P.S. А у меня этот Metrowerks стоит для побаловаться. :D Надо на него переходить. :)
                                Во имя Ctrl, Alt и святаго Del, Enter!

                                Основам программирования не обучаю. Не интересно.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (7) 1 [2] 3 4 ...  6 7 все


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1609 ]   [ 17 queries used ]   [ Generated: 20.11.19, 22:54 GMT ]