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

M

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

Итак, с чего все начиналось? Вот с такого вот предложения:

Цитата nvm @ 16.09.05, 14:52

Аргументацией было бы сравнение результативности фирм, использующих stl+boost, и не использующих их вовсе.
Однако, последних в природе, видимо, не существует (этот факт кто-то поспешит засчитать в пользу необходимости этих технологий, но он вполне объясним и лишь данью моде).

nvm, все очень просто - можно устроить небольшое состязание. Выбрать задачку, и посмотреть - кто ее быстрей решит. Я с помощью возможностей stl и boost, или ты (без их помощи). Право выбора оружия, тьфу, т. е. задачи предоставляется тебе. Итоговое сравнение будем проводить по критериям:
1. Размер полученного исходного текста.
2. Размер полученного испольняемого кода.
3. Скорость работы полученного результата.
4. Суммарное время, потраченное на разработку.
Понятно, что последнее будет подсчитать сложнее всего, по этому этот показатель можно заменить косвенным признаком - объемом полученного исходного текста.
Дополнительное условие - никаких copy-paste из имеющихся заготовок. Т. е. если что-то дописывается "свое", то оно пишется "с нуля".

Эта тема была разделена из темы "Java vs VC++"

M

Эстафета была подхвачена Sazabis'ом (сообщение №2), за что ему большущий респект. Помимо задачи и второго участника остается выбрать секундантов и окончательно определиться с критериями победы, ну и... в бой!

Цитата Flex Ferrum @ 19.09.05, 14:38

nvm решил не принимать вызов...

я могу задачку задать кто будет отстаивать силу С/С++ без str/boost поднимайте руки Против Вас будет Flex Ferrum, может быть еще кто то захочет. Но каждый пишет сам! Если есть желающие переносимся в раздел "Чистый С"
Я бы и сам мог попробовать, но к сожелению, уже сильно подсел

Цитата Sazabis @ 19.09.05, 15:09

я могу задачку задать кто будет отстаивать силу С/С++ без str/boost поднимайте руки Против Вас будет Flex Ferrum, может быть еще кто то захочет. Но каждый пишет сам! Если есть желающие переносимся в раздел "Чистый С"
Я бы и сам мог попробовать, но к сожелению, уже сильно подсел

Отлично! Заодно начинем оттачивать регламент дуэлей!

Цитата Sazabis @ 19.09.05, 15:09

Цитата Flex Ferrum @ 19.09.05, 14:38

nvm решил не принимать вызов...

..Я его только что прочитал..

Принимаю.
Хотя это не совсем по существу сделанного утверждения, но тоже вариант.

Пока только нет идей насчет задачи.

Предлагаю задачу

Цитата

Задача. Speed Limits

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


Входные данные

Первая строка входного файла speed.in состоит из трех целых
чисел: N, M, D, где N (2<=N<=150) - количество перекрестков,
пронумерованных от 0 до N-1, M - количество дорог, D - номер
перекрестка, в который Вы направляетесь.

Каждая из следующих M строк входного файла описывает одну
дорогу. Каждая строка состоит из четырех целых чисел A (0<=A<N),
B (0<=B<N), V (0<=V<=500), L (1<=L<=500), указывающих, что дорога
ведет из A в B, имеет ограничитель скорости V и длину L. Если V
равно 0, это означает, что знак ограничителя скорости на этой дороге
отсутствует (пропущен). Время перемещения по этой дороге равно
T = L / V, если V<>0, иначе T = L / Vold, где Vold - ограничитель
скорости, использованный последним, прежде чем Вы прибыли на этот
перекресток. Заметим, что деление нужно осуществлять вещественное,
чтобы избежать неправильных округлений. В начале пути Вы
находитесь на перекрестке 0, и текущая скорость равна 70.


Выходные данные

Выходной файл должен содержать одну строку целых чисел,
описывающих номера перекрестков в порядке посещения на самом быстром
маршруте из перекрестка 0 в перекресток D, начиная с 0 и заканчивая
D. Гарантируется единственность такого маршрута для всех тестовых
файлов.


Пример

speed.in speed.out
6 15 1 0 5 2 3 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40

как раз, надо писать граф и все такое

Задача выглядит сильно не в пользу stl
(чистый перебор с минимальным использованием простых контейнеров).

Добавлено 20.09.05, 07:53
Мне задача нравится: большое число мелких объектов в динамической памяти - как раз то, где можно без особых усилий соптимизировать.

Цитата nvm @ 20.09.05, 07:33

Задача выглядит сильно не в пользу stl
(чистый перебор с минимальным использованием простых контейнеров).

