Не могу решить задачу на графы

[Jilian]

Между N пунктами (N≤50) заданы дороги длиной A(i,j), где i, j - номера пунктов. Дороги проложены на разной высоте и пересекаются только в общих пунктах. В начальный момент времени из заданных пунктов начинают двигаться с постоянной скоростью M роботов (M равно 2 или 3), независимо меняя направление движения только в пунктах. Роботы управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте. Скорость i-го робота может быть равна 1 или 2. Остановка роботов запрещена.

Необходимо

1) при заданных N, M и сети дорог единичной длины определить минимальное время, через которое может произойти встреча всех M роботов; при этом начальное положение роботов и скорость их движения известны.

В случае невозможности встречи всех M роботов в одном месте должно быть сформировано соответствующее сообщение.


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

[Jilian]

Дороги имеют разную длинну, которая задается.

[незваный гость]

Могу предложить только частичную идею, которая (возможно весьма неэффективно) находит точку встречи, если она есть. Идея сродни динамическому программированию, а может, оно и есть -- врать не стану.

Для простоты, считаем что скорости равны 1/2 и 1, а расстояния -- целые. При float расстояниях там сам препод ногу сломит, не только робот.

Еще один момент, кстати, не понятен из Вашего описания. Может ли меняться скорость робота, или это константа, внутренне ему присущая? Я буду исходить из первого предположения.

Итак. Нам понадобятся тройки из $(R, T, \{a_j\})$, где $R$ -- робот, $T$ -- момент времени, а $\{a_j\}$ -- множество мест, где он может находиться. Плюс курсор из троек, представляющих каждого робота на первый необработанный момент времени. Понятное дело, в курсоре в начале (время 0) находятся тройки, задающие начальное положение роботов.

На каждом шаге цикла мы проверяем курсор. Если все моменты времени совпали, и множества точек пересекаются по непустому множеству, мы выдаем положительный ответ, время и останавливаемся (радуясь, что нас не просили сказать, куда идти). Если не нашли, мы выбираем тройку с минимальным временем из курсора (если есть равные, нам все равно, какую), и удаляем ее из коллекции. Для каждой точки из $\{a_j\}$ мы в соответсвии с матрицей и доступными скоростями вычисляем соседние точки и времена прибытия в них (с учетом доступных скоростей). Получаем $(R, T+t_k, \{b_k\})$ -- одноточетную тройку. Теперь, если $(R, T+t_k, x)$ -- существует, добвавляем в него $b_k$, а иначе добавляем нашу новую тройку. Теперь выбираем тройку с наименьшим $t > T$ (для данного робота), и ставим ее в курсор.

Проблема здесь одна. Алгоритм не остановиться сам по себе, когда решений нет. Может статься, что коли граф связный, а роботы двухскоростные, то решение есть всегда. Тогда достаточно проверить, что все роботы в одной области связности. Другой вариант -- попытаться показать, что если решение не найдено за $C(M) \times N$ шагов ($C(M)$ -- некоторая функция от числа роботов), то его не существует. Третий -- попытаться понять, когда решения нет, и научиться идентифицировать такие ситуации.

Все, чем могу...

[Jilian]

Насчет скорости робота, цитирую сама себя

Цитата:

начинают двигаться с постоянной скоростью M роботов (M равно 2 или 3), независимо меняя направление движения только в пунктах.

[незваный гость]

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

[Jilian]

Как я думала, если роботов 2, то делаем им максимальные скорости и смотрим, какое между ними минимальное расстояние (алгорит кратчайшего расстояния между вершинами в графе). А вот если роботов 3...
Нельзя ли найти такое расстояние для 3-х точек?

[незваный гость]

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

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

[Jilian]

незванный гость писал(а):

:evil:
Мне не очень понятно, почему это корректный подход. В некоторых графах прямой (кратчайший) путь может никуда не вести. Например, из-за четности. А вот кривая (имеющая другую четность), может и вывезти. Именно поэтому такой кривой, расточительный, алгоритм выше.

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

Дело в том, что еще дороги разной длинны. Если выбрать путь минимальной длинны и минимального веса между 2-мя роботами, то зная последовательность этих вершин, нетрудно найти время. Но это только для 2-х роботов.
Да, начальная скорость роботов задается, но после первого же пройденного узла её можно поменять

[незваный гость]

Давайте пока остановимся на роботах со скоростью 1 (временно выключим вторую скорость).

Рассмотрите граф с вершинами А и B -- начальные точки роботов. Между ними две дороги A - P1 - P2 - B и A - Q1 - Q2 - Q3 - B. Расстояния между населенными пунктами все равны. То есть кратчайшее расстояние по дороге Px равно 3, Более длинная (Qx) дает 4. Тем не менее, путешествуя по Px они никогда не встретятся (из-за четности), а пойдя обходным путем всретятся через две у.е. времени.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Теперь о скорости. Все таки Вы меня запутали совсем. Верно ли:

1) Каждый робот может двигаться с одной из двух скоростей;

2) В каждом населенном пункте робот может выбрать скорость и направление (дорогу), и следовать этому решению до следующего населенного пункта?

[Jilian]

незванный гость писал(а):

:evil:
Давайте пока остановимся на роботах со скоростью 1 (временно выключим вторую скорость).

Рассмотрите граф с вершинами А и B -- начальные точки роботов. Между ними две дороги A - P1 - P2 - B и A - Q1 - Q2 - Q3 - B. Расстояния между населенными пунктами все равны. То есть кратчайшее расстояние по дороге Px равно 3, Более длинная (Qx) дает 4. Тем не менее, путешествуя по Px они никогда не встретятся (из-за четности), а пойдя обходным путем всретятся через две у.е. времени.

Почему же не встретяться на Рх, они ведь могут встретиться на дороге, не только в узлах.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Теперь о скорости. Все таки Вы меня запутали совсем. Верно ли:

1) Каждый робот может двигаться с одной из двух скоростей;
[/quote]Да, причем скорости менятся в узлах, как ты хочешь.[b]

2) В каждом населенном пункте робот может выбрать скорость и направление (дорогу), и следовать этому решению до следующего населенного пункта?[/quote]Да, это верно

[незваный гость]

Я предполагал, что в качестве места встречи рассматривается только узел. В некотором смысле, дороги A - B и B - A разные (орграф). Как шоссе с разделителем.

Иначе задача для двух роботов тривиальна и не зависит от количества скоростей.

[Jilian]

незванный гость писал(а):

Иначе задача для двух роботов тривиальна и не зависит от количества скоростей.

Так я и пытаюсь Вам об этом сказать -)))
Так мой алгоритм для 2-х роботов (см.выше) Вам нравится?

[незваный гость]

Он работает -- в Ваших условиях. Но я почему-то уверен, что задача предполагает мои условия (встречи только в городах). И Ваш алгорифм не обобщить на больше чем двух роботов.

[Jilian]

У препода спрашивала - можно встречаться где хочешь. Хоть в вершинах, хоть на дороге.

[незваный гость]

ок