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

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

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

Magneto903, Зависит от графа. Дейкстра работает всегда более или менее одинаково. Этот алгоритм может работать в несколько раз быстрее или в сотни раз медленнее.

На сях, конечно, быстрее будет в среднем. Я бы советовал дейкстру в wasm скомпилировать, если вам так скорость нужна.

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

Magneto903,
О, я понял, почему этот алгоритм работает.
Это что-то типа волнового алгоритма и алгоритма Белла. Всякий раз как где-то ребро релаксируется, конец снова добавляется для рассмотрения.

Проблема с ним, что он может работать сильно дольше на неудачных тестах, потому что каждая вершина может быть в очереди сколько угодно раз. Тут вам повезло с графом, но может быть сииильно хуже.

Можно вообще сделать так, что длина очереди будет O(2^n) для n вершин. Но это будут весьма искусственные тесты. Может в вашем случае оно в среднем будет работать лучше.

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

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++ и сравнить оба решения на одной машине.