обычная олимпиадная задачка. Согласен ?
Flex Ferrum, Согласен ?

тогда погнали...

ЗЫ. Данные не сортированы, в добавок у boost есть "мифический" graph, может его сюда Flex Ferrum, забабашит В добавок, nvm, тебе нельзя будет использовать даже vector. Поэтому перед решением задачи придеться писать свое хранилище.

Цитата Sazabis @ 20.09.05, 07:57

Flex Ferrum, Согласен ?

Да. Единственный момент - я сейчас дома несколько безлошадный (питальник в компе погорел), по этому смогу приступить к решению не раньше, чем куплю новый.

Цитата Sazabis @ 20.09.05, 07:57

ЗЫ. Данные не сортированы, в добавок у boost есть "мифический" graph, может его сюда Flex Ferrum, забабашит

Я уже подумал над этим. Кстати, мы не определились с критериями присуждения победы.

Цитата Sazabis @ 20.09.05, 07:57

В добавок, nvm, тебе нельзя будет использовать даже vector. Поэтому перед решением задачи придеться писать свое хранилище.

Я вот не совсем понял. Дуэль же произошла из темы Java vs C++. nvm на чем будет писать - на С++ или на Java? Если на Java, то он пользуется ихними массивами. А если на С++, без stl, без библиотек, то это бред. Ведь ему и вправду придется писать свое хранилище.

Добавлено 20.09.05, 08:33
Сорри, прочитал теперь подпись к теме. Мдя бредово как-то получается.

Я думаю, что критерием будет:

1. открытый код, проведем голосование среди С++ шников, чтобы им было легче понять, поддержать, так что, пишите КРАСИВО. (И понятными сущностями, вот кстати интересно будет увидеть как сюда впишеться boost::graph )
2. Скорость выполнения, на разных компиляторах, VC6, VC7, BorlandBuilder6 со стандартным компилятором. + Еще бы CW, я думаю (что то мне он понравился после тестов trainer)
3. Посмотрим еще на размер экзешника

Цитата Leprecon @ 20.09.05, 08:31

А если на С++, без stl, без библиотек, то это бред. Ведь ему и вправду придется писать свое хранилище.

Читай цитату nvm'a в первом сообщении. С нее все и пошло.

Добавлено 20.09.05, 08:37

Цитата Sazabis @ 20.09.05, 08:35

Скорость выполнения, на разных компиляторах, VC6, VC7, BorlandBuilder6 со стандартным компилятором. + Еще бы CW, я думаю (что то мне он понравился после тестов trainer)

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

Цитата Flex Ferrum @ 20.09.05, 08:35

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

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

Цитата Sazabis @ 20.09.05, 08:45

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

Ок. Буду иметь в виду.

Добавлено 20.09.05, 09:06
Ограничения по памяти будем вводить?

Цитата Sazabis @ 20.09.05, 08:35

Еще бы CW, я думаю (что то мне он понравился после тестов trainer)

Пишите, я откомпилирую.
CW8 совместим с MSVC6, под него у меня собран boost 1.31

Сообщение отредактировано: trainer - 20.09.05, 09:43

Цитата Flex Ferrum @ 20.09.05, 08:48

Ограничения по памяти будем вводить?

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

Цитата 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 Кбайт, скачиваний: 217)

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

Цитата trainer @ 20.09.05, 18:38

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

Под CodeWarior компилить не пробовал - по причине его отсутствия. А VC проглотил и не поперхнулся. Даже варнингом не плюнул.

А если включить ему опцию "ISO C++ Template Parser", то и эту строку:

property_map<Graph, edge_weight_t>::type weights = get(edge_weight, graph);

без typename не воспринимает.

Цитата nvm @ 20.09.05, 16:33

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

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

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

Цитата

0 1 2

Цитата nvm @ 20.09.05, 16:33

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

Цитата

0 1 2

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

Цитата nvm @ 20.09.05, 16:33

Неужели этот алгоритм применим?!

Пока получается, что да. Там цикличность исключается за счет пометки пройденных узлов (массив vertex_colors). Кроме того, глубина поиска уменьшается за счет того, что при первом достижении целевого узла запоминается полученное время (для последующего отбора путей), и если при последующей обработке еще на "полпути" получается время, превышающее ранее зафиксированное, то дальнейшая обработка этого пути прекращается.

Цитата nvm @ 20.09.05, 16:33

ну ты и быстро - еще даже секунданты флажком не махнули

А это что?:

Цитата Sazabis @ 20.09.05, 07:57

тогда погнали...

Добавлено 20.09.05, 21:19

Цитата trainer @ 20.09.05, 18:38

