1 Отредактировано pvkovalev (2012-05-21 06:10:22)

Тема: Место встречи (изменить нельзя)

Доброго времени суток!

Пожалуйста помогите найти какой алгоритм решает следующую задачу.
Даны N точек(координат) в виде  (-1;0) (20;5) ... (3;2)
Задача - найти такую точку, сумма расстояний от которой до всех остальных будет минимальной.

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

Подходит ли для этой задачи алгоритм Алгоритм Форда-Беллмана? Или что-то другое? Буду очень признателен.


Пример: Даны точки (0;1) (2;5) (3;1) (4;0)
Суммы путешействий будут 11, 13, 8 и 10. Минимальной из них это 8. Ответ: 8.

2 Отредактировано Jumbo (2012-05-21 19:32:24)

Re: Место встречи (изменить нельзя)

Причём Форд-Беллман не понятно smile
Могу только заметить, что расстояние между точками i и j это

max(abs(x[i] - x[j]), abs(y[i] - y[j]))

=> для каждой точки можно посчитать сумму расстояний за N и выбрать минимум. 
Быстрее не знаю sad

3

Re: Место встречи (изменить нельзя)

Jumbo пишет:

Причём Форд-Беллман не понятно smile
Могу только заметить, что расстояние между точками i и j это

max(abs(x[i] - x[j]), abs(y[i] - y[j]))

=> для каждой точки можно посчитать сумму расстояний за N и выбрать минимум. 
Быстрее не знаю sad

Да все верно (на счет расстояний). Просто думаю как ускорить этот процесс подсчета... Думал может как-то эту задачу свести к графу и там какой-то алгоритм подойдет.

4

Re: Место встречи (изменить нельзя)

Ну, например, можно повернуть все на 45 градусов и растянуть (а точнее, сделать замену x' = x-y, y' = x+y), тогда метрика станет манхеттенской. Теперь, сумма расстояний раскладывается в 2 суммы: сумма расстояний по иксу и по игреку. Можно отдельно найти эти две величины для каждой точки, а затем сложить. Найдем, например, сумму расстояний по иксам. Для этого отсортируем все точки по их абсциссе и пройдем по этому массиву слева направо. При переходе к следующей точке мы легко можем посчитать, как изменится искомая сумма. Сложность решения O(NlogN).

5

Re: Место встречи (изменить нельзя)

KADR пишет:

Можно отдельно найти эти две величины для каждой точки, а затем сложить.

А нахождение этого расстояния не займет N*N времени? Из каждой точки до каждой точки?
Хотя конечно чуть меньше, но все же

 for (int i = 0; i < N; i++)
            {
                for (int j = i + 1; j < N; j++)
                {
                    double dist = Distance(list[i], list[j]);
                }
            }

Ничего умнее предложить не могу. В этом же и проблема в алгоритмах с графами - для задания веса, все равно считать через это, а потом + сложность вычисления в графе. Не могли бы вы подробнее описать процесс поиска наименьшего пути? Мне все время кажется что это задача нахождения минимального остова, но может я просто зациклился на ней.

6

Re: Место встречи (изменить нельзя)

pvkovalev пишет:

А нахождение этого расстояния не займет N*N времени? Из каждой точки до каждой точки?
Хотя конечно чуть меньше, но все же

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

7

Re: Место встречи (изменить нельзя)

Да, действительно, графы все только усложняют. Буду разбираться дальше.