Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Интересные и занимательные задачи по программированию > Задача на графы

Автор: Codegrammer 21.3.2009, 14:06

Прошу помочь с задачей. Подскажите алгоритм (писать код не надо - если только не по собственно доброй воле). Между N пунктами (N<=50) заданы дороги длиной A(i,j), где I,J-номера пунктов. Дороги проложены на разной высоте и пересекаются только в общих пунктах. В начальный момент времени из заданных пунктов начинают двигаться с постоянной скоростью M роботов (M=2 или 3), независимо меняя направление движения только в пунктах. Роботы управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте(либо в городе, либо на дороге). Скорость I-того робота может быть равна 1 или 2. Остановка роботов запрещена. Написать программу, которая при заданных N,M и сети дорог различной длины (все имеющиеся A(i,j)=разные) определяет минимальное время, через которое может произойти встреча всех M роботов, при этом начальное положение роботов и скорость их движения известны. Примечание: В случае невозможности встречи всех M роботов в одном месте ни в какой момент времени в результате выполнения программы должно быть сформировано соответствующее сообщение. Требование к вводу-выводу: 1) Все входные данные - целые неотрицательные числа; 2) при задании сети дорог должно быть указано количество дорог - K и пункты их начала и конца в виде пар (i,j). Высказывайте все возможные предложения.

Автор: maxdiver 21.3.2009, 20:22

Если я правильно всё понимаю, то задача сводится к такой: для заданных вершин S[i] (i=1..M) и вершины T найти не обязательно простые пути S[i] -> T, такие, что длина каждого i-го пути, делённая на скорость i-го робота (1 или 2), получается одной и той же для всех путей (и наименьшей возможной). Если бы мы заранее знали ещё и длину искомых путей, то можно было бы решать задачу независимо для всех роботов - просто проверить, что для i-го робота найдётся путь такой длины в графе, где все веса рёбер равны либо 1, либо 1/2 (в зависимости от скорости робота - 1 или 2 соответственно). Поэтому я предлагаю искать кратчайшие пути (возможно, не простые) из каждой из вершин S[i] в вершину T, и искать среди них путь одной длины. Процесс этот представляет собой как бы метод движущихся указателей (для каждой из вершин S[i] ищем очередной кратчайший путь, среди найденных M путей удаляем кратчайший, и повторяем всё до тех пор, пока длины всех M путей окажутся одинаковыми). Но решением это назвать довольно трудно - во-первых, для эффективной реализации (а, на мой взгляд, даже если ответ есть, то для него может понадобиться найти до N^M кратчайших путей) потребуется весьма нехилый алгоритм Эппштейна (я в своё время несколько дней понимал его, и потом полдня его писал и ещё день дебужил   ) (этот алгоритм в простейшем (но далеко не простом  ) варианте находит длины K кратчайших путей в графе с N вершинами и M рёбрами за O(M+NlogN+K) ). Во-вторых, если ответа нет, то алгоритм этого никак не заметит, и будет бесконечно долго выуживать кратчайшие пути  Добавлено через 6 минут и 6 секунд Хотя, если предположение (скорее интуитивное) о достаточности N^M путей верно, то неограниченности не будет.

Автор: Codegrammer 21.3.2009, 23:21

maxdiver, я прошу прощения за неясность в условии. Под словами "в одном месте" я понимал либо в городе, либо на дороге. Это сообщение уже отредактировано. Из-за этого ваш алгоритм не подойдет, хотя он довольно интересен.

Автор: maxdiver 21.3.2009, 23:37

А поясните тогда уж и фразу: Цитата Роботы управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте Означает ли это, что мы можем управлять роботами как хотим, или же они всегда ходят по кратчайшим путям? Цитата ваш алгоритм не подойдет Ну ладно, будем думать дальше

Автор: Codegrammer 22.3.2009, 00:08

