Wie würden Sie die Funktion "Route berechnen" von Google Maps testen?

(Ich stelle mir vor, das wäre eine gute Interviewfrage , aber in meinem Fall ist es pragmatischer.)

Wir haben eine große und komplexe Anwendung , die einen extrem langen und ausgeklügelten chemischen Reaktionsprozess zwischen Dutzenden chemischer Komponenten modelliert. Wir sind gerade dabei, Abnahmetests für die Anwendung zu entwerfen, sind jedoch etwas entmutigt über die unlösbare Anzahl möglicher Testpfade. Mir ist aufgefallen, dass unsere Situation der Situation des Google Maps-Entwicklerteams sehr ähnlich ist, als es darum ging, den Routenplanungsalgorithmus in der Funktion "Route berechnen" zu testen. Offensichtlich konnten sie nicht jede mögliche Route testen (verifizieren und validieren). Wie kamen sie zu der Gewissheit, dass ihre Anwendung in jeder Situation funktionieren würde?

Und da ich nicht damit rechne, herauszufinden, wie sie es geschafft haben, möchte ich Sie fragen: Wie würden Sie eine Testsuite mit angemessener Codeabdeckung entwerfen , um sich davon zu überzeugen, dass eine bestimmte Anwendung robust ist - wenn es buchstäblich unmöglich ist jeden möglichen Weg durch das System zu sondieren?

Was ich suche, sind die Prinzipien, die Sie verwenden würden, um ein hartnäckiges Problem in kleinere, handhabbare Teile zu zerlegen, deren Summe eine zufriedenstellende Schätzung des Ganzen liefert: "Ich kann nicht alles testen, aber ich kann dies testen , dies und das - und das ist genug. " Ich suche nicht einen Ansatz, der "nachweislich richtig" ist, sondern einen , der angesichts realer Budget- / Zeitbeschränkungen umsichtig ist.

(Ich verwende das Google Maps-Beispiel als eine Art Folie, um Antworten zu erhalten, die so spezifisch wie möglich sind.)

Ich habe vor über einem Jahrzehnt in der Autonavigation gearbeitet.

Schritt A) Verwenden Sie ein Referenzpaket und wählen Sie einen großen Probensatz aus. Führen Sie A / B-Tests durch. Keine Suche nach Genauigkeit, keine Suche nach Ausreißern - Im Referenzsatz wurde die Route 1234 mit 10,34 km angegeben, und wir berechneten 123,5 km.

Schritt B) - Verfeinern Sie unsere Software und die Referenzsoftware. - Fügen Sie weitere Muster hinzu und reduzieren Sie die Toleranzen.

Schritt C) - In-House-Tests mit lokalem Wissen über globale Datensätze hinweg.

Schritt D) UAT ... "User Acceptance Test" Wie in "Verkaufe dieses Zeug und schau, worüber sich die Kunden am meisten beschweren"

Wenn Sie jemals Mapping-Produkte zwischen Mitte der 1990er und 2000 verwendet haben, wissen Sie, was ich meine, diejenigen von uns, die noch jedes Mal die Abbiegehinweise überprüft haben.

Zurück zu Ihrer Beispielfrage. Was Sie gefragt werden, ist, wie Sie beweisen können, dass eine Software korrekt ist. Wenn Sie einen mathematischen Beweis benötigen, ist nachgewiesen, dass dies möglich ist - für einfache Software zu einem Preis, der jedes realistische Budget übersteigt, für ein komplexes Softwarepaket, das noch in der Forschung steckt. Die NASA verfügt über Modelle zum Schreiben von hochzuverlässiger Software innerhalb wirtschaftlich überschaubarer Preise, ebenso wie DoD und die Luftfahrtindustrie - obwohl immer noch viel höher als die meisten bereit sind zu zahlen. Am Ende kommt es darauf an, wie viel Sie bereit sind zu zahlen .....

Edit: Ich habe gerade das OP neu gelesen. Was Sie suchen, ist anscheinend eine schnelle und kostengünstige Möglichkeit, die Qualität einer komplexen Software zu testen. Sie können nicht in der Qualität testen. Sie benötigen einen robusten Prozess, damit Sie wissen, dass das, was erstellt wird, richtig funktioniert. Wenn Sie darüber nachdenken müssen, wie Sie die Richtigkeit beweisen können und bereits eine "große und komplexe Anwendung" haben, sind Sie zu spät.

Wir sind einer der Konkurrenten von Google. Unsere Antwort? Grundsätzlich zwei.

Zunächst berechnen wir die vollständige Adress-zu-Adress-Lösung. Ja, das ist eine große Matrix. Schlimmer noch, wir tun dies zu jeder Tageszeit, an allen Tagen der Woche. In der Eingabedomäne gibt es genügend Ähnlichkeiten, um Zwischenergebnisse zwischenzuspeichern, wodurch das Problem behoben werden kann. Versuchen Sie dennoch, eine Bulk-Rate für Festplatten zu ermitteln.

Beachten Sie, dass diese Offline-Berechnung mit einem anderen Algorithmus durchgeführt wird. Es verwendet viel mehr Speicher als der Algorithmus, den wir testen möchten, aber nicht linear mehr (dh es verwendet weniger als das 1000-fache an Speicher, wenn tausend Routen berechnet werden).

Zweitens liefern uns die teilnehmenden Benutzer reale Ergebnisse. Wir validieren Millionen von gefahrenen Strecken. Sind die tatsächlichen Routen so schnell wie vorhergesagt?

Und natürlich finden Sie auf diese Weise Fehler. Jedesmal. ZB ein Straßenabschnitt, der auf beiden Seiten von einer "Nur-Nahverkehrszone" * begrenzt wird. Es gibt nur einen Weg;), den Sie beim Testen finden werden, und dann planen Sie eine Route zu dieser bestimmten Straße.

_{* Eine "Zone nur für lokalen Verkehr" kann nur verwendet werden, wenn Sie eine Route in einer solchen Zone starten oder beenden. Die Strecke in der Mitte ist daher vom Hauptstraßennetz getrennt. Dies ist entweder ein Zonen- oder ein Kartenfehler.}

Es ist nicht so, als würde Google für jedes Adresspaar der Welt einen eigenen Code schreiben. Mit Ausnahme von Heuristiken, die in größerem Maßstab eingesetzt werden, ist der Algorithmus für eine Reise mit drei Etappen genau derselbe wie für eine Reise mit 3000 Etappen. Sie testen die kürzeren Pfade gründlich und verwenden die Induktion, um zu zeigen, dass der Test auch für längere Pfade gilt.

Sie wählen eine gesunde Stichprobe realer Routen aus und vergleichen sie mit den Vorstellungen eines Menschen. Sie legen großen Wert auf das Feedback der Endbenutzer in Ihren ersten Releases und erleichtern ihnen die Bereitstellung. Sie testen die Randbedingungen, zum Beispiel, ob die beste Route tatsächlich eine Weile vom Ziel entfernt sein muss oder ob die kürzeste Route nach Entfernung 18 Umdrehungen aufweist, verglichen mit einer direkteren Route, die etwas länger ist. Sie machen negative Tests, wenn Sie versuchen, von Kalifornien nach Hawaii zu fahren, und stellen sicher, dass clevere Ostereier vorhanden sind.