Hoy le encargaron a Troty hacer un programa para que calculase la mejor distribución posible de los asistentes a la cena de negocios organizada por Marqueze en Madrid.
Es un problema complicado de resolver, disponemos de unas listas de preferencias de asistentes con los que quieren sentarse, con los que no quieren sentarse y con los indiferentes.
He estado dandole vueltas al asunto, se me ocurren dos formas de hacerlo: Una aplicando un metodo voraz, en la que va calculado la mejor mesa, luego elimina esos comensales y pasa a la siguiente mesa. Hasta terminar con todo.
Otra, más complicada y en tiempo de calculo no creo que sea factible (problema de orden factorial, 111!) es la de calcular todas las posibilidades.
Es un problema complicado de resolver, disponemos de unas listas de preferencias de asistentes con los que quieren sentarse, con los que no quieren sentarse y con los indiferentes.
He estado dandole vueltas al asunto, se me ocurren dos formas de hacerlo: Una aplicando un metodo voraz, en la que va calculado la mejor mesa, luego elimina esos comensales y pasa a la siguiente mesa. Hasta terminar con todo.
Otra, más complicada y en tiempo de calculo no creo que sea factible (problema de orden factorial, 111!) es la de calcular todas las posibilidades.
Se podría resolver aplicando Backtraquing (recursividad) aunque el coste del algoritmo sería del orden de 2^n ya que prueba todos los caminos posibles.
ResponderEliminarOtro número tela de grande :-)
ResponderEliminar