Датские ученые нашли решение задачи, которой занимались сорок лет

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

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

В сообщении говорится, что ученые факультета компьютерных наук — доцент Кристиан Вульф-Нильсен и его коллеги смогли составить алгоритм нахождения кратчайшего пути. Поиск решения особенно осложняется при изменении ситуации на дороге, оптимальный маршрут может внезапно стать очень медленным из-за аварии на дороге или при дорожных работах.

«Мы разработали алгоритм, для которого теперь у нас есть математическое доказательство того, что он лучше, чем любой другой алгоритм до настоящего времени — и наиболее близок к оптимальному из возможных, даже если мы заглянем на тысячу лет в будущее», — заявил Вульф-Нильсен.

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

Ученые использовали в своей работе так называемый «динамический» граф, в котором узлы и ребра могут быть удалены или изменятся, если участок дороги или перекресток внезапно становится недоступным по разным причинам.

«Огромное преимущество рассмотрения сети как абстрактного графа состоит в том, что его можно использовать для представления любого типа сети. Это может быть Интернет, куда вы хотите отправлять данные по как можно более короткому маршруту, человеческий мозг или сеть дружеских отношений на Facebook. Это делает алгоритмы графов применимыми в самых разных контекстах», — сообщает Вульф-Нильсен.

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

«Мы живем в то время, когда объемы данных растут с огромной скоростью, а разработка оборудования просто не успевает за ними. Чтобы управлять всеми данными, которые мы производим, нам необходимо разработать более умное программное обеспечение, которое на выполнение требует меньше времени и памяти. Вот почему нам нужны более умные алгоритмы», — подводит итоги Вульф-Нильсен.

Напомним, ИА «Красная Весна» уже писала о новом решении задачи трех кубов, которая была поставлена в 1953 году.

Читайте также: Математики нашли новое решение задачи «Сумма трех кубов»