Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Алгоритмы > Задача с графами

Автор: Grigorill 13.12.2011, 18:32

Здравствуйте очень нужна помощь, с графами столкнулся впервые. Суть такая, есть N вершин, между ними есть ребра (длину ребер мы задаем сами целым числом). По ребрам ездят точки могут ехать в обе стороны. При нахождении 2 точек в одной вершине происходит столкновение, соответственно если точки едут по 1 ребру навстречу друг-другу тоже произойдет столкновение. Движение точек заданы списком вершин через которые они проходят. Скорости точек =1. По достижению конечной вeршины тoчка исчезает. Определить будет ли стoлкновение?
Пишу на C# буду благодарен за любую помощь.

Автор: ksnk 13.12.2011, 18:49

Моделировать с шагом 1/2, чтобы гарантированно определить столкновение навстречу движущихся по грани точек. Или проще тупо увеличить расстояния по вершинам в 2 раза, и считать время моделирование движущимся в 2 раза быстрее.
Каждая грань - пара X,Y - отсортированных по алфавиту(или порядку). Скорость на грани - +-1, в зависимости от того, из какой вершины грани начинаем движение. Таким образом, мгновенное состояние точки записывается как грань и пройденная доля грани. Для определенности ( X-Y:3/5 ) - четыре числа, если приписать длину грани для целочисленности вычислений.
Для всех точек вычисляется мгновенное состояние, совпавшие состояния означают столкновение.
С каждым шагом каждая точка в соответствии со скоростью изменяет пройденную долю до 0 или 1, после чего переводится на другую грань по маршруту движения.

В чем вообще проблемы-то?

Автор: Grigorill 13.12.2011, 21:26

Как реализовать множество точек и вершин? Как для каждой точки задавать маршрут?

Автор: Akina 13.12.2011, 21:45

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

Автор: Grigorill 13.12.2011, 21:58

Двигаются одновременно у всех одна скорость =1.

Автор: ksnk 13.12.2011, 23:19

Цитата(Grigorill @ 13.12.2011, 21:26

)

Как реализовать множество точек и вершин? Как для каждой точки задавать маршрут?

А кто тут задачу задает? smile

Откуда-то взялся граф и маршруты движения?

Для простоты можно считать, что сначала задается граф. В виде координат и символического обозначения точек

Код


a(1,2)-8-b(3,4)-5-c(5,6)-9-d(7,9)-1-a
a-278-c

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

)

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

Автор: Akina 14.12.2011, 08:01

Grigorill, конвертируйте граф в двумерную матрицу, где M(i,j) = номер ребра, на котором находится i-я точка в момент времени j. Если точка находится в вершине - из двух рёбер в матрицу заносится наименьший из них.
Такая матрица легко позволяет найти "коллизии" - одновременное нахождение двух точек на одном ребре. Остаётся проверить столкновение, которое может быть только если они одновременно пришли на это ребро в одну и ту же вершину либо если они пришли на ребро с разных вершин этого ребра. Поскольку скорость = 1 и длины рёбер - целые, то при отсутствии рёбер длины 1 массив можно строить с дискретностью по времени = 1, иначе 0.5.