¿Cómo probaría la función “Obtener indicaciones” de Google Maps?

13

(Me imagino que esto sería una buena pregunta de la entrevista , pero en mi caso es más pragmático que eso.)

Tenemos un large & Aplicación compleja que modela un proceso de reacción química extremadamente largo y sofisticado entre docenas de componentes químicos. Estamos en la etapa de diseño de Pruebas de Aceptación para la aplicación, pero estamos un tanto intimidados por el número intratable de posibles rutas a probar. Se me ocurrió que nuestra situación es muy parecida a la que debió enfrentar el equipo de desarrollo de Google Maps cuando llegó el momento de probar el algoritmo de planificación de rutas en su función "Obtener instrucciones". Obviamente no pudieron probar (verificar y validar) todas las rutas posibles. Entonces, ¿cómo obtuvieron la confianza de que su aplicación funcionaría en cada situación?

Y dado que no espero descubrir cómo lo hicieron ellos , permítame preguntarle: ¿Cómo usted trataría de diseñar un conjunto de pruebas con una cobertura de códigos adecuada? , para asegurarse de que una aplicación determinada es robusta, ¿cuando es literalmente imposible explorar cada camino potencial a través del sistema?

Lo que busco son los principios que usaría para desglosar un problema intratable en partes más pequeñas y manejables, cuya suma proporciona una estimación satisfactoria del conjunto: "No puedo probar todo, pero Puedo probar esto, esto y esto, y eso es suficiente ". No estoy buscando un enfoque que sea "probablemente correcto", sino uno que sea prudente , dado el presupuesto del mundo real / las limitaciones de tiempo.

(Estoy usando el ejemplo de los mapas de Google como una hoja para solicitar respuestas que sean lo más específicas posible).

    
pregunta kmote 13.08.2012 - 01:13

3 respuestas

10

Trabajé en el campo de la navegación de automóviles hace más de una década.

Paso A) Use un paquete de referencia y seleccione un conjunto de muestra grande, ejecute pruebas A / B. No buscamos exactitud, buscando valores atípicos: el conjunto de referencia mostró Reroute 1234 como 10.34 km, y calculamos 123.5km.

Paso B) - Refinar nuestro software y el software de referencia. - Añadir más muestras y reducir las tolerancias.

Paso C)  - Pruebas internas utilizando conocimiento local a través de conjuntos de datos globales.

Paso D) UAT ... "Prueba de aceptación del usuario" Como en "Venda estas cosas y vea de qué se quejan más los clientes"

Si alguna vez usaste productos de cartografía alrededor de mediados de los años 1990 - 2000, sabes a qué me refiero, aquellos de nosotros que seguimos revisando las instrucciones paso a paso cada vez.

Volver a tu pregunta de ejemplo. Lo que se le pregunta es cómo probar que una pieza de software es correcta. Si desea una prueba matemática, se ha demostrado que se puede hacer: para un software simple a un precio que supera cualquier presupuesto realista, para un paquete de software complejo, bueno, eso es investigación ... La NASA tiene modelos para escribir software altamente confiable dentro de precios económicamente manejables, como lo hacen el Departamento de Defensa y la industria de la aviación, aunque todavía son mucho más altos que los que están dispuestos a pagar. Al final, todo se reduce a cuánto está preparado para pagar ...

Editar: Acabo de releerte OP. Parece que lo que está buscando es una forma rápida y barata de probar la calidad de un software complejo. No se puede probar en calidad. Debe tener un proceso sólido para que sepa que lo que se construye funciona correctamente. Si tiene que pensar en cómo demostrar que es correcto y ya tiene la "aplicación grande y compleja", es demasiado tarde.

    
respondido por el mattnz 13.08.2012 - 06:25
5

Somos uno de los competidores de Google. Nuestra respuesta? Básicamente dos.

Primero, calculamos la solución completa de dirección a dirección. Sí, eso es una gran matriz. Peor aún, lo hacemos para todos los momentos del día, todos los días de la semana. Hay suficiente similitud en el dominio de entrada para almacenar en caché los resultados intermedios, lo que hace que el problema sea manejable. Sin embargo, intente obtener una tasa mayor en los discos duros.

Tenga en cuenta que este cálculo fuera de línea se realiza utilizando un algoritmo diferente. Utiliza mucha más memoria que el algoritmo que intentamos probar, pero no linealmente más (es decir, utiliza menos de 1000 veces más memoria al calcular mil rutas).

En segundo lugar, los usuarios participantes nos proporcionan resultados reales. Validamos millones de rutas impulsadas. ¿Las rutas reales son tan rápidas como se predijo?

Y seguro, encuentras errores de esa manera. Todos los tiempos. P.ej. un tramo de carretera que está delimitado en ambos lados por una "zona de tráfico local" *. Solo hay una forma;) que lo encontrará en las pruebas, y es cuando planifica una ruta a esa carretera en particular.

* Solo se puede usar una "zona de tráfico local" cuando está comenzando o terminando una ruta en esa zona. Por lo tanto, el tramo en el medio se desconecta de la red de carreteras principal. Esto es una falla de zonificación o un mapa.

    
respondido por el MSalters 13.08.2012 - 13:59
3

No es como si Google escribiera un código separado para cada par de direcciones en el mundo. Con la excepción de las heurísticas que se inician a una escala mayor, el algoritmo para un viaje de 3 patas es exactamente el mismo que para una de 3000 patas. Prueba a fondo las rutas más cortas y usa la inducción para mostrar que las pruebas también se aplican a las rutas más largas.

Escoges una muestra saludable de rutas del mundo real y la verificas contra lo que se le ocurre a un humano. Usted le presta a mucha atención a los comentarios de los usuarios finales en sus primeras versiones y le facilita la provisión. Prueba las condiciones de contorno, como si la mejor ruta realmente requiere viajar lejos del destino por un tiempo, o si la ruta más corta por distancia tiene 18 vueltas en comparación con una ruta más directa que es un poco más larga. Realiza pruebas negativas, como si estuviera tratando de conducir de California a Hawai, y se asegura de que los huevos de Pascua inteligentes estén en su lugar.

    
respondido por el Karl Bielefeldt 13.08.2012 - 05:50

Lea otras preguntas en las etiquetas