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

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;

сделать.

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

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

Magneto903, Странный у вас какой-то граф. Я правильно понял, что индекс в массиве - это начальная вершина, ключ в map - это вторая вершина, а значение - длина ребра?
У вас ребра вперед и назад разной длины, есть связь всех вершин с четвертой, а она назад только с третьей. Но дейкстра и в ориентированных графах работет, так что это не проблема.

Дабавьте еще вывода туда, где newDistance считается и в очереди что-то обновляется или добавляется. Проблема там, где второй раз выводится current_node 1. Видимо на предыдущей итерации он ее добавляет в очередь из дуги 1=>3

Как он ей делает distance = 3? Ведь в начале вы делаете distances.set(startNode, 0); и только уменьшаете расстояние.

Видимо косяк в этом коде:

if (!distances.get(child[0]) || distances.get(child[0]) > newdistance)

когда child[0] == 1, distances[1] ==0, newdistance ==3 он переписывает. Проверьте приоритет операций, что возвращает !distances.get(). Пройдитесь дебаггером.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, У вас есть шаг изменения широты, чтобы отступить на один метр.

Откладывайте его от x0, y0, пока расстояние от текущей точки до центра не станет больше вашего радиуса (исходные данные в вашей задаче).

Так вы получите столб точек прямо над центром с заданным шагом. Внитури этого цикла от каждой точки найдите таким же бинарным поиском (лучше его в отдельную функцию вынести) приращение по долготе. Отаклыдывайте это приращение влево и вправо, пока не выйдете за радиус.

Так вы получите все точки в сетке с расстоянием примерно в 1м в пределах заданного радиуса.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, Еще смотрите, что расстояние возвращенное haversine в тех же единицах, что и required_dist. Модуль по ссылке в ответе, вроде без дополнительных параметров возвращает в километрах.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, Потому что опечатка, надо в условии цикла поменять знак на >.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, required_dist - это ваш 1м, заданный в условии задачи.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203,

// x,y - точка от которой ищем +1м вверх
// -180 <=x<=180, -90<=y<=90.
l = 0
// required_dist - нужное приращение
r = min(180, 90-y);
while r-l < 1e-10:
  m=(r+l)/2;
  dist = haversine((x,y),(x,y+m)); // Формула для расстояния между точками.
  if dist > required_dist: r = m
  else l = m
step = l; // шаг по широте, чтобы сдвинутся на required_dist.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, расстояние между точками. 1 метр.

Но на самом деле там фигня у меня написана... лучше тупо до 180 по долготе и до 90 по широте гнать и не доумать.

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

Magneto903, Смотрите внимательно в отладке, этот цикл доходит до стартовой вершины? Выведите parents.

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

Magneto903, с этим циклом алгоритм не выполняется фактически.

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

Magneto903, Выглядит нормально.

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

Magneto903, давайте...

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

Magneto903, Не знаю, может minHeap коряво написан.

Вряд ли это причина ваших проблем, но changePriority (вернее вызываемый им remove) тут работает за линию. Поэтому в итоге решение, когда заработает, будет тормозить. Это можно вылечить, если переписать minHeap возвращать номер позиции куда добавленный элемент был воткнут в add. Ее надо в priorityQueue.add и changePriority сохранять. При вызове remove или changePriority надо удалять с этой позиции (немного переписать minHeap.remove не вызывая find, ведь номер позиции уже известен).

Добавляйте всюду отладочный вывод в консоль (minheap тоже), смотрите где память выделяется, куда девается.

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

Magneto903, Попробуйте воткнуть changePriority в конце. поменяйте 5 на 2. Должно вернуть a, c, b.

Добавьте отладочный вывод в дейкстру или вообще пройдитесь отладчиком по падающему тесту. Я не помниаю, как оно может падать по памяти. Смотрите, сколько вершин в очереди.

Еще дайте ссылку на реализацию priorityQueue. Может там косяк.

БлэкДжек, вероятность комбинации, как посчитать?

DALVROT, Нет, ничего не меняет. Ведь диллер мог вытащить туз,туз, 10, 5,
а мог, 5, туз, 10, туз. Да и тузы разные (даже если одной масти - это физически разные карты). Просто у вас массив A содержит 1,1,10,5 и все остальные карты.

Вам не надо никакие наборы добавлять в списки. Все различные наборы перебираются сами внутри динамического программирования.

Из ваших наборов надо очень аккуратно считать, сколькими способами их можно вытащить. Плюс они не независимые будут. Например, можно вытащить 10+3+2+5, а можно 10+3+5 и это разные наборы у вас. Хотя первый набор можно перетасовать в 10+3+5+2, но выбрать его так никогда не получится.

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

Magneto903, Что у вас за PriorityQueue реализация? Посмотрите код, потестируйте. Добавьте в очередь приоритеты a:1,b:3,c:5 и сделайте queue.poll() несколько раз.

Надо, что бы вернулись именно минимальные числа и они из очереди удалялись. Т.е. 3 poll() вернут a,b,c в таком порядке.

Если возвращается максимальный элемент, то вам надо пихать в очередь не newdistance, а -newdistance.

Если все три раза возвращается один и тот же элемент, то значит после poll() надо удалять элемент из очереди или спользовать какой-нибудь pop_front(), pop() метод у queue.

Код выглядит правильно.

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

Magneto903, Проверьте
1) queue.poll() удаляет первую вершину.
2) очередь возвращает вершину с МИНИМАЛЬНЫМ приоритетом.
3) Цикл for (var child of graph[startNode].keys()) не нужен.
4) Если child нет в очереди - то надо добавить вершину с приоритетом newdistance. Вы же только обновляете приоритет. если вершины нет.

БлэкДжек, вероятность комбинации, как посчитать?

Можно конкретизировать задачу для незнакомых с блекджеком?

Правильно ли я понимаю, что у вас есть набор возможных карт в колоде. Одна карта уже выдана дилеру. Диллер случайно вытаскивает по одной из оставшихся карт, пока не наберет >=17. И вам надо подсчитать вероятности всех сумм?