Но по скорости имеет MSVC7.1 в 1.5 раза. Правда, и исполнимый файл во столько же раз больше.

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

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

Цитата nvm @ 20.09.05, 16:33

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

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

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

Цитата

0 1 2

А правильный ответ
0 1 3 1 2,

а во втором примере - 0 1 1 2.

Так что алгоритм, как и ожидалось, неприменим, или требует радикальной модификации.

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

Цитата nvm @ 21.09.05, 04:48

А правильный ответ
0 1 3 1 2,

Гм. А ты прав, однако... Послушаем - что скажет Sazabis.
Впрочем, эту проблему можно достаточно легко решить, если помечать не пройденные узлы, а пройденные ребра.

Цитата nvm @ 21.09.05, 04:48

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

Как и сказано в условии - использую значение последнего "виденного" ограничителя.

Добавлено 21.09.05, 05:06
nvm, обрати внимание:

Цитата Sazabis @ 20.09.05, 06:45

Каждая дорога - односторонняя, соединяет ровно два перекрестка

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

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

-юсртыхэю 21.09.05, 05:22

Цитата Flex Ferrum @ 21.09.05, 04:56

nvm, обрати внимание:

Цитата Sazabis @ 20.09.05, 06:45

Каждая дорога - односторонняя, соединяет ровно два перекрестка

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

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

Хотя .."ровно два перекрестка" - так как дорогу, соединяющую три перекрестка, представить трудно, то наверное имелось в виду как раз отсутствие петель. Но в математическом плане фраза совершенно пустая (т.е. петли не исключает), и за такие формулировки составителей нужно дисквалифицировать.

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

Кроме того, глубина поиска уменьшается за счет того, что при первом достижении целевого узла запоминается полученное время (для последующего отбора путей), и если при последующей обработке еще на "полпути" получается время, превышающее ранее зафиксированное, то дальнейшая обработка этого пути прекращается.

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

Цитата Sazabis @ 21.09.05, 06:42

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

Ты меня, видимо, не совсем правильно понял. Вот смотри. Предположим, есть два возможных пути из А в D: (A B D) и (A C D). Алгоритм первый раз прошел через узел B и, добравшись до D, получил время, положим 10. После этого, идя по второму варианту пути (через C) он уже на узле C получил время 10. Есть ли, в таком случае, смысл продолжать этот путь дальше, если ранее полученное время заведомо никак не улучшится? Расстояния, ведь, ненулевые, а потому за нулевое время их преодолеть никак нельзя.

Добавлено 21.09.05, 07:18
Кстати, нет ли у тебя файликов побольше?

Цитата Sazabis @ 20.09.05, 06:45

Каждая дорога - односторонняя, соединяет ровно два перекрестка

дороги из А в А не будет/(из 1 в 1)/петли

Теперь, что касаеться импровизированого теста, на раскрутку тела. Момент, конечно интересный, НО задача из серии дейкстры, так что, можно сказать, в каждой вершине достаточно побывать 1 раз. Можем внести это в условие, если хотите. Так же, сами подумайте, какого черта ехать набирать скорость в 3 перекресток а потом возвращаться ? У нас же с Вами не космическая программа по разгону спутников по орбите . В тестовых файлах такого не будет.

Цитата Sazabis @ 21.09.05, 07:45

Теперь, что касаеться импровизированого теста, на раскрутку тела. Момент, конечно интересный, НО задача из серии дейкстры, так что, можно сказать, в каждой вершине достаточно побывать 1 раз. Можем внести это в условие, если хотите. Так же, сами подумайте, какого черта ехать набирать скорость в 3 перекресток а потом возвращаться ? У нас же с Вами не космическая программа по разгону спутников по орбите

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

файлики побольше тестируйте.
Flex, проверь свой алгоритм на 2 архиве
Прикреплённый файлtest1.zip (89.22 Кбайт, скачиваний: 159)

2 архив
Прикреплённый файлtest2.zip (69.45 Кбайт, скачиваний: 167)

Цитата Sazabis @ 21.09.05, 07:45

Теперь, что касаеться импровизированого теста, на раскрутку тела. Момент, конечно интересный, НО задача из серии дейкстры, так что, можно сказать, в каждой вершине достаточно побывать 1 раз. Можем внести это в условие, если хотите.

Нехорошо принципиально менять условие задачи через два дня после того, как она сформулирована.

Добавлено 21.09.05, 08:00
Я бы сказал, что менять условие - ни в какие ворота не лезет (когда время потрачено на исходную задачу).
Поэтому либо оставляем прежнее условие, где оптимальное решение может проходить дважды не только через вершину, но и через одну дугу, либо меняем секунданта (вместе с задачей).

