Fermer le menu
Pieuvre
    Facebook X (Twitter) Instagram
    PieuvrePieuvre
    • Accueil
      • Qui sommes-nous?
      • Travaillez avec nous
      • Work with us
      • Abonnez-vous à l’infolettre
      • Encouragez Pieuvre
      • Nos abonnés
      • Contactez-nous
    • Culturel
      • Festivals
        • Cinémania
        • Fantasia
        • FIFA
        • FIJM
        • FIL
        • FNC
        • Fringe
        • FTA
        • Image+Nation
        • OFFTA
        • Montréal complètement cirque
        • Mutek
        • Nuits d’Afrique
        • RIDM
        • RVQC
        • Vues d’Afrique
        • Zoofest
      • Arts visuels
      • Cinéma / Télévision
      • Danse
      • Littérature
        • Romans
        • Essais
        • Bandes dessinées
        • Beaux livres
        • Biographie
        • Poésie
        • Recettes
      • Musique
      • Théâtre / Cirque
    • Politique / Économie
      • Politique
      • Économie
      • Afrique
      • Amériques
        • Élections québécoises 2026
      • Asie
      • Europe
      • Moyen-Orient
      • Océanie
    • Science
      • Science
      • Environnement
    • Société
      • Société
      • Médias
      • Santé
      • Vie tentaculaire
      • Jeux de société
      • Jeux de rôle
      • 45 ans du Stade olympique
    • Techno / Jeux
      • Technologie
        • Séance de test
      • Jeux vidéo
        • Jeux préférés de…
        • Rétroctopode
    • Podcasts
      • Entretiens journalistiques
      • Rembobinage
        • La Voûte
        • Projection
      • SVGA
      • Pixels et préjugés
      • Heure supplémentaire
      • Des nouvelles de l’Oncle Sam
      • Dans les coulisses de…
    • Encouragez Pieuvre
    Pieuvre
    Accueil»Technologie»Un nouvel algorithme pour résoudre un vieux problème d’itinéraire

    Un nouvel algorithme pour résoudre un vieux problème d’itinéraire

    0
    Par Pieuvre.ca le 12 mars 2021 Technologie

    L’un des problèmes d’algorithme les plus connus est lié au calcul du plus court trajet entre deux points. Une variante plus complexe de ce casse-tête consiste à faire passer la trajectoire au sein d’un réseau changeant, que ce soit un réseau routier ou le web. Pendant 40 ans, des chercheurs ont voulu concevoir un algorithme offrant une solution optimale à ce problème. Maintenant, le chercheur en informatique Christian Wulff-Nilsen, de l’Université de Copenhague, croit avoir trouvé une solution en compagnie de deux collègues.

    En se rendant à une nouvelle destination, la plupart d’entre nous faisons confiance à des algorithmes informatiques pour calculer le meilleur trajet, que ce soit en utilisant un GPS dans la voiture, ou les transports publics et des applications de cartographie sur téléphone intelligent. Malgré tout, il survient des occasions où les trajets proposés ne correspondent pas tout à fait à la réalité. Cela s’explique par le fait que les réseaux routiers, ceux des transports collectifs et d’autres réseaux ne sont pas statiques. Le meilleur trajet peut soudainement devenir le plus lent, par exemple parce que les véhicules ont soudainement ralenti en raison de travaux de construction ou d’un accident.

    Les gens ne pensent probablement pas aux équations mathématiques complexes sous-tendant les suggestions de chemins à emprunter dans ce genre de situations. Le logiciel utilisé tente de trouver une variante au problème algorithmique classique du « plus court trajet », c’est-à-dire le plus court trajet au sein d’un réseau dynamique.

    Pendant 40 ans, des chercheurs ont tenté de trouver un algorithme qui peut résoudre ce casse-tête mathématique de façon optimale. M. Wulff-Nilsen estime y être parvenu.

    « Nous avons conçu un algorithme, pour lequel nous disposons maintenant d’une preuve mathématique, qui est meilleur que tout autre algorithme développé jusqu’à maintenant, et s’avère être la chose la plus optimale qui sera jamais créée, même pour une période de 1000 ans », affirme M. Wulff-Nilsen.

    L’adjectif optimal, dans ce contexte, fait référence à un algorithme qui consacre le moins de temps possible et le moins de mémoire informatique possible pour calculer le meilleur itinéraire au sein d’un réseau donné. Cela ne s’applique pas seulement aux réseaux routiers, mais aussi au web, ou à tout autre genre de réseau.

    Des réseaux sous forme de graphiques

    Les chercheurs représentent un réseau comme un graphique dynamique. Dans le contexte, un graphique est une représentation abstraite d’un réseau formé d’arrêtes, des routes, par exemple, ainsi que des points de convergence, qui représentent les intersections, entre autres.

    Lorsqu’un graphique est dynamique, cela veut dire qu’il peut changer avec le temps. Le nouvel algorithme gère ces changements, notamment lorsqu’une arrête disparaît. Sur le terrain, cela pourrait équivaloir à une section de route rendue inaccessible en raison de travaux.

    « Le grand avantage de voir un réseau comme un graphique abstrait est le fait qu’il peut être utilisé pour représenter tout type de réseau. Cela pourrait être le web, où vous voulez envoyer des données selon le plus court trajet possible, comme un cerveau humain, ou un réseau d’amis sur Facebook. Cela permet d’utiliser les algorithmes de création de graphiques dans une grande variété de contextes », explique encore M. Wulff-Nilsen.

    Les algorithmes traditionnels tiennent pour acquis qu’un graphique est statique, ce qui est rarement vrai dans le monde réel. Lorsque ce genre d’algorithmes sont utilisés dans un réseau dynamique, ils doivent être relancés chaque fois qu’un changement se produit au sein du graphique, ce qui gaspille du temps.

    Abonnez-vous à l’infolettre!

    Encouragez Pieuvre.ca


    Des chaussures qui font courir un peu plus vite

    Partager. Facebook Twitter Pinterest LinkedIn Tumblr E-mail

    Articles connexes

    13 novembre 2026

    Big Tech rate ses cibles de réduction de GES

    25 octobre 2026

    Pour de l’asphalte plus durable, ajoutez-y du plastique

    12 octobre 2026

    Les parents veulent faire interdire les médias sociaux… même s’ils les utilisent

    Pieuvre.ca
    • Site web
    • Facebook
    • X (Twitter)

    Laisser un commentaire Annuler la réponse

    Vous cherchez un contenu?
    Abonnez-vous à l’infolettre!

    Suivez-nous
    Dossiers spéciaux
    • Cinémania
    • FNC
    • Élections québécoises 2026
    • Séance de test
    Nos podcasts
    • Entretiens journalistiques
    • Rembobinage
    • Projection
    • Des nouvelles de l’Oncle Sam
    • SVGA
    • Pixels et préjugés
    • Heure supplémentaire
    • Dans les coulisses de…
    Récemment publié
    16 novembre 2026

    La Gradiva: les cendres de Cupidon

    16 novembre 2026

    Les quatre saisons de Vivaldi, « nouvelles et améliorées ».

    16 novembre 2026

    Les ultrariches polluent plus que vous et 3,5 milliards d’autres personnes

    15 novembre 2026

    En haut de la pile: l’amour suffira

    15 novembre 2026

    33 Days Till Extraction, le combat de tous les instants

    Informations
    • Votre semaine tentaculaire
    • Qui sommes-nous?
    • Contactez-nous
    © 2009-2026 Pieuvre.ca. Tous droits réservés.

    Tapez ci-dessus et appuyez sur Entrée pour rechercher. Appuyez sur Échap pour annuler.

    Gérez votre confidentialité

    Pour offrir les meilleures expériences, nous et nos partenaires utilisons des technologies telles que les cookies pour stocker et/ou accéder aux informations de l’appareil. Le consentement à ces technologies nous permettra, ainsi qu’à nos partenaires, de traiter des données personnelles telles que le comportement de navigation ou des ID uniques sur ce site et afficher des publicités (non-) personnalisées. Ne pas consentir ou retirer son consentement peut nuire à certaines fonctionnalités et fonctions.

    Cliquez ci-dessous pour accepter ce qui précède ou faites des choix détaillés. Vos choix seront appliqués uniquement à ce site. Vous pouvez modifier vos réglages à tout moment, y compris le retrait de votre consentement, en utilisant les boutons de la politique de cookies, ou en cliquant sur l’onglet de gestion du consentement en bas de l’écran.

    Fonctionnel Toujours activé
    Le stockage ou l’accès technique est strictement nécessaire dans la finalité d’intérêt légitime de permettre l’utilisation d’un service spécifique explicitement demandé par l’abonné ou l’internaute, ou dans le seul but d’effectuer la transmission d’une communication sur un réseau de communications électroniques.
    Préférences
    L’accès ou le stockage technique est nécessaire dans la finalité d’intérêt légitime de stocker des préférences qui ne sont pas demandées par l’abonné ou l’internaute.
    Statistiques
    Le stockage ou l’accès technique qui est utilisé exclusivement à des fins statistiques. Le stockage ou l’accès technique qui est utilisé exclusivement dans des finalités statistiques anonymes. En l’absence d’une assignation à comparaître, d’une conformité volontaire de la part de votre fournisseur d’accès à internet ou d’enregistrements supplémentaires provenant d’une tierce partie, les informations stockées ou extraites à cette seule fin ne peuvent généralement pas être utilisées pour vous identifier.
    Marketing
    Le stockage ou l’accès technique est nécessaire pour créer des profils d’internautes afin d’envoyer des publicités, ou pour suivre l’internaute sur un site web ou sur plusieurs sites web ayant des finalités marketing similaires.
    Statistiques

    Marketing

    Fonctionnalités
    Toujours activé

    Fonctionnalités spéciales

    Finalités spéciales
    Toujours activé

    • Gérer les options
    • Gérer les services
    • Gérer {vendor_count} fournisseurs
    • En savoir plus sur ces finalités
    Gérer les options
    • {title}
    • {title}
    • {title}

    logo

     Ne manquez aucun article ou épisode de podcast: abonnez-vous à l’infolettre!