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 вектора - один от красного бота, другой - в самую далекую точку. И вам надо как-то между этими векторами выбирать. Например, складывайте их с разными коэффициентами - вот и будет ваше направление для зеленого бота.
Magneto903, Найдите расстояния от преследователя до всех вершин. Найдите самую далекую вершину. Найдите расстояния от этой вершины до всех остальных. Выбирайте то ребро, которое уводит от преследователя и при этом уменьшает расстояние до самой далекой вершины.
В этом случае зеленый будет локально не идти на встречу красному и не будет заходить в тупик, потому что этот тупик удлиняет расстояние до самой далекой вершины.
Это будет работать плохо только если зеленый уже в тупике и прижат красным.
По условию получается, что в результирующем массиве может быть сколько угодно элементов - ровно столько, сколько положительных в массиве C. Вам можно использовать std::vector? Если это действительно C++, а не C, то стоит использовать его.
Andrei1penguin1, Ну запустите уже far или totalcommander, поищите в этой папке файлы с подстрокой "Py_Initialize". Найдите уже файл - библиотеку, которой не хватает и ее укажите в -l.
Осталось реализацию дейкстры исправить не с массивом visited самих номеров вершин и линейным поиском в нем, а массив из N пометок 0/1.