Algoritmo transversal del gráfico con un giro - número mínimo de paradas

Question

Estoy perplejo con este problema de tarea. Creo que tengo la respuesta correcta, pero no estoy seguro de cómo demostrarlo. Tampoco estoy seguro de cómo acercarme a la prueba. Aquí está el problema:

El profesor Gekko siempre ha soñado con el patinaje en línea en todo Dakota del Norte. Planea cruzar el estado en la autopista U.S. 2, que se extiende desde Grand Forks, en la frontera este con Minnesota, hasta Williston, cerca de la frontera occidental con Montana. El profesor puede cargar dos litros de agua y puede patinar millas antes de quedarse sin agua. (Debido a que Dakota del Norte es relativamente plana, el profesor no tiene que preocuparse por beber agua a un ritmo mayor en las secciones cuesta arriba que en las secciones planas o cuesta abajo). El profesor comenzará en Grand Forks con dos litros de agua. Su mapa oficial del estado de Dakota del Norte muestra todos los lugares a lo largo de EE. UU. 2 en los que puede rellenar su agua y las distancias entre estos lugares.

El objetivo del profesor es minimizar el número de paradas de agua a lo largo de su ruta en todo el estado. Proporcione un método eficiente mediante el cual pueda determinar qué agua debe parar. Demuestre que su estrategia arroja una solución óptima y da su tiempo de ejecución.

Creo que debe elegir sus paradas para que llegue a la distancia máxima antes de quedarse sin agua. Es decir, en cada parada, si continuaba, se quedaría sin agua antes de la próxima parada.

No estoy seguro de cómo proceder. Apuesto a que esto ya se ha hecho antes, pero soy bastante nuevo en este campo de CS y podría usar alguna orientación.

Answer 1

Su algoritmo es correcto.

Intente probar lo siguiente por inducción en el número de paradas pasadas. Después de pasar por cada ubicación de agua, ninguna otra estrategia puede haber hecho menos paradas, y de aquellas que hicieron el mismo número de paradas, ninguna otra estrategia puede dejarlo con más agua.

En 0 paradas, todas las estrategias son iguales, por lo que es trivial probar la afirmación.

Si no bebe en una parada bajo esta estrategia, el resultado es fácil de probar.

Si bebes en una parada, por el hecho de que la declaración era cierta en la parada anterior, puedes probar que la otra estrategia hizo más paradas la última vez (por lo tanto, no están adelante en paradas, y pueden ' t estar adelante en el agua ya que acaba de obtener agua), o bien la otra estrategia también debe tener agua también (de lo contrario, se quedarán sin agua antes de la siguiente parada).

Eso es suficiente para completar la prueba de inducción.

Si tiene problemas con el concepto de lo que se requiere para una prueba formal y cómo hacerlo, consulte How I Do Proofs. También escribí en mi blog sobre mi experiencia al usar ese folleto here.

Answer 2

El truco con este tipo de preguntas es indicar el problema como otro problema para el que puede probar algo.

Por ejemplo, para este podría formar un gráfico no ponderado donde las paradas son nodos y tiene una ventaja entre dos nodos si es posible viajar entre ellos sin detenerse. Entonces, todo lo que tienes que hacer es encontrar el camino más corto en el gráfico y listo. Esto está bien si la distancia a recorrer entre paradas es relativamente pequeña, de lo contrario, el gráfico se vuelve muy denso. Sospecho que hay un problema mejor para reducir ya que su camino está en una línea.

Answer 3

Espero que mi primer intento sea realmente eliminado. Estaba mal.

Boceto de prueba: Si el codicioso falló, debe haber sido óptimo llevar una ciudad más cerca del punto de partida (más allá de la línea de meta) que la elegida en algún momento. Ignore el problema hasta esa elección, y observe los dos subproblemas: uno que comienza en la ciudad elegido por codicioso y el otro - que incluye el punto codicioso en el subproblema. Para evitar una contradicción, la ciudad que comienza más lejos de la línea de llegada debe tener una solución óptima con menos saltos que la solución óptima que comienza en el punto codicioso. Ignora cómo llegas a esta solución óptima para ambos subproblemas, solo que existe. Dado que el punto de partida no codicioso incluye el subproblema codicioso, debe tener los mismos saltos de subtrayecto óptimos o más (Demuestre esta afirmación. Puede hacerse por inducción, pero creo que hay una prueba más simple de que yo también soy cansado de pensar. Tal vez solo puede decir que es obvio?). Si eran iguales, entonces el codicioso funcionaba bien. Si son mayores, contradicción.