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

Dijkstra возвращает путь - это get_paths.

Если вам нужна get_dists, то можете взять dijkstra и вернуть массив distances после цикла while. Остальной код не нужен.

Что бы 2 раза не гонять дейкстру для расстояний и пути можно вернуть одновременно массив distances и prev. Тогда по prev кодом в Dijsktra после while можно построить путь, если он нужен.

Ваш массив graph перобразуется в Graph в функции Load.
Это фактически и есть двумерый массив, но там ребра из каждой вершины сгруппированы в одну строчку.

Алгоритм для минимизации стоимости товаров от разных поставщиков, какие ресурсы изучить?

Adamos, Как в вашем примере отсекается оптимальный вариант? Вариант "берем только первого продавца" - не отсекается, потому что он имеет минимум по всем товарам из всех взятых продавцов (он один).

Критерий не говорит, что какого-то продавца никогда не будет смысла брать потому что другие существуют. Он говорит, что не будет смысла брать его вместе с некоторыми другими.

Вот еще раз цитата:

Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару.

Алгоритм для минимизации стоимости товаров от разных поставщиков, какие ресурсы изучить?

Adamos, Поэтому брать всех трех продавцов - невыгодно. Если какой-то продавец не дает минимум покакому-то товару, то все покупаемые у него товары можно купить у кого-то другого дешевле. Значит можно сделать так и выкинуть этого продавца и не платить ему за доставку.

Брать только перовго продавца или только двух других - локально оптимальные решения и их оба придется рассматривать в переборе.

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

Как выполнить эту задачу на алгоритмы?

Nurdaulet Turar, Можно ли в условии ставить несколько комманд? Вроде - если текущая клетка филоетовая - повернуть направо, шаг вперед, окрасить в оранжевый, вернуться в начало.

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

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.

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

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