Цитата nvm @ 21.09.05, 07:54

Нехорошо принципиально менять условие задачи через два дня после того, как она сформулирована.

я ничего не менял! это ты сам придумал. Я уже сказал, что у меня нет таких тестовых данных, чтобы проверять кольца. Однако ресурсоемкость очень возрастет, так что, если хотите, можете включить в тесты свой вариант, и фиксить кольца. Только ОБА либо фиксят кольца, либо не фиксят. Выбирайте сами, я на Вас не давлю.

Цитата Sazabis @ 21.09.05, 08:23

Только ОБА либо фиксят кольца, либо не фиксят. Выбирайте сами, я на Вас не давлю.

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

Предлагаю вспомнить, как проходили задачи в C/C++: есть условие, есть автор условия. Если есть уточняющие задачу вопросы - спрашивайте. Вопросов нет - поехали.

Поиск оптимального алгоритма в какой-то степени важен, ИМХО. Вот посмотрел код Flex Ferrum'a что то с трудом идет
много чего не понятно, а в частности, как это вообще работает

Цитата Sazabis @ 21.09.05, 08:48

много чего не понятно, а в частности, как это вообще работает

Комментарии добавить?

Цитата Flex Ferrum @ 21.09.05, 08:55

Комментарии добавить?

конечно. Желательно еще обосновать выбор. Почему например используеться list а не stack(deque) ? а как вообще с тестами которые я выложил, работает верно ?

Цитата Flex Ferrum @ 21.09.05, 08:25

Я ссылок на возможность присутствия колец в условии задачи не нашел.

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

Цитата

Мне кажется (что по этому поводу думают остальные?), что детали наподобия колец и возможности возврата в данном случае не существенны.

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

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

Прицепи экзешник - попробую найти контрпример без циклов.

Цитата nvm @ 21.09.05, 13:12

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

Совершенно необязательно. Как правильно скзал trainer, если текст задания недоконца ясен - неясные моменты уточняют вопросами. В нашем случае на вопрос "обрабатывать ли кольца" и "обрабатывать ли возвраты" был получен ответ - "нет, не надо".

Цитата Flex Ferrum @ 21.09.05, 14:23

Цитата nvm @ 21.09.05, 13:12

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

Совершенно необязательно. Как правильно скзал trainer, если текст задания недоконца ясен - неясные моменты уточняют вопросами. В нашем случае на вопрос "обрабатывать ли кольца" и "обрабатывать ли возвраты" был получен ответ - "нет, не надо".

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

Текст задачи вполне ясен, и из него следует, что кольца допускаются.

Здесь невозможны другие трактовки.

Сообщение отредактировано: nvm - 21.09.05, 15:14

Цитата nvm @ 21.09.05, 15:07

Текст задачи вполне ясен, и из него следует, что кольца допускаются.

Из какой фразы это следует?

Цитата Flex Ferrum @ 21.09.05, 15:10

Цитата nvm @ 21.09.05, 15:07

Текст задачи вполне ясен, и из него следует, что кольца допускаются.

Из какой фразы это следует?

Из отсутствия обратного утверждения.

Цитата nvm @ 21.09.05, 13:12

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

Ограничения - вещь относительная. Например, ограничение скорости в 100 км/ч - это снизу или сверху?
Если не уточнил - будь уверен, ситуацию истолкуют не в твою пользу. Суровая правда жизни.

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

Цитата nvm @ 21.09.05, 15:15

Из отсутствия обратного утверждения.

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

Добавлено 21.09.05, 15:19

Цитата nvm @ 21.09.05, 15:16

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

nvm, извини, ты слишком сильно заморочился. По твоей логике задачу "напишите мне программу, выводящую на экран строку "Hello World!"" надо начинать с разработки собственной ОС. Ибо в задаче не сказано обратного.

Добавлено 21.09.05, 15:26

Цитата Sazabis @ 21.09.05, 09:09

а как вообще с тестами которые я выложил, работает верно

Верно то оно верно, только вот speed4.in колбасила 10598406 msecs - почти 3 часа (правда, надо учесть, что с приоритетом "Low", т. к. паралельно и другими делами компьютер приходилось занимать). На ночь запущу speed8.in, а покуда подумаю над оптимизацией и сужением пространства поиска. Блин, ну нельзя так - задача превратилась в чисто алгоритмическую .

Цитата Flex Ferrum @ 21.09.05, 15:17

Добавлено 21.09.05, 15:19

Цитата nvm @ 21.09.05, 15:16

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

