Форум на Исходниках.RU

Первая дуэль.

Sazabis — Mon, 24 Oct 2005 06:56:41 +0000

Sazabis:

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

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

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

Первая дуэль.

Flex Ferrum — Fri, 21 Oct 2005 09:45:33 +0000

Flex Ferrum:

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

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

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

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

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

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

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

Первая дуэль.

Sazabis — Fri, 21 Oct 2005 09:39:59 +0000

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

Первая дуэль.

Flex Ferrum — Fri, 30 Sep 2005 14:17:14 +0000

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

Первая дуэль.

nvm — Fri, 23 Sep 2005 16:45:00 +0000

nvm:

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

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

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

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

Первая дуэль.

Flex Ferrum — Fri, 23 Sep 2005 14:53:53 +0000

Flex Ferrum:

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

Ждемсъ Flex Ferrum.

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

Первая дуэль.

Sazabis — Fri, 23 Sep 2005 14:29:59 +0000

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

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

Первая дуэль.

nvm — Fri, 23 Sep 2005 13:46:51 +0000

nvm: Новая версия программы для демонстрации бесполезности stl+boost.
Время работы на всех задачах меньше секунды.
Код не до конца причесан, но бывает хуже.

Первая дуэль.

Sazabis — Fri, 23 Sep 2005 11:05:57 +0000

Sazabis:

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

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

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

Первая дуэль.

nvm — Fri, 23 Sep 2005 10:55:02 +0000

nvm:

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

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

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

Цитата

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

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

Первая дуэль.

Flex Ferrum — Fri, 23 Sep 2005 10:33:02 +0000

Flex Ferrum:

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

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

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

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

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

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

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

Первая дуэль.

Sazabis — Fri, 23 Sep 2005 10:17:35 +0000

Sazabis:

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

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

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

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

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

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

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

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

Первая дуэль.

nvm — Fri, 23 Sep 2005 09:34:00 +0000

nvm:

Цитата 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-ой меткой скорости.

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

Первая дуэль.

Flex Ferrum — Fri, 23 Sep 2005 07:49:45 +0000

Flex Ferrum:

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

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

Первая дуэль.

Sazabis — Fri, 23 Sep 2005 07:10:04 +0000

Sazabis: смотрите на время и память.

Первая дуэль.

Sazabis — Fri, 23 Sep 2005 07:06:21 +0000

Sazabis:

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

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

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

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

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

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

Первая дуэль.

Flex Ferrum — Thu, 22 Sep 2005 20:40:51 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

nvm — Thu, 22 Sep 2005 17:03:09 +0000

nvm:

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

Первая дуэль.

Flex Ferrum — Thu, 22 Sep 2005 16:46:55 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

nvm — Thu, 22 Sep 2005 15:41:36 +0000

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

Первая дуэль.

nvm — Thu, 22 Sep 2005 14:22:47 +0000

nvm:

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

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

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

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

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

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

-юсртыхэю 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).
Но с путем опять проблемы.

Первая дуэль.

Sazabis — Thu, 22 Sep 2005 13:53:39 +0000

Sazabis:

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

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

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

Первая дуэль.

Flex Ferrum — Thu, 22 Sep 2005 13:53:35 +0000

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 — Thu, 22 Sep 2005 13:49:20 +0000

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

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

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

Первая дуэль.

nvm — Thu, 22 Sep 2005 13:37:36 +0000

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 — Thu, 22 Sep 2005 12:52:19 +0000

Sazabis:

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

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

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

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

Первая дуэль.

nvm — Thu, 22 Sep 2005 11:57:56 +0000

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

Первая дуэль.

nvm — Thu, 22 Sep 2005 11:14:58 +0000

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

Первая дуэль.

Flex Ferrum — Thu, 22 Sep 2005 10:45:06 +0000

Flex Ferrum:

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

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

Первая дуэль.

nvm — Thu, 22 Sep 2005 10:37:36 +0000

nvm:

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

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

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

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

Первая дуэль.

Flex Ferrum — Thu, 22 Sep 2005 07:49:39 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

Sazabis — Thu, 22 Sep 2005 07:42:34 +0000

Sazabis:

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

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

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 18:42:14 +0000

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 17:15:27 +0000

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 повторов, а меньше..

Первая дуэль.

trainer — Wed, 21 Sep 2005 16:53:39 +0000

