AInewz

Век поиска кратчайшего пути

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

Однако это не так — прогресс был, и придумано много интересного.

Хотя фокус сместился и на другие задачи.

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

Почему автора огорчает, что HOMM III не учитывает флаг единства при расчете путей, и кто эти люди на фотографии рядом с Дейкстро́й?


Прогресс в поиске кратчайших путей

  1. Алгоритм Дейкстры.
  2. Эдсгер Дейкстра в 1959 году разработал алгоритм, который получил широкое распространение и используется до сих пор.
    Алгоритм позволяет находить кратчайшее расстояние от одной вершины графа до всех остальных вершин.
    Этот алгоритм называют «почти оптимальным», поскольку он работает за O (M log N), где M — количество рёбер,
    N— количество вершин.

    То есть этот алгоритм работает асимптотически оптимально.

  3. Более быстрые алгоритмы
  4. С развитием вычислительной техники появились более быстрые алгоритмы, которые позволяют находить кратчайшие пути за меньшее время, чем алгоритм Дейкстры.
    Например, в 2000

Игорь Орехов

Подписывайтесь на нас (Follow us)

Не стесняйтесь, пишите. Мы любим знакомиться с интересными людьми и заводить новых друзей.

Don't be shy, get in touch. We love meeting interesting people and making new friends.

Most popular

Most discussed