nvm, извини, ты слишком сильно заморочился. По твоей логике задачу "напишите мне программу, выводящую на экран строку "Hello World!"" надо начинать с разработки собственной ОС. Ибо в задаче не сказано обратного.

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

Если в ТЗ сказано напечатать целые числа от 0 до 10, а заказчик, оказывается, имел в виду только четные - он должен принять работу, так как это доп. ограничение он в ТЗ не вписывал.

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

Цитата nvm @ 21.09.05, 15:29

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

Никто не мешает использовать дополнительные знания о предметной области. Нам с тобой известно, что в тестовых файлах будут графы без колец и возвратов. Так зачем усложнять себе жизнь?

Добавлено 21.09.05, 15:34

Цитата nvm @ 21.09.05, 15:29

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

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

Цитата nvm @ 21.09.05, 15:29

Если в ТЗ сказано напечатать целые числа от 0 до 10, а заказчик, оказывается, имел в виду только четные - он должен принять работу, так как это доп. ограничение он в ТЗ не вписывал.

Это ты перегибаешь. Заказчик хочет, чтобы были целые числа от 0 до 10, но не оговорил последовательность, то он может взять твою работу, а может и не взять, т.к. ему надо в виде 10-9-..-1-0. Для него это естественно, а для тебя - ограничение.

В общем, фальстарт получился

Цитата trainer @ 21.09.05, 16:53

Это ты перегибаешь. Заказчик хочет, чтобы были целые числа от 0 до 10, но не оговорил последовательность, то он может взять твою работу, а может и не взять, т.к. ему надо в виде 10-9-..-1-0. Для него это естественно, а для тебя - ограничение.

Если ему нужен обратный порядок - то это с доплатой, как и за все, что не отражено в ТЗ.

Цитата

В общем, фальстарт получился

Ну нет, вот решение (грубое и без оптимизации).

..Только, скорее всего, техническая оптимизация здесь даст малый эффект по сравнению с алгоритмической.

Добавлено 21.09.05, 17:26
На примерах с циклами алгоритм правильно находит скорейший путь, правда, не выводит его полностью (только до пересечения) - небольшой баг.

Добавлено 21.09.05, 17:36
Если добавить printf:

bool GraphNode::draw_path(const GraphNode* next, double speed, double time)
{
...
        m_next=next;
        printf("%i ",m_id);
        return true;
...
}

то будет выводить правильный путь на консоль.

-юсртыхэю 21.09.05, 17:44

Цитата Flex Ferrum @ 21.09.05, 15:17

только вот speed4.in колбасила 10598406 msecs - почти 3 часа

Так сделай не 10000 повторов, а меньше..
Прикреплённый файлMinTime.rar (4.62 Кбайт, скачиваний: 157)

..Баг с неточным восстановлением пути остался, но будет исправлен. Минимальное время вычисляется точно.

Цитата nvm @ 21.09.05, 17:15

только вот speed4.in колбасила 10598406 msecs - почти 3 часа

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

Добавлено 22.09.05, 07:43
по индивидульной программе

Цитата Sazabis @ 22.09.05, 07:42

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

Ок. Буду иметь в виду.

Цитата Sazabis @ 22.09.05, 07:42

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

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

Поэтому очень спорный вопрос, что здесь правильно.
Может статься, полиномиального алгоритма не существует, даже при ограничении на самопересечения траектории.

Цитата nvm @ 22.09.05, 10:37

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

А может говорить о том, что исполнитель задачи слишком заморачиваться...

..Кстати, в условии сказано (1<=L<=500), а в тестах есть L=0.

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

Сообщение отредактировано: nvm - 23.09.05, 10:08

Прикреплённый файлMinTime.rar (5.15 Кбайт, скачиваний: 160)

Цитата nvm @ 22.09.05, 11:14

..Кстати, в условии сказано (1<=L<=500), а в тестах есть L=0.

Тебе условие дано, тесты это для упрощения, чтобы не заморачиваться созданием графов самому. Не понравился, тест не используй. Я посмотрел, там только в одном? эта "бага" Я думаю на алгоритм не повлияет.

Добавлено 22.09.05, 13:25
nvm, если в одном цикле объявил переменную, а в следующем используешь переменную с тем же именем, то борланд ругаеться. Объявляй их в каждом цикле, или до цикла.

Цитата Sazabis @ 22.09.05, 12:52

nvm, если в одном цикле объявил переменную, а в следующем используешь переменную с тем же именем, то борланд ругаеться. Объявляй их в каждом цикле,

Тогда VC6 не примет.

Цитата

или до цикла.

Пожалуй, это лучший выход. Где не забуду, буду придерживаться.

