Да, действительно, графы все только усложняют. Буду разбираться дальше.
2 2012-05-23 06:45:21
Re: Место встречи (изменить нельзя) (6 ответов, оставленных в Problems)
Можно отдельно найти эти две величины для каждой точки, а затем сложить.
А нахождение этого расстояния не займет N*N времени? Из каждой точки до каждой точки?
Хотя конечно чуть меньше, но все же
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
double dist = Distance(list[i], list[j]);
}
}
Ничего умнее предложить не могу. В этом же и проблема в алгоритмах с графами - для задания веса, все равно считать через это, а потом + сложность вычисления в графе. Не могли бы вы подробнее описать процесс поиска наименьшего пути? Мне все время кажется что это задача нахождения минимального остова, но может я просто зациклился на ней.
3 2012-05-22 05:13:06
Re: Место встречи (изменить нельзя) (6 ответов, оставленных в Problems)
Причём Форд-Беллман не понятно
Могу только заметить, что расстояние между точками i и j этоmax(abs(x[i] - x[j]), abs(y[i] - y[j]))
=> для каждой точки можно посчитать сумму расстояний за N и выбрать минимум.
Быстрее не знаю
Да все верно (на счет расстояний). Просто думаю как ускорить этот процесс подсчета... Думал может как-то эту задачу свести к графу и там какой-то алгоритм подойдет.
4 2012-05-21 06:07:38
Тема: Место встречи (изменить нельзя) (6 ответов, оставленных в Problems)
Доброго времени суток!
Пожалуйста помогите найти какой алгоритм решает следующую задачу.
Даны N точек(координат) в виде (-1;0) (20;5) ... (3;2)
Задача - найти такую точку, сумма расстояний от которой до всех остальных будет минимальной.
В задаче также указывается что происходит движение по массиву где переход в каждую соседнюю ячейку (в том числе по диагонали) имеет длину 1. Как бы по аналоги с шахматным королем, но мне кажется здесь это не принципиально, хотя может я не прав.
Подходит ли для этой задачи алгоритм Алгоритм Форда-Беллмана? Или что-то другое? Буду очень признателен.
Пример: Даны точки (0;1) (2;5) (3;1) (4;0)
Суммы путешействий будут 11, 13, 8 и 10. Минимальной из них это 8. Ответ: 8.