sabakka: Все сообщения за 22 Августа 2011 года

sabakka>> Интересно, а найдутся ли желающие здесь.
sabakka>> Присоединяйтесь к нам в Альпах в сентябре Велопробег Милан - Санкт-Мориц - Инсбрук в августе-сентябре
Mishka> Ты там написал, что 200 метров на 5 км. Это общего набора-спуска? Вроде не особо горно, я бы сказал холмисто. В прошлую среду скатались на 35 км с ребятами с общим набором-спуском 550-600 метров, учитавая, что около 30 км по плоскачу, то там было эти 550-600 на 5 км.
Это не общий набор-спуск. Это означает, что профиль пути в указанном месте будет из себя представлять чередующиеся через каждые 5 км подъёмы на 200 м и спуски на 200 м. Но будут также и относительно ровные участки.
/\/\/\-/\/\/\-/\/\/\/\
Общий подъём спуск на 50 км пути может составить 1000-1200 м.

sabakka>> Справились за 1 час 25 минут. Думаю, чот 50 км в день по таким "холмистому" пути будет проехано за 3-4 часа в не очень спешном режиме.
Без опыта много дневным горных велопоходов я свои силы стараюсь оценивать осторожно. К тому же при многодневных походах себе уже нельзя позволить то, что позволяешь себе при однодневных, а именно укатываться за день в хлам.

•  16
•  инфо
•  инструменты
• Ответить на сообщение

Mishka> Блин, мимо пропустил. Неужели совсем образование уплыло в России? Ведь стандартная же задача в курсе дискретной математики (теория графов или терия сетей). И древняя, как Г мамонта. Матрица достижимости — Википедия
Mishka> А алгоритм Уоршала, который не в лоб — тоже древний — 1962 год. Алгоритм Флойда–Уоршелла — Википедия
Так сказано же: требуемая сложность по памяти O(1). Иначе решение получается тривиальным.
Как вы после применения алгоритма Уоршала будете исходную матрицу смежности восстанавливать?
Подсказка: граф ненаправленный.

•  9
•  инфо
•  инструменты
• Ответить на сообщение

sabakka>> Так сказано же: требуемая сложность по памяти O(1). Иначе решение получается тривиальным.
Mishka> О(1) — это константа. Не растёт. Возьми две матрицы. При умножении в лоб умножают матрицу до степени N.
O(1) по памяти означает, что объём используемой алгоритмом доп.памяти не должен зависеть от NUM_VERTICES.
Алгоритм Уоршала позволяет это сделать, но как после заполнения вектора достижимости для требуемой исходной вершины вернуть исходную матрицу смежности? Алгоритм, который портит после себя исходные данные, переданные ему по ссылке, очевидно, не годится.

sabakka>> Подсказка: граф ненаправленный.
Mishka> И что?
Это означает, что исходная матрица смежности содержит избыточную информацию.

•  5
•  инфо
•  инструменты
• Ответить на сообщение

sabakka>> O(1) по памяти означает, что объём используемой алгоритмом доп.памяти не должен зависеть от NUM_VERTICES.
Mishka> У тебя просто представление исходных данных уже не будет, как О(1) в твоём понимании. Поскольку исходные данные.
Не будет. Требование O(1) относится только к доп. памяти.

Mishka> Когда учили, то у нас О(1) было именно статическое размещение (хотя эта метрика официальной не была).
Этого не может быть.

Mishka> Потому, я думаю, что рекурсия запрещена, т.к. это неявное размещение динамическое на стеке.
А тут получается, что рекурсия сама по себе будет нарушать требование O(1) по памяти.

Mishka> Поэтому и можно всё дефайнером определить.
Это нарушение условий задачи.

Mishka> Ты говоришь про вектор достижимости. Понятно, что для одного элемента, это строка/столбец из матрицы достижимости. В твоём понимании, О(1) не получится, если только не гадить в исходные данные.
Гадить можно, но нужно и убрать за собой. Возможно ли это воообще и как это сделать? В этом и вся суть задачи.

Mishka> Можно ещё пойти и путём ленивых вычислений....
Дальше ничего не понял.

Mishka> Ну, нет правда у нас ограничений на количество ввода-вывода. Можно исходную там хранить. Или вывести заранее исходную, а потом строить замыкание.
У нас есть ссылка на матрицу смежности и вектор достижимости, а также индекс начальной вершины всё.

•  3
•  инфо
•  инструменты
• Ответить на сообщение