Добавлено 22.09.05, 13:44
Да, долго считает, на 9-й задаче уже полтора часа..

Зато какой простой алгоритм:

static double precision=1E-10;
bool GraphNode::find_solution(const GraphNode::Stat* parent, double speed, double time)
{
  for (Stat* s=m_Stats; s; s=s->next) if (s->speed>=speed-precision && s->time<=time+precision) return true; // Pareto
  m_Stats=new Stat(m_Stats,*this,parent,speed,time);
  for (Arc* a=m_Arcs; a; a=a->next){
    const double new_speed=a->speed>precision?a->speed:speed;
    if (new_speed<precision) throw("GraphNode::find_solution");
    if (!a->end.find_solution(m_Stats,new_speed,time+a->distance/new_speed)) return false;
    }
  return true;
}

- Эта функция находит быстрейшие (возможно, циклические) пути ко всем вершинам.

и вынеси дебаг из релиза, к чему столько файлов speed.log /speed.cmp.

на 5 задачке какой то цикл нашел, по времени одентичен оптимальному, а вот по пути.... Ты что, петли будешь фиксить ?

после 5 теста, твоя игрушка накрываеться )), не знаю сколько ей время нужно на поиск.
память плавно растет, но кодГвард вроде не ругаеться. в конце видать аккуратно чистишь, но в процессе

Моя игрушка загнулась на 7-ом. Над чем-то думала 14 часов, после чего я ее срубил. А до этого результаты такие:
1. 0 1 4 3
Working time: 0 msecs.
2. 0 8 3 1
Working time: 0 msecs.
3. 0 18 1
Working time: 16 msecs.
4. 0 1 2 6 10 14 17 20 25 30 35 39 41 45 48 52 57 62 66 70 74 78 81 86 90 94 99
Working time: 3428797 msecs.
5. 0 12 5 14 15 27 26 29 30 41 40 38 44 45 58 49 54 59 60 73 74 75 89
Working time: 14953 msecs.
6. 0 53 16 35 40 1
Working time: 3110 msecs.

Цитата nvm @ 22.09.05, 13:37

m_Stats=new Stat(m_Stats,*this,parent,speed,time);

может где то в глубине твоих классов ты и убиваешь это, но явно не понятно где

Цитата Sazabis @ 22.09.05, 13:53

Цитата nvm @ 22.09.05, 13:37

m_Stats=new Stat(m_Stats,*this,parent,speed,time);

может где то в глубине твоих классов ты и убиваешь это, но явно не понятно где

В деструкторе, конечно.

Расход памяти умышлен и оправдан - это сокращает перебор.

-юсртыхэю 22.09.05, 14:26

Цитата Sazabis @ 22.09.05, 13:49

на 5 задачке какой то цикл нашел, по времени одентичен оптимальному, а вот по пути....

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

Цитата

Ты что, петли будешь фиксить ?

Нет.
Если оптимальный путь содержит петли, то он уже и так находится.

Добавлено 22.09.05, 15:10
9-й пример все же досчитался (2,5 часа).
Быстрейшее время: best_time=1.20745 (last_speed=413).
Но с путем опять проблемы.

Сообщение отредактировано: nvm - 22.09.05, 16:19

Нашел ошибку:

bool GraphNode::find_solution(const GraphNode::Stat* parent, double speed, double time)
{
  if (parent && parent->time>time+precision) throw("GraphNode::find_solution");
  for (Stat* s=m_Stats; s; s=s->next) if (s->speed>=speed-precision && s->time<=time+precision) return true; // Pareto
  m_Stats=new Stat(m_Stats,*this,parent,speed,time);
  Stat* new_parent=m_Stats; // avoid recursive spoiling
  for (Arc* a=m_Arcs; a; a=a->next){
    const double new_speed=a->speed>precision?a->speed:speed;
    if (new_speed<precision) throw("GraphNode::find_solution");
    if (!a->end.find_solution(new_parent,new_speed,time+a->distance/new_speed)) return false;
    }
  return true;
}

- Теперь работает правильно.

Добавлено 22.09.05, 15:53
Sazabis, а у тебя есть "эталонный" алгоритм решения задачи (тот, который использовался при просчете тестов) ?

Добавлено 22.09.05, 16:18
Пример 7 просчитала за пол-часа, траектория правильная.

Добавлено 22.09.05, 16:21
Flex Ferrum, ты, наверное, жестко ограничиваешь использование памяти?

Цитата nvm @ 22.09.05, 15:41

Flex Ferrum, ты, наверное, жестко ограничиваешь использование памяти?

Да. Пока что память используется по минимуму. Но это ненадолго.

