Ayer me encontré con un problema en el aula (clase orientada a los negocios, no informática) y lo encontré interesante desde una perspectiva algorítmica.
El problema es más o menos así:
suponga que hay un taller con N habitaciones diferentes y que tiene N departamentos diferentes que necesitan ir en esas habitaciones. Los departamentos y las habitaciones son del mismo tamaño, por lo que cualquier departamento puede entrar en cualquier habitación. Hay una distancia de viaje conocida de cada habitación a la otra habitación. También hay una cantidad conocida de viajes necesarios de un departamento a otro (los viajes se cuentan de la misma manera, independientemente de la habitación de donde provengan, por lo que un viaje de A a B es equivalente a un viaje de B a A). Dadas esas entradas, determine un diseño de departamentos en habitaciones que minimice el tiempo de viaje.
¿Cuál es la mejor manera de abordar este problema algorítmicamente? ¿Existe ya un algoritmo particular o una clase de algoritmos diseñados para resolver este tipo de problema? ¿Este tipo de problema tiene un nombre en informática?
No estoy buscando que diseñe un algoritmo para resolver esto, aunque siéntase libre de hacerlo si lo desea. Me pregunto si este es un espacio problemático que ya ha sido bien definido y estudiado algorítmicamente y, de ser así, obtenga algunos enlaces para investigar más. Puedo ver muchas estructuras de datos y algoritmos diferentes que podrían aplicarse a esto y tengo curiosidad por saber qué enfoque sería el "mejor".
Y no te preocupes, no estás haciendo mi tarea por mí. Este no es un problema de tarea en sí mismo, ya que este es un curso de negocios y simplemente estábamos discutiendo los conceptos y no tratando de resolver el problema algorítmicamente.
fuente
Respuestas:
Esto se llama Problema de ubicación de la instalación , que es un problema NP-difícil . La solución algorítmica típica para tal problema es usar algoritmos de aproximación .
fuente
Una solución pragmática:
1) distribuya todos los departamentos al azar (coloque los nombres de los departamentos en una casilla y saque la combinación con el número de habitaciones); 2) dar a todos los empleados zapatos nuevos 3) medir el consumo de zapatos (suelas y tacones) después de dos semanas 4) colocar los departamentos cuyos zapatos de empleados muestran un consumo importante directamente cerca 5) repetir este método n veces (n = la cantidad de departamentos ) 6) después de n pruebas, medirá el promedio del consumo de zapatos y sabrá cuál es la mejor distribución de departamentos. Pero si estuviera en su lugar, haría esta prueba como una experiencia mental con la ayuda de algoritmos (solo tiene que formalizar este procedimiento, si es bueno en matemáticas ya adivina cómo ... si no lo descubre)
fuente
La forma más simple es: obtener el diseño civil del edificio, marcar las ubicaciones de los departamentos con una hoja gráfica (la mejor manera es usar Auto CAD o cualquier otro software 2D / 3D). Luego debe evaluar cuánto espacio tiene y cómo desea ubicar los departamentos. Desde la hoja, puede obtener las distancias de viaje entre departamentos.
fuente