Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, Эта реализация пишет 0.034 в консоль. Видимо - это ms на прогон. Си-шная моя по прежнему 0.024ms. Весьма близко.

Но правильно ли работает? Я не понимаю, что там в get_path за алгоритм. Что-то среднее между BFS и дейкстрой. Проверьте, что путь такой же как прошлая версия выдает.

Как исправить ошибку - "ZeroDivisionError: Inverse of Mod(0,2) does noet exist"?

sazer, Судя по всему, там используется какая-то своя арифметика на целых числах на эллиптической кривой. Там вещественные числа вообще никаким боком привязаны быть не могут. Соответственно, вопрос точности не стоит - все числа-то целые. На С++ каком-нибудь был бы вопрос переполнения, но в питоне реализована длинная арифметика, поэтому и это не проблема.

Как исправить ошибку - "ZeroDivisionError: Inverse of Mod(0,2) does noet exist"?

sazer, Попробуйте деление на 2 заменить на целочисленное m//2.

Как исправить ошибку - "ZeroDivisionError: Inverse of Mod(0,2) does noet exist"?

Что за задачу-то код решает? Что он должен делать?

Как оптимизировать код на Python?

А в чем здесь оптимизация? Разве что код короче, а работать будет даже медленнее, потому что на каждой итерации проверяет все значения, после текущего. У автора в вопросе же после первого большего элемента стоит break.

Как получилась запись в квадратных скобках?

Василий Иванов, Она доказывается через разложение экспоненты в ряд тейлора и перегруппировку его в сумму двух рядов - синуса и косинуса. Запись на картинке - тупо применение формулы Эйлера, и никак не может использоваться в самом доказательстве.

Больше похоже на разбор свойств экспоненты от комплексных аргументов с применением формулы Эйлера.

Как решить эту задачу?

Rsa97, А если степень была бы не 2020, а 10000000000000? А если там k в общем виде?

Формула смены логарифма тут и не нужна вообще. log(a^b) = log(a)*b - это известная и так формула.

Поможет ли функциональный ЯП (например, Haskell) лучше понять ООП (С++)? Если да, то чем конкретно он поможет?

Василий Банников, На мой взгляд, ФП просто ломает мозг, если вы привыкли к императивщине и наоборот.
ФП - крутая штука, но учить ее, чтобы лучше понять ООП - точно не стоит.

Почему у меня не выводится текст в файле?

Оформите код в тег code.

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, Да. Bfs работает только если все ребра одинаковой длины. Ну или можно его обобщить, когда все длины - целые числа от 0 до какого-то маленького K, если использовать K+1 очереди.

Корректен ли данный код, возможна ли оптимизация?

Николай, Почти.
После continue и break в if не надо писать else, как у вас в начале. Так снижается уровень вложенности для основной логики.

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, Пары сравниваются по первым частям, потом по вторым, если равенство в первом случае. На самом деле там недочет у меня. Можно, как в ShiftDown сравнивать только heap_[i].first. Будет даже чуть чуть быстрее.

Деление на 2 в целых числах округляется вниз. Для 1 и 2 (i-1)/2 даст 0, для 3 и 4 - 1. Точно также в вашей реализации кучи действует getParentIndex.

Как реализовать приоритетную очередь?

Никита, Смотрите этот код, который я тут написал в другой теме.

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, Js код работает 0.508ms. Мой С++ код - 0.024ms
Сумма и там и там одинаковая: 401.

Если хотите проверить, вставьте в текстовый файл "348 157 159" в первую строку, а потом ваши ребра (начало, конец, длина). Скомпилировать можно вот этой коммандой:

g++ dijkstra.cpp -O2 -Wall -std=c++14 -static-libgcc -static-libstdc++ -o dijkstra.exe

Скормить текстовый файл можно через командную строкуdijkstra.exe <input.txt.

Мой код чуть проще того minHeap что у вас используется, потому что там слишком общий. Можете попробовать так же обрезать ваш, но в 20 раз вы ускорения не получите.

Эти 20 раз - это объекты, мапы везде вместо тупых интов и массивов.

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, Совсем забыл, когда формат описывал. А длины ребер-то какие? Надо по три числа выдавать.

И да, ребра у вас одинаковой длины в разные стороны?

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, Лучше просто текстом без всякого синтаксиса. в c++ json нет и надо как-то прикручивать парсинг, дополнительный.

1 2
2 3
1 3

И сначала - сколько ребер, какая вершина начальная, какая конечная.

Можно console.log(a+" "+b) для всех ребер делать.

Для проверки идентичности решений, например, пусть ваш JS бенчмарк считает сумму всех вершин в кратчайшем пути. Или сумму произведений <вершина>* (0 для startNode).

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, По моим расчетам, ~0.05ms. +-в пару раз разброса в зависимости от машины. Если вы мне дадите js скрипт, который фиксированный тест прогоняет 1000 раз и меряет среднее время, и заодно тест в тектовом виде (не json, а тупо список ребер парами номеров), то я могу замерить на C++ и сравнить оба решения на одной машине.

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903,

Похоже вы исчерпали возможности джаваскрипта.

Флойд будет быстрее если у подвижных вершин мало соседей. Но, например, когда вам надо найти пути до всех вершин, чтобы найти самую далекую, вам придется для каждой из n конечных вершин перебирать всех соседей подвижного начала. Это может быть даже медленнее дейкстры,

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, ускорение не в n раз. До этого было n^2+m, теперь стало (n+m) log n операций. Да и операции чуть посложнее стали. Где-то 10 раз и есть ускорение. Этого вам теперь должно хватить.

Самая быстрая реализация алгоритма Дейкстры на javascript?

this.indexes у вас должен быть map из item в место в очереди.

В swap надо делать:

this.indexes.set(this.heapContainer[indexOne], indexOne);
this.indexes.set(this.heapContainer[indexTwo], indexTwo);

Надо в poll тоже переписывать index у pop-нутого элемента:
this.indexes.set(this.heapContainer[0], 0);

В remove тоже есть место где вы на место indexToRemove ставите последний элемент. Надо

indexes[heapContainer[indexToRemove]] = indexToRemove;

сделать.

Воде все косяки, что я нашел.