Цитата Flex Ferrum @ 22.09.05, 16:46

Цитата nvm @ 22.09.05, 15:41

Flex Ferrum, ты, наверное, жестко ограничиваешь использование памяти?

Да. Пока что память используется по минимуму. Но это ненадолго.

Ничего, я тоже оставил резерв для будущей оптимизации

Добавлено 22.09.05, 17:21
А ты усложнения внес только, чтобы ловить циклы, или обнаружил, что алгортм Дейкстры в непосредственном виде неприменим и без циклов?

Добавлено 22.09.05, 17:49
Вроде бы Дейкстра не должен сработать на таком примере:
6 6 5
0 1 110 120
0 2 100 100
1 3 0 120
2 3 0 100
3 4 0 150
4 5 0 150

Цитата nvm @ 22.09.05, 17:03

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

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

Цитата Flex Ferrum @ 22.09.05, 20:40

Таким образом получается, что вектор минимальных "расстояний" в чистом виде не применим, а вместе с ним и весь Дейкстра.

Ну это вы загнули. Просто тут в качестве метки вершины надо использовать не метку (был/небыл) а пару (время/скорость) и, как я подумал по дороге на работу, еще и метку "проехал" или нет. Тоесть если добавить метку "уже проехал" помимо (время/скорость), то НЕ получим фиксирование циклов, а если эту метку убрать, то получим нахождение с учетом "разгонных" циклов.

Цитата nvm @ 22.09.05, 15:41

Sazabis, а у тебя есть "эталонный" алгоритм решения задачи (тот, который использовался при просчете тестов) ?

эталона нету, могу положить свой .exe, без кода, так как он ужасен )) , я писал на время. Если в выходные будет время подредактирую выложу код.

смотрите на время и память.
Прикреплённый файлl9porshe.rar (103.44 Кбайт, скачиваний: 167)

Цитата Sazabis @ 23.09.05, 07:06

Просто тут в качестве метки вершины надо использовать не метку (был/небыл) а пару (время/скорость) и, как я подумал по дороге на работу, еще и метку "проехал" или нет. Тоесть если добавить метку "уже проехал" помимо (время/скорость), то НЕ получим фиксирование циклов, а если эту метку убрать, то получим нахождение с учетом "разгонных" циклов.

Я пришел к аналогичному выводу. Но квадратичной сложности все равно не получится, ибо если мы входим на перекресток с большей скоростью, то мы обязаны обойти все дуги с 0-ой меткой скорости.

Цитата Flex Ferrum @ 22.09.05, 20:40

Посуди сам. Алгоритм Дейкстры основан на том предположении, что веса ребер и дуг фиксированы, а потому мы действительно можем уложиться во время O(n²).

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

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

-юсртыхэю 23.09.05, 09:58

Цитата Sazabis @ 23.09.05, 07:06

.. без кода, так как он ужасен ))

Не стесняйся - все свои
..Екзешник в 300кб - это тоже ужасно (в данном случае).

-юсртыхэю 23.09.05, 10:16

Цитата Flex Ferrum @ 23.09.05, 07:49

Я пришел к аналогичному выводу. Но квадратичной сложности все равно не получится, ибо если мы входим на перекресток с большей скоростью, то мы обязаны обойти все дуги с 0-ой меткой скорости.

Если комбинировать идею Дейкстры с ограниченным перебором, то, наверное, можно сильно ускорить поиск, но алгоритм получается сильно "развесистый".
..Как-то лень связываться с алгоритмической оптимизацией, но если напишешь более быстрый вариант, то и мне придется.

Сообщение отредактировано: nvm - 23.09.05, 10:16

Цитата nvm @ 23.09.05, 09:34

Екзешник в 300кб - это тоже ужасно (в данном случае).

оттуда можно много выкинуть к тому же это вроде дебаг сборка

Добавлено 23.09.05, 10:21

Цитата nvm @ 23.09.05, 09:34

Если комбинировать идею Дейкстры с ограниченным перебором, то, наверное, можно сильно ускорить поиск, но алгоритм получается сильно "развесистый".

блин сделайте сортировку, ( вроде ее у вас не видно ) Ничего там развесистого нету.

Добавлено 23.09.05, 10:23
у nvm выделение памяти через new прямо в рекурсивном цикле, нельзя было за ранее чтоли продумать. Там столько вызовов этой процедуры на большом графе.

Цитата Sazabis @ 23.09.05, 07:06

Ну это вы загнули. Просто тут в качестве метки вершины надо использовать не метку (был/небыл) а пару (время/скорость)

