¿Cómo resolver el problema del Puente de cuerda con un algoritmo?

Question

Me preguntaba si este problema de puente de cuerda podría resolverse con una búsqueda de algoritmo de gráficos:

Mi intuición dice DFS, pero ¿cómo debo definir los estados? (Esto es, si DFS es aún el camino a seguir.)

Rope Bridge

Answer 1

se supone Esta tarea que hay que resolver sin una computadora.

Sin embargo, si generaliza el caso, entonces, supongo que puede hacerlo con la búsqueda de gráficos, pero debe tener en cuenta el tamaño del gráfico. Si cada vértice es el "estado", entonces el número de estos estados se estima como 2 ^N ⋅L, donde N es el número de personas y L es la longitud de la linterna. Cada estado contiene información, de qué lado está cada persona, y de la duración restante de la linterna. Si hay un camino desde el estado inicial hasta uno de esos estados donde todos están del lado del campamento, entonces este camino es la solución.

Esa es la manera más obvia de crear estados, pero quizás pueda hacerlo de una manera más eficiente (el número actual de estados, por lo tanto, el tiempo de ejecución, es exponencial al tamaño de entrada).

Sin embargo, para los tamaños tan pequeños como en la muestra que proporcionó, el tiempo de ejecución exponencial (con gráficos) es aceptable. Al entrevistador puede gustarle, si sugiere una solución programática en lugar de hacerlo a mano.

Answer 2

Es posible que desee mirar EWD 1255.