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

[nvm]

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

[nvm]

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

[Sazabis]

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

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

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

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

[Flex Ferrum]

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

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

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

[nvm]

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

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

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

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

[Flex Ferrum]

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

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

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

[nvm]

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

[nvm]

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

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

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

[Sazabis]

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

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

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

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

[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;
}

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

[Sazabis]

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

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

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

[Flex Ferrum]

Моя игрушка загнулась на 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.

[Sazabis]

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

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

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

[nvm]

Цитата 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

[nvm]

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

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, ты, наверное, жестко ограничиваешь использование памяти?