¿Puede resolverse el problema del "lobo cabrío" mediante programación entera?

Question

Pregunta:

¿Puedes resolver el problema de " coles de cabra lobo " mediante programación entera.

Si es así, ¿podría obtener un esquema de la solución o una referencia a una?

Answer 1

Vale, picaré.

Podría implementar esto utilizando el concepto de "inventario". Después de cada viaje tenemos: $$ inv_{trip,side,item} = inv_{trip-1,side,item} + delivered_{trip,side,item} - takenaway_{trip,side,item} $$ También tenemos el inventario inicial y el inventario final requerido. Las ecuaciones son así:

Las ecuaciones para prohibir ciertas configuraciones son similares a las que sugerí aquí .

Las principales decisiones parecen:

----     64 VARIABLE pax.L  items taken on each trip

                 wolf        goat     cabbage

trip1.L2R                       1
trip2.L2R           1
trip2.R2L                       1
trip3.L2R                                   1
trip4.L2R                       1