Да даже если и так - по каким криетриям сравнивать эту пару? По каким критериям выбирать очередной узел (если использовать идею Дейкстры)? По минимальному времени? По максимальной скорости?

Добавлено 23.09.05, 10:35

Цитата Sazabis @ 23.09.05, 10:17

блин сделайте сортировку, ( вроде ее у вас не видно ) Ничего там развесистого нету.

Сделал. И что? 0-ые дуги помещаются вначало (отсортированные по расстоянию), помеченные - в конец.

Цитата Sazabis @ 23.09.05, 10:17

блин сделайте сортировку, ( вроде ее у вас не видно ) Ничего там развесистого нету.

Пока мой алгоритм быстрее, чем у Flex Ferrum-а, нет стимула модернизировать.

Цитата

у nvm выделение памяти через new прямо в рекурсивном цикле, нельзя было за ранее чтоли продумать. Там столько вызовов этой процедуры на большом графе.

Выделение памяти обычно первый кандидат на оптимизацию (тем более, когда 100Мб выделяются кусочками по 30б), но пока, как ни странно, не это узкое место (скорость приращения используемой программой памяти существенно падает со временем, что означает, что не в памяти дело).

Цитата Flex Ferrum @ 23.09.05, 10:33

Сделал. И что? 0-ые дуги помещаются вначало (отсортированные по расстоянию), помеченные - в конец.

имхо, сортировка ветвей должна быть по времени при попадании в узел. А не один раз в начале. Это же эвристический показатель крутости ветви. Он постоянно меняеться в зависимости от того, когда вы пришли в узел. Двигаясь сразу по наиболее быстрой траектории мы получаем давольно сностное время прохождения, которое потом нам поможет отсеить большенство ветвей еще на середине прохождения. Можно сортировать по скорости, опять таки при попадании в узел. На разных задачках эти два подхода обратно пропорциональны. Можно конечно коэфициэнт крутости взять исходя из скорости (некий знак, +,* ...) времени прохождения.
Но если сортировать по времени, по на больших графах получаете выйгрыш при выходе из цикла по первому достижению макс времени, без сортировки вам приходиться проверять весь граф.
Не считаю ЭТО алгоритмической трудностью, это естественный подход для решения подобной задачи. Надо еще заметить, что я был в курсе, что придеться сортировку реализовывать

Сообщение отредактировано: Sazabis - 23.09.05, 11:07

Новая версия программы для демонстрации бесполезности stl+boost.
Время работы на всех задачах меньше секунды.
Код не до конца причесан, но бывает хуже.
Прикреплённый файлMinTime.rar (5.67 Кбайт, скачиваний: 186)

вот это уже заявка на победу. Ждемсъ Flex Ferrum.

а, nvm, причеши пока свой код, и пояснения к алгоритму напиши, а то крыша едет.

Цитата Sazabis @ 23.09.05, 14:29

Ждемсъ Flex Ferrum.

Блин. У меня засада - не могу догнать идею алгоритма.

Цитата Sazabis @ 23.09.05, 14:29

а, nvm, причеши пока свой код, и пояснения к алгоритму напиши, а то крыша едет.

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

..Свой вариант все же тоже выложи.

Фуф. Ну все. Завтра покупаю себе питальник (в комп), и наконец-то добью задачу.

хм... Ну так что ? Наичистейший С++ победил ?

Цитата Sazabis @ 21.10.05, 09:39

хм... Ну так что ? Наичистейший С++ победил ?

Я же написал чуть выше -

Цитата Flex Ferrum @ 23.09.05, 14:53

Блин. У меня засада - не могу догнать идею алгоритма.

Т. е. у меня проблема в идее алгоритма, а не в его реализации. Мало я с графами работал.
Сравнивал работу моего варианта и варианта nvm'а - не могу догнать, за счет чего nvm'овский вариант настолько сужает пространство поиска. Короче, засада

Могу поступить, гм, таким образом - взять nvm'овский вариант и один-в-один переложить его на STL+boost. Вопрос - будет ли это засчитано как решение .

Цитата Flex Ferrum @ 21.10.05, 09:45

Могу поступить, гм, таким образом - взять nvm'овский вариант и один-в-один переложить его на STL+boost. Вопрос - будет ли это засчитано как решение .

Flex Ferrum, nvm, напишите, ваши алгоритмы в псевдо коде или лучше словами. Так как функция, имхо, рекурсивная то получиться не много. Посмотрим и сразу все видно будет. А один в один перекладывать, имхо, будет нечестно. nvm писал выше, что алгоритм рабочий, но "причесывать" его он не стал, если ты переложишь его алгоритм, то как бы "причешишь" код и твой будет лучше.