trainer:

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

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

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 15:32:27 +0000

Flex Ferrum:

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

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

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

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

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

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 15:29:45 +0000

nvm:

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

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

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

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

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

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

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

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

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 15:17:27 +0000

Flex Ferrum:

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

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

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

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

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

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

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 15:16:53 +0000

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

Первая дуэль.

trainer — Wed, 21 Sep 2005 15:16:24 +0000

trainer:

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

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 15:15:18 +0000

nvm:

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

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

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

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

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

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 15:10:17 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 15:07:37 +0000

nvm:

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

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

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

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

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

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

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

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 14:23:04 +0000

Flex Ferrum:

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 13:12:47 +0000

nvm:

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

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

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

Цитата

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

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

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

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

Первая дуэль.

Sazabis — Wed, 21 Sep 2005 09:09:15 +0000

Sazabis:

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

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

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

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 08:55:02 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

Sazabis — Wed, 21 Sep 2005 08:48:42 +0000

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

Первая дуэль.

trainer — Wed, 21 Sep 2005 08:30:58 +0000

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

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 08:25:13 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

Sazabis — Wed, 21 Sep 2005 08:23:18 +0000

Sazabis:

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

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 07:54:44 +0000

nvm:

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

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

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

Первая дуэль.

Sazabis — Wed, 21 Sep 2005 07:51:38 +0000

Sazabis: 2 архив

Первая дуэль.

Sazabis — Wed, 21 Sep 2005 07:51:00 +0000

Sazabis: файлики побольше ;) тестируйте.
Flex, проверь свой алгоритм на 2 архиве

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 07:48:41 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

Sazabis — Wed, 21 Sep 2005 07:45:10 +0000

Sazabis:

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

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

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

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

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 06:47:45 +0000

Flex Ferrum:

Цитата 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 — Wed, 21 Sep 2005 06:42:04 +0000

Sazabis:

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 05:08:52 +0000

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

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

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

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

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

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

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

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

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

Первая дуэль.

Flex Ferrum — Wed, 21 Sep 2005 04:56:15 +0000

Flex Ferrum:

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

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

Первая дуэль.

nvm — Wed, 21 Sep 2005 04:48:58 +0000

nvm:

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

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

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

Первая дуэль.

Flex Ferrum — Tue, 20 Sep 2005 20:46:07 +0000

Flex Ferrum:

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

тогда погнали... 8-)

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

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

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

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

Первая дуэль.

trainer — Tue, 20 Sep 2005 19:19:10 +0000

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

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

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

Первая дуэль.

Flex Ferrum — Tue, 20 Sep 2005 19:16:36 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

trainer — Tue, 20 Sep 2005 18:38:50 +0000

trainer: Флекс, 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 стоит для побаловаться. :D Надо на него переходить. :)

Первая дуэль.

nvm — Tue, 20 Sep 2005 16:33:42 +0000

nvm:

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

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

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

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

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

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

Добавлено 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

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

Первая дуэль.

Flex Ferrum — Tue, 20 Sep 2005 16:01:27 +0000

Flex Ferrum: Yes!

Цитата

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

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

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

PS: Исходный текст буквально с колес, пока что особо не причесывал. Компилилось на VC 7.1

Первая дуэль.

nvm — Tue, 20 Sep 2005 14:59:43 +0000

nvm:

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

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

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

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

Первая дуэль.

Sazabis — Tue, 20 Sep 2005 14:38:10 +0000

Sazabis:

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

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

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

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

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

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

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

Первая дуэль.

nvm — Tue, 20 Sep 2005 14:04:29 +0000

nvm:

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

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

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

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

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

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

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

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

Первая дуэль.

Flex Ferrum — Tue, 20 Sep 2005 12:45:36 +0000

Flex Ferrum:

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

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

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

Первая дуэль.

Sazabis — Tue, 20 Sep 2005 12:37:28 +0000

Sazabis:

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

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

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

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

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

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

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

Первая дуэль.

Flex Ferrum — Tue, 20 Sep 2005 12:31:28 +0000

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

Цитата

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 (предыдущий).

Первая дуэль.

Машина — Tue, 20 Sep 2005 12:30:36 +0000

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

Первая дуэль.

Flex Ferrum — Tue, 20 Sep 2005 12:27:07 +0000

Flex Ferrum:

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

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