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

[Flex Ferrum]

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

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

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

[trainer]

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

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

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

[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

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

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

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

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

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

[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]

Цитата 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 не соответствует условиям задачи.

[nvm]

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

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

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

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

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

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

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

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

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

[Sazabis]

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

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

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

[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]

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

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

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

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

[Flex Ferrum]

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

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

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

[Sazabis]

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

[Sazabis]

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

[nvm]

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

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

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

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

[Sazabis]

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

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

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

[Flex Ferrum]

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

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

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