¿Cuál es el tiempo mínimo requerido para cruzar el puente con los siguientes detalles?

Answer 1

La respuesta es de 29 minutos.

Se me ocurren algunos paradigmas de resolución de problemas que se pueden usar para resolver genéricamente (o, en general). Pero iré con la teoría de grafos para esta respuesta.

Supongamos que los dos lados del puente son X e Y. Supongamos también que | yo | representan el tiempo que le toma a la persona i cruzar el puente donde se extrae del conjunto {A, B, C, D, E, F} . En cualquier instante de tiempo discreto cuando la antorcha está en un lado del puente, podemos representar el estado del sistema con dos conjuntos, cada uno con personas presentes a cada lado del puente. Cada posible estado del sistema es un nodo en nuestro gráfico ponderado donde los bordes son el tiempo requerido para que los transeúntes crucen el puente con la linterna a través de los nodos.

Nuestro estado inicial es {A, B, C, D, E, F} {}, es decir, todos en el lado X y nadie en el lado Y. Desde aquí podemos pasar a los siguientes estados:

{C, D, E, F} {A, B} por {A, B} cruzando el puente a un costo máximo de {| A |, | B |} = 2
o
{A, B, C, D} {E, F} por {E, F} cruzando el puente a un costo máximo de {| E |, | F |} = 10
o
una de las transiciones válidas 6C2 + 6C1 de la forma anterior.

Nuestro gráfico tendrá 64 nodos (un ejercicio en sí mismo, dejado para el lector). Completemos este gráfico. Comience con el nodo inicial y agregue bordes ponderados, donde los pesos son el costo de llegar al nodo objetivo a todos los nodos accesibles desde aquí. Ahora, desde cada nodo accesible v, recurse y agregue bordes a todos los nodos accesibles desde v , hasta que se quede sin nodos accesibles.
Hablando programáticamente:

Inicialice un gráfico g con los 64 nodos posibles
Inicializar una cola q
q.enqueue ({A, B, C, D, E, F} {})
hasta q.empty ()
srcNode = q.dequeue ()
para destNode en todos los nodos accesibles desde srcNode
addDirectedEdge ( g , srcNode , destNode , cost )
q .enqueue ( destNode )

Una vez que haya terminado de llenar el gráfico, la respuesta será la ruta más corta desde el nodo {A, B, C, D, E, F} {} al nodo {} {A, B, C, D, E, F} en este gráfico Puede utilizar el algoritmo de ruta más corta de Dijkstra para encontrarlo.

Aquí está el camino que descubrí:
{A, B, C, D, E, F} {} a {C, D, E, F} {A, B} a un costo de 2
{C, D, E, F} {A, B} a {A, C, D, E, F} {B} al costo 1
{A, C, D, E, F} {B} a {A, C, D} {B, E, F} a un costo de 10
{A, C, D} {B, E, F} a {A, B, C, D} {E, F} a un costo de 2
{A, B, C, D} {E, F} a {C, D} {A, B, E, F} a un costo de 2
{C, D} {A, B, E, F} a {A, C, D} {B, E, F} al costo 1
{A, C, D} {B, E, F} a {A} {B, C, D, E, F} a un costo de 7
{A} {B, C, D, E, F} a {A, B} {C, D, E, F} a un costo de 2
{A, B} {C, D, E, F} a {} {A, B, C, D, E, F} a un costo de 2

Costo total = 2 + 1 + 10 + 2 + 2 + 1 + 7 + 2 + 2 = 29