Comment testeriez-vous la fonctionnalité «Obtenir l'itinéraire» de Google Maps?

(J'imagine que ce serait une bonne question d'entrevue , mais dans mon cas, c'est plus pragmatique que cela.)

Nous avons une application large et complexe qui modélise un processus de réaction chimique extrêmement long et sophistiqué entre des dizaines de composants chimiques. Nous sommes au stade de la conception des tests d'acceptation pour l'application, mais nous sommes quelque peu découragés par le nombre insurmontable de chemins possibles à tester. Il m'est venu à l'esprit que notre situation ressemble beaucoup à ce que l'équipe de développement de Google Maps a dû faire face au moment de tester l'algorithme de planification d'itinéraire dans sa fonction "Obtenir l'itinéraire". De toute évidence, ils ne pouvaient pas tester (vérifier et valider) tous les itinéraires possibles. Alors, comment ont-ils eu l'assurance que leur application fonctionnerait dans toutes les situations?

Et comme je ne m'attends pas à découvrir comment ils l' ont fait, permettez-moi de vous demander: comment allez- vous concevoir une suite de tests avec une couverture de code adéquate, pour vous assurer qu'une application donnée est robuste - quand elle est littéralement impossible pour sonder chaque chemin potentiel à travers le système?

Ce que je recherche, ce sont les principes que vous utiliseriez pour décomposer un problème insoluble en morceaux plus petits et plus maniables, dont la somme fournit une estimation satisfaisante de l'ensemble: "Je ne peux pas tout tester, mais je peux le tester , ceci et cela - et cela suffit. " Je ne recherche pas une approche qui soit «prouvablement correcte», mais plutôt une approche prudente , compte tenu des contraintes de budget / temps réelles.

(J'utilise l'exemple de Google Maps comme un clin d'œil pour solliciter des réponses aussi précises que possible.)

J'ai travaillé dans le domaine de la navigation automobile il y a plus d'une décennie.

Étape A) Utilisez un package de référence et sélectionnez un grand ensemble d'échantillons, exécutez des tests A / B. Ne recherchant pas l'exactitude, recherchant des valeurs aberrantes - L'ensemble de référence a montré la Reroute 1234 à 10,34 km, et nous avons calculé 123,5 km.

Étape B) - Affiner notre logiciel et le logiciel de référence - Ajouter plus d'échantillons et réduire les tolérances.

Étape C) - Tests internes utilisant les connaissances locales à travers des ensembles de données mondiaux.

Étape D) UAT ... "Test d'acceptation des utilisateurs" Comme dans "Vendez ces trucs et voyez ce que les clients se plaignent le plus"

Si vous avez déjà utilisé des produits de cartographie vers le milieu des années 1990-2000, vous savez ce que je veux dire, ceux d'entre nous qui vérifiaient toujours les directions tour par tour à chaque fois.

Retour à votre exemple de question. Ce qu'on vous demande, c'est comment prouver qu'un logiciel est correct. Si vous voulez une preuve mathématique, il a été démontré que cela peut être fait - pour un logiciel simple à un prix qui dépasse tous les budgets réalistes, pour un progiciel complexe, eh bien, c'est encore de la recherche ... La NASA a des modèles pour écrire des logiciels très fiables dans des prix économiquement gérables, comme le font le DoD et l'industrie aéronautique - bien que toujours beaucoup plus élevés que la plupart sont prêts à payer. En fin de compte, cela revient à combien êtes-vous prêt à payer .....

Edit: je viens de vous relire OP. Il semble que ce que vous cherchez soit un moyen rapide et bon marché de tester la qualité d'un logiciel complexe. Vous ne pouvez pas tester la qualité. Vous devez avoir un processus robuste pour savoir que ce qui est construit fonctionne correctement. Si vous devez réfléchir à la façon de prouver qu'elle est correcte et que vous avez déjà une "application large et complexe", vous êtes trop tard.

Nous sommes l'un des concurrents de Google. Notre réponse? Fondamentalement, deux.

Tout d'abord, nous calculons la solution complète d'adresse à adresse. Oui, c'est une grande matrice. Pire encore, nous le faisons à tout moment de la journée, tous les jours de la semaine. Il y a suffisamment de similitude dans le domaine d'entrée pour mettre en cache les résultats intermédiaires, ce qui rend le problème traitable. Essayez tout de même d'obtenir un taux global sur les disques durs.

Notez que ce calcul hors ligne est effectué à l'aide d'un algorithme différent. Il utilise beaucoup plus de mémoire que l'algorithme que nous avons l'intention de tester, mais pas linéairement plus (c'est-à-dire qu'il utilise moins de 1000 fois plus de mémoire lors du calcul d'un millier de routes).

Deuxièmement, les utilisateurs participants nous fournissent des résultats réels. Nous validons des millions d'itinéraires parcourus. Les itinéraires réels sont-ils aussi rapides que prévu?

Et bien sûr, vous trouvez des bogues de cette façon. Tout le temps. Par exemple, un tronçon de route délimité des deux côtés par une "zone réservée à la circulation locale" *. Il n'y a qu'une seule façon;) que vous allez trouver cela lors des tests, et c'est à ce moment-là que vous planifiez un itinéraire vers cette route particulière.

_{* Une "zone de trafic local uniquement" ne peut être utilisée que lorsque vous commencez ou terminez un itinéraire dans une telle zone. Le tronçon du milieu est donc déconnecté du réseau routier principal. Il s'agit soit d'un zonage, soit d'un défaut de carte.}

Ce n'est pas comme si Google écrit un code distinct pour chaque paire d'adresses dans le monde. À l'exception des heuristiques qui démarrent à plus grande échelle, l'algorithme pour un voyage à 3 étapes est exactement le même que pour une étape à 3000 étapes. Vous testez soigneusement les chemins plus courts et utilisez l'induction pour montrer que le test s'applique également aux chemins plus longs.

Vous choisissez un échantillon sain d'itinéraires du monde réel et le comparez à ce que propose un humain. Vous prêtez beaucoup d'attention aux commentaires des utilisateurs finaux dans vos premières versions et vous leur permettez de les fournir facilement. Vous testez les conditions aux limites, comme si le meilleur itinéraire nécessite réellement de s'éloigner de la destination pendant un certain temps, ou si l'itinéraire le plus court par la distance a 18 tours par rapport à un itinéraire plus direct qui est légèrement plus long. Vous effectuez des tests négatifs, comme si vous essayez de conduire de la Californie à Hawaï, et assurez-vous que des œufs de Pâques intelligents sont en place.