xmoonlight, Можно жадно - не надо даже дихотомии и динамики. Отсортируйте все соседние расстояния и сливайте эти 2 соседних числа в один кластер, считая метрику.
В вашем примере сначала объединим 9.5 и 10 (разность 0.5), потом 8 и 8.7 (0.7), потом 8.7 и 9.5 (0.8), потом 5 и 6 (1). При слиянии смотрите отношение текущего расстояния и следующего и минимум его тут 1/2.
Можно даже не сливать по пути, а просто найти все разности, отсортировать, найти пару с максимальным отношением и запомнить большее. Потом все точки, с расстоянием меньше этого числа - объединить в один кластер за еще один проход.
xmoonlight, максимальное расстояние между соседними берется по всем кластерам. Да, в {8, 8.7, 9.5, 10} расстояние 0.8, но есть же еще {5, 6}. Идея в этой метрике - мы смотрим как близко точки бывают в одном кластере и как близко бывают точке вне кластеров. Эти 2 множества должны быть хорошо разделены - в кластрерах точки рядышком, а сами кластеры далеко друг от друга.
Требование иметь хотя бы 2 точки в кластерах не влияет на подсчет метрики, и его нужно включить в алгоритм. Например, во время динамики вы не смотрите на варианты, когда последний кластер состоит из одной точки - и все.
Например в {1, 3, 5, 6, 8, 8.7, 9.5, 10, 12}, если разбить на {1, 3, 5, 6}, {8, 8.7, 9.5, 10}, {12}, то максимальное расстояние в кластере между соседними будет 2 (5-3), а расстояние между кластерами - тоже 2 (8-6 или 12-10). Итого метрика - 2/2=1.
Если разбить {1}, {3}, {5, 6}, {8, 8.7, 9.5, 10}, {12}, то максимальное расстояние между соседними будет 1 (это для каждой точки берем минимум по всем в том же кластере, а потом из этого всего берем максимум). А минимальное расстояние между кластерами будет 2 (тупо минимум по всем парам из разных кластеров). Итого метрика 1/2 лучше. Но тут если количество кластеров не ограничено, то можно вообще каждую точку отдельным кластером сделать и будет 0.
xmoonlight, Нет, непонятно. Может эти числа - это числовое обозначение цвета тома словаря, в котором это слово описывается. То, что зеленый выпал на 11, а красный на 12, и они как бы рядом - просто повезло.
Или вы делаете фильтр мата и эти числа - это какая-то мера матерности слова. В этом случае вам нужно именно 2 кластера.
Еще раз - без физического смысла величины и цели кластеризации - вопросы о корректности и оптимальности кластеризации не имеют смысла.
Magneto903, Нет, достаточно простой двоичной кучи. с Фиббоначиевой там получше ассимптотика чуть чуть, но это имеет смысл делать только если у вас очень много ребер. В вашем же графе это не нужно.
Осталось реализацию дейкстры исправить не с массивом visited самих номеров вершин и линейным поиском в нем, а массив из N пометок 0/1.
Там уже сложность операций в множителе 10 заложена. Попробуйте инкрементировать переменную.
Ну и, 400ms значит, что вы 40% времени будете тратить на эти поиски. Если построение графа в оставшиеся 60% влезает, то вы все успеваете.
Magneto903, javascript - боль. Ну блин, там в дейкстре надо 160 раз пройтись по всем вершинам и выбрать минимум, переписать пару значений в массивах и пройтись по всем ребрам суммарно по одному разу. У вас там что, цикл до 160*160*60*10=15m целую секунду выполнятся будет?
Поищите другую реализацию, без всяких объектов, преобразования к строкам.
Хотя, у меня вообще подозрение, что операция ```visited.includes(node)``` выполняется за линию в shortestDistanceNode. Что там за ```let visited = []``` в которую делается ```visited.push(node)```? это же массив, да? Если вместо этого использовать тупо массив из 160 булов и там помечать обойденность вершины, то будет работать в ~160 раз быстрее. Или на Set заменить хотябы.
Adamos, Вам следует изменить свой ответ, чтобы явно указать. что это будет приближение, а не оптимальный ответ. Не все заглядывают в комменты и ваш ответ в таком виде ошибочен.
Magneto903, Ну вот есть у вас несколько самых далеких вершин от двух красных ботов, по разные стороны от зеленого. куда ему бежать?
Да, кстати, а кто за кем гоняется? у каждого зеленого бота свой красный, или красный гонится за ближайшим зеленым?
Так-то дейкстра на 160 вершинах 60*4 раз в секунду особо не должна нагружать ничего. Тем более, если с кучей делать. Можно в 100 раз больше в секунду успесть сделать на не самом мощном железе. Что-то у вас не так, возможно, в релизации.
Но, попробуйте флойдом на статичном графе. Еще предподсчитайте для каждой вершины самую далекую. Тогда приближение для красных вершин будет перебрать все исходящие ребра, прибавить к ним расстояние до самой далекой в графе и из этих чисел брать максимум. Потом вам надо для каждой зеленой и каждой самой далекой точки найти путь. Опять же, просто для зеленой перебирайте все ребра и берите минимум из длина ребра + длина пути в матрице.
Да, самые далекие точки нужно только статические смотреть.
A* дает неплохой прирост в скорости, когда у вас есть конечная вершина. А тут вам надо найти расстояния от одной до всех, чтобы найти самую далекую точку. Можно второй этап заменить А* вы из самой далекой вершины идете к зеленой.
Но вообще, нужно же всего 2 дейкстры, на самом деле. Одна - найти самую далекую вершину от всех красных. Вторая - нужно найти кратчайшие пути от этой самой далекой до всех вершин графа. И вы сразу нашли пути для всех зеленых.
Можно схалтурить и проннать флойда только для статичных вершин, а потом для поиска самой далекой вершины просто припихать каждую красную к ближайшей соседней статичной вершине. А потом просто перебрать все вершины, посчитать расстояния по матрице флойда и взять максимум.
А для зеленых - нужно просто перебрать все ребра и взять то, путь через которое до конечной наикротчайший.
Этот жадный алгоритм не работает. Тут вообще нет жадности.
вот пример 2 станка, 5 работ {10,9,3,2,2} - ваш алгоритм вернет {{10,2},{9,3,2}}. максимум 14. Хотя можно 3 положить не к 9, а к 10, и получить {{10,3},{9,2,2}} - максимум 13.
То, что вычисления совпали у меня в firefox но не у вас говорит лишь о том, что firefox оптимизирует возведение в целую степень через логарифмы, а chrome - считает через ряды. Custom функция чуть ближе к правде, но все-равно 10-ый знак вычислен не правильно.
Видимо, в хроме менее точно работает возведение в степень. Вернее, с другой ошибкой. Ошибка в 11 знаке для степени почти миллион - выгладит не страшным багом.
float дело такое... Достаточно порядок операций поменять и чуть по другому считать, и уже ошибка в другую сторону получится.
Я бы искал точку для которой максимально расстояние до ближайшего бота. Это делается одной дейкстрой - добавьте в граф новую вершину и ребра длины 0 во всех красных ботов. Потом ищите самую далекую точку от этой новой.
По ботам я бы убегал от самого близкого. Или, опять же, брал всех ботов с коэффициентами обратнопропорциональными квадрату расстояния. Тогда будет сильнее убегать от ближайшего, но и остальные будут немного влиять на решения.
Нет-нет, расстояние не тупо по плоскости а по ребрам графа. Поэтому вам нужно запустить одну дейкстру от красного бота, найти самую далекую вершину, и запустить вторую дейкстру из нее.
Посмотрите на все соседние вершины от зеленого бота. Одни из них ближе к самой далекой вершине и ведут к ней, другие - дальше. Можно ввести что-то типа косинуса - отношение изменения расстояния до самой далекой точки и длины ребра. Так, ребро, лежащее на пути в эту наиудаленнейшую точку будет давать 1. Ребра, ведущие от этой точки будут давать -1. Аналогично можно найти эту метрику относительно вершины в которой красный бот. Это косинус вашего синего угола на графике (-1 для идти от красного бота и +1 для идти на него), если есть прямая видимость.
Надо эти 2 метрики как-то смешать с коэффициентами и брать самое хорошее значение жадно. Коэффициенты берите такого знака, чтобы поощрять движение к самой далекой точке и от красного бота. Кажется, движение от красного бота должно идти с большим коэффициентом. Можно их делать нелинейными - если идем к красному боту, то штраф с большим коэффициентом, чем бонус от ходьбы от бота.
Можно сделать бота ходящего не по вершинам графа. Вот вы нашли путь от красного бота до зеленого и у вас есть входящий вектор - последнее ребро. Еще вы нашли путь от самой дальней точки (для красного бота) до этого же зеленого бота. Опять, есть входящий вектор по последнему ребру - разверните его. Теперь у вас есть 2 вектора - один от красного бота, другой - в самую далекую точку. И вам надо как-то между этими векторами выбирать. Например, складывайте их с разными коэффициентами - вот и будет ваше направление для зеленого бота.
В вашем примере сначала объединим 9.5 и 10 (разность 0.5), потом 8 и 8.7 (0.7), потом 8.7 и 9.5 (0.8), потом 5 и 6 (1). При слиянии смотрите отношение текущего расстояния и следующего и минимум его тут 1/2.
Можно даже не сливать по пути, а просто найти все разности, отсортировать, найти пару с максимальным отношением и запомнить большее. Потом все точки, с расстоянием меньше этого числа - объединить в один кластер за еще один проход.