Архив форумов ЦИТФорума

[Aragaer]

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

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

Вот тут и появляется проблема - полное вычисление этого графа занимает в 5-10 раз больше времени, чем собственно поиск пути в нем.

Идея в том, чтобы длины некоторых ребер вычислить заранее и где-то хранить. Длины остальных ребер вычислять по мере необходимости или же допустить некоторую потерю оптимальности маршрута и оставить что есть.

Как я уже сказал, количество вершин очень велико, а потому общее число ребер уже начинает зашкаливать и просто не помещаться в памяти.

Собственно вопрос: как именно можно описать граф (вершины уже описаны, требуется описание ребер), чтобы и считать сравнительно немного и места сэкономить?
_________________
Open your eyes.
And Awaken.

[GREA]

массив вершин - с вещественными координатами x,y.
В массиве ребер - по два int - номера вершин начала и конца + длина ребра. таким образом ты экономишь память, если граф близок к полному.

[Aragaer]

И тем не менее массив ребер имеет величину порядка 2^20 записей. Это все равно слишком много.
_________________
Open your eyes.
And Awaken.

[GREA]

К примеру у нас точки расположены регулярно. Каждую точку окружают 8 других точек (сверху, снизу, справа, слева и по диагоналям). Тогда наличие ребер, связывающее одну вершину с соседними можно описать одним байтом (каждый бит - наличие/отсутствие ребра). Можно исхитриться описать всю структору по 4 бита на каждую вершину, но это очень усложнит обход.
Таким образом вот тебе простейший алгоритм.
Вычисляешь для заданной точки восемь самых близких соседей(остальными ребрами - пренебрегаешь). Упорядочиваешь их по номерам и устанавливаешь биты в чаре так, чтобы впоследствии можно было восстановить структуру связности. 0-нет ребра, 1 - есть ребро.

Внимание! Этот метод даст тебе только емкое описание топологии графа, но не разрешит хранить длины ребер и т.п.
Памяти при этом затратится 2^10, т.е. столько же, сколько и точек в массиве.
Чтобы достичь числа 2^20 придется использовать по два/три байта на вершину. Но это при условии, что граф соединяет только близкие между собой вершины. Для общего случая, алгоритм, разумеется, не применим.

[Aragaer]

Вершины, увы, располежены нерегулярно.
Понятно, что без потерь описать весь граф не получится. А вот с потерями.. Мне например предложили такую идею: разбить все вершины на более-менее тесные кучки по .. условно 16 вершин. Затем в каждой кучке выбрать вершину, наиболее близкую к среднему арифметическому и рассматривать только ее, остальные 15 отбросить.
Для полученных порядка 2^6 вершин уже можно построить полный граф. Когда же потребуется искать маршрут между некоторой парой вершин, сначала выбирается маршрут между центрами кучек, к которым эти вершины относятся, затем строится полный граф на всех тех вершинах, которые попали внутрь областей, через которые прошел первый (приближенный) маршрут. В итоге на описание графа уходит порядка 2^12 записей.

Насчет того, чтобы выбирать для каждой вершины только часть ребер.. Самые ближние ребра тут не годятся. Самые дальние тоже. Какую-то золотую середину определить тоже не получается.
_________________
Open your eyes.
And Awaken.

[GREA]

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

[Aragaer]

Тогда ... попробую. Потом расскажу, как и что получилось.
_________________
Open your eyes.
And Awaken.