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 O(n),O(nlog⁡n),O(nlog2n) 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 OPT(I) el número de contenidors en la solució òptima i per BDF(I) el número de contenidors completats en l'algoritme de repartiment bidireccional. Llavors, BDF(I)≥(2/3)OPT(I)−(2/3), o equivalentemente, OPT(I)≤(3/2)BDF(I)+1.

Demostració

Per a la demostració, s'utilisa la següent terminologia:

  • t:=BDF(I)= el número de contenidors completats per l'algoritme.
  • B1,…,Bt:= 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.
  • w := el número d'elements finals que són com a màxim 1/2 (equivalentemente, t−w és el número d'elements finals majors que 1/2).

La suma de cada contenidor B1,…,Bt és a lo manco 1, pero si s'elimina l'element final, la suma restant és menor que 1. Cada u dels primers contenidors w B1,…,Bw conté un element inicial, possiblement alguns elements intermijos i un element final. Cada u dels últims contenidors t−w Bw+1,…,Bt 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 w=t, és dir, tots els elements finals són menors que 1/2. Llavors, la suma de cada Bi 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 3t/2+1. 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 OPT(I). Per lo tant, OPT(I)≤3t/2+1 és lo requerit.

El cas difícil és w<t, és dir, alguns elements finals són majors que 1/2. Ara es demostra l'existència d'una cota superior en OPT(I) presentant-la com una suma OPT(I)=|K0|+|K1|+|K2| a on:

  • K0:= els contenidors òptims sense elements inicials/finals (sol elements intermijos).
  • K1:= els contenidors òptims en exactament un element inicial/final (i alguns elements intermijos).
  • K2:= els contenidors òptims en dos o més elements inicials/finals (i alguns elements intermijos).

Primer cal centrar-se en els contenidors òptims en K0 i K1. S'establix una biyección entre els elements en cada contenidor per a alguns elements en B1,…,Bt que són a lo manco evaluables.

  • L'element inicial/final de les categories K1 s'assigna a l'element inicial de B1,…,B|K1|. Es deu tindre en conte que estos són els elements inicials més grans.
  • Els elements intermijos de les categories K0 i K1 s'assignen als elements intermijos de B1,…,Bw, considerant que estes categories contenen tots els elements intermijos.
  • Per lo tant, tots els elements de K0 i K1 s'assignen a tots els elements no finals de B1,…,B|K1|, més tots els elements intermijos de B|K1|+1,…,Bw.
  • La suma de cada categoria B1,…,Bw 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 B1,…,B|K1|, més tots els elements intermijos de B|K1|+1,…,Bw, és com a màxim |K1|+(w−|K1|)/2=(|K1|+w)/2.

La suma de cada categoria òptima és a lo manco 1. Per lo tant: |K0|+|K1|≤(|K1|+w)/2, lo que implica 2|K0|+|K1|≤w≤t. Ara, es posa el foc en els contenidors òptims en K1 i K2.

  • El número total d'elements inicials/finals en els contenidors K1 i K2 és a lo manco |K1|+2|K2|, pero el seu número total també és 2t, ya que hi ha exactament dos elements inicials/finals en cada contenidor. Per lo tant, |K1|+2|K2|≤2t.
  • La suma de les dos últimes desigualtats implica que 2OPT(I)≤3t, lo que a la seua volta comporta que OPT(I)≤3t/2.

Estrechez

El factor 2/3 és ajustat per a BDF. Considere's la següent instància (a on ϵ>0 és suficientment menut):

1−6kϵ,12−ϵ,…,12−ϵ,ϵ,…,ϵ{⋯6kunidades⋯}{⋯6kunidades⋯}


BDF inicializa el primer contenidor en l'element més gran i ho completa en els 6k elements més menuts. En conseqüència, els elements restants 6k solament poden cobrir contenidors en triplets, per lo que, en total, es completen 2k+1 contenidors. No obstant, en OPT es poden completar 3k 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:

1−6kϵ,12−ϵ,…,12−ϵ,ϵ,…,ϵ{|X|=1}{⋯|Y|=6k⋯}{⋯|Z|=6k⋯}

TCF alcança el resultat òptim, ya que inicializa tots els contenidors 3k en parells d'elements d'I i els completa en parells d'elements de Z.

Per a qualsevol instància I, denote's OPT(I) com el número de contenidors en la solució òptima i TCF(I) com el número de contenidors completats en l'algoritme de repartiment en tres classes d'artículs. Després, TCF(I)≥(3/4)(OPT(I)−4).

El factor 3/4 determina la estrechez per al procediment TCF. Considere's el següent eixemple (a on ϵ>0 és suficientment menut):

12−6kϵ,12−6kϵ,13−ϵ,…,13−ϵ,ϵ,…,ϵ{⋯12kunits⋯}{⋯12kunits⋯}

El TCF inicializa el primer contenidor en els dos elements més grans i ho completa en els 12k elements més menuts. Llavors, els 12k elements restants solament poden cobrir contenidors en grups de quatre, per lo que, en total, es completen 3k+1 contenidors. No obstant, en la tècnica OPT es poden completar 4k contenidors, cada u en 3 elements mijans i 3 menuts.

Referències

  1. ↑ 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. ↑ 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)
  3. ↑ 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