Первая дуэль. , Наичистейший С++ vs С++ + stl + boost

Цитата Sazabis @ 20.09.05, 09:13

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

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

Добавлено 20.09.05, 09:21
Кстати, судя по приведенному примеру исходного файла, граф может быть цикличный? Т. е. между двумя перекрестками могут быть две дороги, идущие в разных направлениях?

Цитата Flex Ferrum @ 20.09.05, 09:20

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

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

Добавлено 20.09.05, 11:53

Цитата Flex Ferrum @ 20.09.05, 09:20

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

могут

Добавлено 20.09.05, 11:54
но смысла возвращаться назад нету

Кстати, а кто будет секундантами?

Тогда получается, что тестируются два прогера, а не C++ vs C++/stl/boost. Думаю, что после всего можно "всем вместе" (детали потом) отредактировать код и посмотреть, что получилось лучше по заданным критериям.

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

Цитата Тайлер @ 20.09.05, 12:20

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

Способ решения - известен. Поиск кратчайшего пути на помеченном ориентированном цикличном графе. Оптимальные алгоритмы собственно поиска - тоже (Дейкстры или Бельмана-Форда, но в данном случае достатчно Дейкстры). Так что задача сводится именно к реализации оных алгоритмов.

ОК, а как насчет моего первого замечания

Дабы действительно не изобретать по крайней мере математических велосипедов приведу текст оного алгоритма:

Цитата

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.

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.
Добавлено 20.09.05, 12:32

Цитата Тайлер @ 20.09.05, 12:30

ОК, а как насчет моего первого замечания

См. пост №22 (предыдущий).

Цитата Flex Ferrum @ 20.09.05, 12:18

Кстати, а кто будет секундантами?

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

Цитата Тайлер @ 20.09.05, 12:30

ОК, а как насчет моего первого замечания

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

Добавлено 20.09.05, 12:40
Только пусть хоть что то решают! а то nvm придеться реализовывать только vector<> , что имхо не очень интересно.

Цитата Sazabis @ 20.09.05, 12:37

Только пусть хоть что то решают! а то nvm придеться реализовывать только vector<> , что имхо не очень интересно.

Ну, от алгоритма на псевдоязыке до его реализации на конкретом ЯВУ путь бывает очень длинным... Или очень коротким...

Цитата Flex Ferrum @ 20.09.05, 12:27

Способ решения - известен. Поиск кратчайшего пути на помеченном ориентированном цикличном графе. Оптимальные алгоритмы собственно поиска - тоже (Дейкстры или Бельмана-Форда, но в данном случае достатчно Дейкстры). Так что задача сводится именно к реализации оных алгоритмов.

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

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

-юсртыхэю 20.09.05, 14:36

Цитата Sazabis @ 20.09.05, 09:13

считаю вполне нормально, если весь граф будет в памяти. Вообще то больше памяти больше не надо?

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

Цитата nvm @ 20.09.05, 14:04

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

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

Добавлено 20.09.05, 14:41

Цитата nvm @ 20.09.05, 14:04

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

Если Вы будите для этой задачи использовать 400 Мб, то грош Вам цена Надеюсь подобных эксцессов не будет

Цитата Sazabis @ 20.09.05, 14:38

Если Вы будите для этой задачи использовать 400 Мб, то грош Вам цена Надеюсь подобных эксцессов не будет

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

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

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

-юсртыхэю 20.09.05, 15:16

Цитата Sazabis @ 20.09.05, 11:49

Цитата Flex Ferrum @ 20.09.05, 09:20

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

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

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

Yes!

Цитата

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

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

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

PS: Исходный текст буквально с колес, пока что особо не причесывал. Компилилось на VC 7.1
Прикреплённый файлpath_find.zip (1.64 Кбайт, скачиваний: 218)

Цитата Тайлер @ 20.09.05, 12:20

Тогда получается, что тестируются два прогера, а не C++ vs C++/stl/boost. Думаю, что после всего можно "всем вместе" (детали потом) отредактировать код и посмотреть, что получилось лучше по заданным критериям.

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

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

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

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

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

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

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

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

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

Жду ответа на примеры - сам проверить не могу из-за отсутствия библиотек.

Сообщение отредактировано: nvm - 20.09.05, 17:12

Флекс, CodeWarrior матерится на строку

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'и дает).

    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 стоит для побаловаться. Надо на него переходить.