Problema de repartiment en contenidors
En el problema de repartiment en contenidors, es deuen distribuir artículs de diferents tamanys en una série de contenidors, tenint en conte que cada u d'ells deu contindre un o varis elements que completen a lo manco un tamany mínim determinat, de manera que s'maximizar el número total de contenidors utilisats.
Un eixemple seria obtindre el màxim número possible de cistelles de regal el contingut del qual supere un valor mínim, a partir d'una série de productes de diferents preus disponibles en distintes cantitats.
Este problema és el dual del problema d'empaquetat en contenidors: en el problema del repartiment en contenidors, l'objectiu és maximizar el seu número imponent el volum mínim del conjunt d'artículs que deu estajar cada u; mentres que en el problema de l'empaquetat en contenidors, l'objectiu és minimisar el número de contenidors necessari per a estajar tots els artículs.[1]
El problema és NP-difícil, pero existixen varis algoritmes d'aproximació eficients:
- Algoritmes que cobrixen a lo manco la mitat, dos terços o tres quartos del reconte òptim de contenidors de forma asintòtica, eixecutant-se en el temps respectivament.[1][2]
- Un esquema d'aproximació de temps polinòmic (PTAS) asintòtic, algoritmes en comportament acotat en el pijor dels casos, el comportament esperat dels quals és asintóticamente òptim per a algunes distribucions discretes, i un algoritme d'aprenentage en comportament esperat asintóticamente òptim per a totes les distribucions discretes.[3]
- Un esquema d'aproximació de temps completament polinòmic (FPTAS) asintòtic.
Algoritme bidireccional de repartiment en contenidors
Csirik, Frenk, Lebbe i Zhang[2]<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: 16–19 presenten el següent algoritme simple per a l'aproximació 2/3. Suponga's que el tamany del contenidor és 1 i hi ha n elements.
- Ordenar els elements del major (1) al menor (n).
- Completar un contenidor en els elements més grans: 1, 2, ..., m, a on m és el sancer més gran per al que la suma dels elements 1, ..., m és menor que 1.
- Afegir a este contenidor els elements més menuts: n, n-1, ..., fins que el seu valor supere 1.
Per a qualsevol instància I, denote's per el número de contenidors en la solució òptima i per el número de contenidors completats en l'algoritme de repartiment bidireccional. Llavors, , o equivalentemente, .
Demostració
Per a la demostració, s'utilisa la següent terminologia:
- el número de contenidors completats per l'algoritme.
- els t contenidors completats per l'algoritme.
- Elements inicials: els t elements que s'inserten primer en cada u dels t contenidors.
- Elements finals: els t elements que s'inserten al final de cada u dels t contenidors.
- Elements intermijos: tots els elements que no són ni inicials ni finals.
- := el número d'elements finals que són com a màxim 1/2 (equivalentemente, és el número d'elements finals majors que 1/2).
La suma de cada contenidor és a lo manco 1, pero si s'elimina l'element final, la suma restant és menor que 1. Cada u dels primers contenidors conté un element inicial, possiblement alguns elements intermijos i un element final. Cada u dels últims contenidors conté solament un element inicial i un element final, ya que abdós són majors que 1/2 i la seua suma ya és major que 1.
La demostració considera dos casos.
El cas fàcil és , és dir, tots els elements finals són menors que 1/2. Llavors, la suma de cada completat és com a màxim 3/2, i la suma dels elements restants és com a màxim 1, per lo que la suma de tots els elements és com a màxim . Per un atre costat, en la solució òptima, la suma de cada contenidor és a lo manco 1, per lo que la suma de tots els elements és a lo manco . Per lo tant, és lo requerit.
El cas difícil és , és dir, alguns elements finals són majors que 1/2. Ara es demostra l'existència d'una cota superior en presentant-la com una suma a on:
- els contenidors òptims sense elements inicials/finals (sol elements intermijos).
- els contenidors òptims en exactament un element inicial/final (i alguns elements intermijos).
- els contenidors òptims en dos o més elements inicials/finals (i alguns elements intermijos).
Primer cal centrar-se en els contenidors òptims en i . S'establix una biyección entre els elements en cada contenidor per a alguns elements en que són a lo manco evaluables.
- L'element inicial/final de les categories s'assigna a l'element inicial de . Es deu tindre en conte que estos són els elements inicials més grans.
- Els elements intermijos de les categories i s'assignen als elements intermijos de , considerant que estes categories contenen tots els elements intermijos.
- Per lo tant, tots els elements de i s'assignen a tots els elements no finals de , més tots els elements intermijos de .
- La suma de cada categoria sense el seu element final és menor que 1. Ademés, l'element inicial és major que 1/2, per lo que la suma de solament els elements intermijos és menor que 1/2. Per lo tant, la suma de tots els elements no finals de , més tots els elements intermijos de , és com a màxim .
La suma de cada categoria òptima és a lo manco 1. Per lo tant: , lo que implica . Ara, es posa el foc en els contenidors òptims en i .
- El número total d'elements inicials/finals en els contenidors i és a lo manco , pero el seu número total també és , ya que hi ha exactament dos elements inicials/finals en cada contenidor. Per lo tant, .
- La suma de les dos últimes desigualtats implica que , lo que a la seua volta comporta que .
Estrechez
El factor 2/3 és ajustat per a BDF. Considere's la següent instància (a on és suficientment menut):
BDF inicializa el primer contenidor en l'element més gran i ho completa en els elements més menuts. En conseqüència, els elements restants solament poden cobrir contenidors en triplets, per lo que, en total, es completen contenidors. No obstant, en OPT es poden completar contenidors, cada u dels quals conté dos elements mijans i dos menuts.
Algoritme de repartiment en contenidors en elements de tres classes
'Csirik, Frenk, Lebbe i Zhang[2]<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: 19–24 presenten un atre algoritme que conseguix una aproximació de 3/4. L'algoritme ordena els elements de major a menor i els dividix en tres classes:
- X: Elements en un tamany d'a lo manco 1/2;
- I: Elements en un tamany menor a 1/2 i a lo manco 1/3;
- Z: Elements en un tamany menor a 1/3.
L'algoritme funciona en dos fases:
Fase 1:
- Inicializar un nou contenidor en l'element més gran de X o en els dos elements més grans d'I, el que siga major. Tinga's en conte que, en abdós casos, la suma inicial dels contenidors és menor que 1.
- Completar el nou contenidor en elements de Z en orde creixent de valor.
Repetir fins que X O I o Z estiguen buits.
Fase 2:
- Si X O I està buit, completar els contenidors en elements de Z per mig de la regla simple del següent ajust.
- Si Z està buit, destinar els elements restants en X per parells i els restants en I per triplets.
En l'eixemple anterior, que mostra la estrechez de BDF, els conjunts són:
TCF alcança el resultat òptim, ya que inicializa tots els contenidors en parells d'elements d'I i els completa en parells d'elements de Z.
Per a qualsevol instància I, denote's com el número de contenidors en la solució òptima i com el número de contenidors completats en l'algoritme de repartiment en tres classes d'artículs. Després, .
El factor 3/4 determina la estrechez per al procediment TCF. Considere's el següent eixemple (a on és suficientment menut):
El TCF inicializa el primer contenidor en els dos elements més grans i ho completa en els elements més menuts. Llavors, els elements restants solament poden cobrir contenidors en grups de quatre, per lo que, en total, es completen contenidors. No obstant, en la tècnica OPT es poden completar contenidors, cada u en 3 elements mijans i 3 menuts.
Referències
- ↑ 1,0 1,1 Assmann, S. F.; Johnson, D. S; Kleitman, D. J; Leung, J. Y. -T(01 de decembre de 1984).«On a dual version of the one-dimensional bin packing problem».Journal of Algorithms.5(4): 502–525.ISSN 0196-6774.doi:10.1016/0196-6774(84)90004-X.(en en)
- ↑ 2,0 2,1 2,2 Csirik, János; J. B. G. Frenk and M. Labbé and S. Zhang(01 de giner de 1999).«Two simple algorithms for bin covering».Acta Cybernetica.14(1): 13–25.ISSN 2676-993X.(en en)
- ↑ Csirik, Janos; Johnson, David S.; Kenyon, Claire(09 de giner de 2001).«Better approximation algorithms for bin covering».Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms.Society for Industrial and Applied Mathematics.Washington, D.C., USA:: 557–566.
Referències
- Este artícul conté una traducció derivada de «Problema de reparto en contenedores» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.