Цитата(maxdiver @  21.3.2009,  23:37 ) Означает ли это, что мы можем управлять роботами как хотим, или же они всегда ходят по кратчайшим путям? Это означает, что путь до встречи их в одном месте является кратчайшим. Т.е. при меньшем пути они никогда не встретятся в одной точке. Если рассматривать этот же путь, не принимая во внимание других роботов, то вполне может быть, что он и не кратчайший.

Автор: Silent 26.3.2009, 22:07

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

Автор: maxdiver 27.3.2009, 18:01

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

Автор: Codegrammer 27.3.2009, 21:59

В задаче на это ограничения нет. Ну а если бы было, то как динамикой?

Автор: maxdiver 27.3.2009, 23:23

d[i][v][l] - можно ли i-ым роботом прийти в вершину v за время l. если найдётся такое v0 и l0, что d[i][v0][l0] = true для всех i, то можно встретиться в этой вершине. если найдётся такое ребро (a,b) длины len и такое l и такое 0<k<len, что для всех i выполняется: d[i][a][l-k/speed[i]] || d[i][b][l-(len-k)/speed[i]], т.е. они могут встретиться в момент времени l в позиции k на этом ребре, то ответ тоже true. ну понятно, что при больших длинах рёбер это всё будет работать страшно медленно. как считать саму динамику d[i][v][l] - думаю, понятно. пробегаемся по всём рёбрам из v, и если хотя бы по одному из рёбер оказалось d[i][edge_v][l-edge_len] = true, то и d[i][v][l] = true.

Автор: Codegrammer 28.3.2009, 17:44

Цитата(maxdiver @  27.3.2009,  23:23 ) d[i][v][l] - можно ли i-ым роботом прийти в вершину v за время l.если найдётся такое v0 и l0, что d[i][v0][l0] = true для всех i, то можно встретиться в этой вершине.если найдётся такое ребро (a,b) длины len и такое l и такое 0<k<len, что для всех i выполняется: d[i][a][l-k/speed[i]] || d[i][b][l-(len-k)/speed[i]], т.е. они могут встретиться в момент времени l в позиции k на этом ребре, то ответ тоже true.ну понятно, что при больших длинах рёбер это всё будет работать страшно медленно.как считать саму динамику d[i][v][l] - думаю, понятно. пробегаемся по всём рёбрам из v, и если хотя бы по одному из рёбер оказалось d[i][edge_v][l-edge_len] = true, то и d[i][v][l] = true. Довольно интересный подход. Но здесь вы не учитываете, встреча может произойти не обязательно в целочисленный момент времени.

Автор: maxdiver 28.3.2009, 19:21

Ну учитывая, что все скорости равны 1 или 2, то мы все длины можем увеличить в 2 раза, за счёт этого времена прихода роботов в вершины уже станут целыми (ну или просто, ничего не удлиняя, а помня, что все времена - целые или полуцелые). А встречи в серединах рёбер - по моим выкладкам получается, что два робота, если имеют разные скорости, могут встретиться либо в полуцелые, либо в шестьцелые (сам сейчас придумал  ну вида k/6) моменты времени. Я записал уравнение встречи для двух роботов разных скоростей: x + 2y = len (это если с разных концов навстречу идут), или x = 2y (если с одного конца) и всё при условии a+x = b+y. Здесь a и b - времена прихода роботов в вершины-концы рёбер, x и y - времена их движения по ребру. Если мы их разрешим, в первом случае получится вида x=целое/3, во втором - x=целое, и в обоих - y=x+целое/2. Итого y может быть целое/6, и это наихудший случай. Если два робота имеют одинаковую скорость (понятно, нам хуже всего, когда =2), то получаются "четверть-целые" времена в худшем случае  Ну это и интуитивно было понятно, что при таких скоростях все времена будут "не сильно" дробными.

Автор: Codegrammer 29.3.2009, 00:11

Ну кстати, вот это уже дело. Т.е получается берем НОК(4,6)=12. Умножаем ребра на 12. Применяем динамику. Делим t на 12 и все. Классно придумал. Огромное спасибо!!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)