¡Buena noches! Realmente estoy haciendo una pasantía en los Archivos Nacionales de Francia y me encontré con una situación que quería resolver usando gráficos ...
I. La situación polvorienta
Queremos optimizar la disposición de los libros de mi biblioteca de acuerdo con su altura para minimizar su costo de archivo. La altura y el grosor de los libros son conocidos. Ya organizamos los libros en orden ascendente de altura (no sé si fue lo mejor, pero ... así fue como lo hicimos). Conociendo el grosor de cada libro, podemos determinar para cada clase de H i el grosor necesario para su disposición, llámelo L i (por ejemplo, los libros que son H i = 23 altura podría tener un espesor total L i = 300 ).
La biblioteca puede fabricar estanterías a medida, indicando la longitud y altura deseadas (no hay problema con la profundidad). Un estante de altura y longitud x i cuesta F i + C i x i , donde F i es un costo fijo y C i es el costo del estante por unidad de longitud.
Tenga en cuenta que un estante de altura puede usarse para almacenar libros de altura H j con j ≤ i . Queremos minimizar el costo.
Mi tutor me sugirió que modelara este problema como un problema de búsqueda de ruta. El modelo puede involucrar vértices indexados de 0 a n . Mi mentor me sugirió que resolviera las condiciones existentes, cada significado de borde y cómo calcular la valoración v ( i , j ) asociada al borde ( i , j ) . También estaría de acuerdo con otras soluciones, así como con ideas.
Por ejemplo, tenemos para la Convención (un período oscuro de la historia de Francia) tal matriz:
II Las suposiciones de un ratón de biblioteca aprendiz
Creo que tengo que calcular un algoritmo entre Djikstra, Bellman o Bellman-Kalaba ... Estoy tratando de averiguar cuál en las siguientes subsecciones.
1.condiciones
Estamos aquí con un problema de pathfinding entre un vértice y un vértice n , n debe ser saliente desde 0 (es decir, debe existir un camino (o una caminata) entre 0 y n
2.Qué calcular (actualizado (25/10/2015))
// Trabajar todavía en proceso hasta donde no sé a qué vértices y qué bordes modelar ...
Mi mejor conjetura
Creo que nos deshacemos de al menos un tipo de estantes cada vez que encontramos un camino más corto desde la matriz, pero eso es solo mi suposición ...;).
Creo que la mejor manera de modelar cómo comprar estanterías y almacenar nuestros libros debe parecerse al siguiente gráfico (pero, por favor, ¡no dude en criticar mi método!;))
vértices:
- son estantes que podemos usar para almacenar nuestros libros.
- es el estado donde no se almacena ningún libro. El uso de este vértice me permite usar las fórmulas de cada costo (aristas).
bordes: son el costo usando un tipo de estantería. por ejemplo: F 1 + C 1 x 1 fom 0 es el costo usando solo estantes tipo 1 para almacenar nuestros pergaminos, manuscritos ...
Sin embargo, desde aquí no sé cómo crear mi problema de ruta más corta.
De hecho, no sabría dónde habría guardado todos mis libros.
Esto me lleva a otra idea ...
otra idea...
Aquí, estoy buscando la ruta más corta desde un vértice dado hasta el estado 0, es decir, sabiendo que el documento más alto es alto, estoy buscando la forma más barata de organizar mis documentos.
vértices:
- son estantes que podemos usar para almacenar nuestros libros.
- es el estado donde se almacenan todos los libros. El uso de este vértice me permite usar las fórmulas de cada costo (aristas).
3. Cómo calcular
Creo que tenemos que comenzar con los estantes más altos hasta donde podamos almacenar los libros más pequeños ...
Hacer
Mientras yo> <0
Finalmente, no sé cómo hacer que x varíe ...
fuente
Respuestas:
Te veo preguntando: "Quiero resolver esto con el algoritmo de Dijkstra, pero no puedo configurar un buen gráfico para ejecutar", por lo tanto, te presentaré dicho gráfico.
Un dígrafo donde los vértices son conjuntos de libros archivados.
fuente
Int
mayor que1
. Esto lleva a una gráfica den^2
vértices. Cuando está buscando una ruta entre A y B y todos los pesos de los bordes son positivos, entonces no hay diferencia entre Dijkstra y Bellman-Kalaba, excepto que Bellman-Kalaba siempre está tratando de actualizar los bordes que no necesitan actualización; Dijkstra simplemente almacena punteros a los vértices que le importan.Creo que tengo una solución a tu problema. Espero no haber entendido mal algo en la definición de su problema. Aquí va:
Probemos las siguientes dos cosas:
De las dos cosas que hemos probado, B es la significativa.
Por último, como dije antes, como los libros son grandes, no se puede usar el algoritmo para cada libro. Creo que representar su altura por la suma de su grosor debería ser el truco. (Creo que ya es así por tu declaración)
(Supongo que el número de alturas diferentes es mucho menor que el número de libros)
fuente
A veces, simplemente "acercarse" al "problema más cercano" en la literatura puede ayudar a comprender la teoría y los antecedentes detrás del problema, construir una abstracción y eliminar detalles espurios. El problema más cercano en la literatura al suyo parece ser lo que se conoce como "problema de empaque de contenedores de tamaño variable". Ejemplos de documentos se incluyen a continuación. Este problema está muy estudiado teóricamente y existe un software estándar que se muestra en la optimización de cajas de embalaje en, por ejemplo, contenedores de envío de camiones. También hay versiones en las que se puede ajustar el tamaño del contenedor. Hay muchos enfoques algorítmicos. por ejemplo, del 1er papel:
OPTIMIZAR EL EMBALAJE DE BANDEJA TRIDIMENSIONAL MEDIANTE SIMULACIÓN / Dube, Kanavathy
Problema de embalaje del contenedor con volúmenes y capacidades inciertos / Peng, Zhang
Algoritmos de embalaje de contenedores 3D , stackoverflow
fuente