O novo algoritmo de classificação é melhor do que Dijkstra

Existe um novo algoritmo de classificação Um algoritmo determinístico de O (M Log2/3 N) para caminhos mais curtos de fonte única (SSSP) em gráficos direcionados com pesos de borda não negativos reais no modelo de comparação de adição. Este é o primeiro resultado a quebrar o tempo de tempo O (M + N log n) do algoritmo de Dijkstra em gráficos esparsos, mostrando que o algoritmo de Dijkstra não é ideal para o SSSP. Isso melhora o vencedor do prêmio Tarjan’s O (M + NLOGN) com Dijkstra’s, algo que todo estudante de ciência da computação aprende na faculdade. Ele combina técnicas de Bellman-Ford, um algoritmo mais lento e Dijkstra’s para melhorar o tempo de execução. Ele minimiza a dependência da classificação da fila de prioridade, processando vários nós (o “Frontier”) ao mesmo tempo usando novas estruturas de dados, conquistando o gargalo de classificação, especialmente em gráficos esparsos. Melhoria quantitativa Limite antigo (dijkstra): O (m+nlog⁡n) o (m+nLogn) Novo limite: o (mlog⁡2/3n) o (mlog2/3n) para gráficos esparsos onde mm tem cerca de o (n) o (n), isso é assintoticamente mais acelerado, como neve. Impacto prático e teórico Teórico: muda a compreensão do cálculo mais curto para os gráficos direcionados. Inspira novas avenidas de pesquisa para algoritmos de gráficos ideais, livres de restrições de classificação. Fornece evidências de que novas melhorias podem ser possíveis. Prático: algoritmos mais rápidos para redes enormes e esparsas (transporte, roteamento, redes sociais). Escalabilidade: redes com milhões de nós/arestas podem ver ganhos de velocidade perceptíveis. As técnicas podem generalizar ou inspirar melhorias em cenários mais complexos (por exemplo, arestas ponderadas, negativas, gráficos dinâmicos). Modelos híbridos (usando Bellman-Ford para inicialização e dijkstra para estado estacionário ou outras combinações) mostraram melhor adaptabilidade, robustez e eficiência computacional, especialmente quando combinadas com o aprendizado de máquina para seleção de rota em tempo real. Ele desafia as suposições sobre limites baseados em comparação, potencialmente influenciando problemas relacionados, como caminhos mais curtos dos pares ou algoritmos de gráficos dinâmicos. As discussões destacam seu log⁡2/3n \ log^{2/3} n \ log^{2/3} N fator como um novo truque de particionamento recursivo. Pode inspirar outras melhorias na classificação. APLICAÇÕES: Navegação e roteamento: recálculos mais rápidos de GPS, simulação de tráfego e logística (por exemplo, entregas mais baratas por meio de caminhos otimizados). Redes e gráficos: roteamento mais rápido em redes de computadores, gráficos sociais ou vias biológicas. Potencial em IA/ML: pode acelerar modelos baseados em gráficos (por exemplo, em sistemas de recomendação ou de aprendizado de reforço). Há alta complexidade de implementação e possíveis grandes constantes. É mais lento que as variantes de dijkstra sintonizadas (por exemplo, com pilhas binárias) ou heurísticas como Hierarquias A* e Contração em redes rodoviárias. Isso será refinado e melhorado. Brian Wang é um líder de pensamento futurista e um blogueiro de ciências popular com 1 milhão de leitores por mês. Seu blog NextBigfuture.com está classificado como #1 Blog de notícias de ciências. Abrange muitas tecnologias e tendências disruptivas, incluindo espaço, robótica, inteligência artificial, medicina, biotecnologia antienvelhecimento e nanotecnologia. Conhecida por identificar tecnologias de ponta, ele atualmente é co-fundador de uma startup e angariador de fundos para empresas em estágio inicial de alto potencial. Ele é o chefe de pesquisa de alocações para investimentos em tecnologia profunda e um investidor anjo da Space Angels. Um orador frequente das empresas, ele foi um orador do TEDX, um orador da Universidade de Singularidade e convidado em inúmeras entrevistas para rádio e podcasts. Ele está aberto a falar em público e aconselhar compromissos.

Fonte