Problema de classificação da pasta - Por favor, ajude a categorizar

5

Eu tenho um problema para o qual estou desenvolvendo uma solução e atualmente resolvo isso com uma solução de força bruta que verifica todas as possibilidades. Ele funciona para um pequeno número de caixas, mas eu gostaria de trabalhar com uma velocidade razoável para números crescentes, no entanto, o algoritmo que eu uso (força bruta) aumenta no tempo de computação de maneira fatorial, relacionado ao número de caixas. Em outras palavras, fica muito lento muito rapidamente após cerca de 6 ou 7 caixas. Eu gostaria de classificar o problema para ver se é NP-Complete, NP-Hard ou outro, então eu sei onde procurar na tentativa de otimizar.

O problema básico é este.

Você tem um número de pontos n e você tem pesos para esses pontos. Os pontos também têm uma ordem tal que os pontos em uma caixa devem ser consecutivos. Você deve colocá-los em um total de no máximo k bins. As caixas contêm uma estimativa para o conjunto de pontos colocados nele e o erro total do valor absoluto da diferença nos pontos e a estimativa deve ser minimizada. O objetivo é descobrir como colocar esses pontos nos compartimentos para ter o erro total mínimo.

Obrigado!

    
por CodeMonkey42 12.07.2013 / 22:26
fonte

2 respostas

1

Apenas uma ideia: trocar aleatoriamente itens em compartimentos, algo assim:

using System;
using System.Linq;
using System.Collections.Generic;

namespace BinsGenetic
{
    class Program
    {
        private const int NumberOfBins = 10;
        private const int NumberOfPoints = 100000;
        private const int MinimalPoint = 1;
        private const int MaximalPoint = 1000;
        private const int NumberOfSwaps = 10000;

        static void Main()
        {
            // Generate empty bins.
            var bins = new List<Bin>();
            for (int i = 0; i < NumberOfBins; i++)
            {
                bins.Add(new Bin(i + 1));
            }

            // Generate 100 points with weight from 1 to 10.
            var points = new List<int>();
            var rnd = new Random();
            for (int i = 0; i < NumberOfPoints; i++)
            {
                points.Add(rnd.Next(MinimalPoint, MaximalPoint));
            }

            // Insert points into bins by random order.
            int c = 0;
            foreach (var point in points.OrderBy(p => p))
            {
                bins[c].Add(point);
                c++;
                if (c % NumberOfBins == 0) c = 0;
            }

            Console.WriteLine("Initial:");
            Test(bins);

            // Get max and min bin.
            for (int i = 0; i < NumberOfSwaps; i++)
            {
                var b1 = bins[rnd.Next(0, NumberOfBins)];
                var b2 = bins[rnd.Next(0, NumberOfBins)];

                var p1 = b1.Points[rnd.Next(0, b1.Points.Count)];
                var p2 = b2.Points[rnd.Next(0, b2.Points.Count)];

                var initialSumBin1 = b1.Points.Sum(p => p);
                var initialSumBin2 = b2.Points.Sum(p => p);
                var initialDiff = Math.Abs(initialSumBin1 - initialSumBin2);

                b1.Add(p2);
                b2.Remove(p2);
                b2.Add(p1);
                b1.Remove(p1);

                var finalSumBin1 = b1.Points.Sum(p => p);
                var finalSumBin2 = b2.Points.Sum(p => p);
                var finalDiff = Math.Abs(finalSumBin1 - finalSumBin2);

                if (finalDiff < initialDiff)
                {
                    Console.WriteLine("Optimized {0}:", i);
                    Test(bins);
                }
                else
                {
                    b1.Add(p1);
                    b2.Remove(p1);
                    b2.Add(p2);
                    b1.Remove(p2);
                }
            }

            Console.WriteLine("Final:");
            Test(bins);

            Console.ReadKey();
        }

        private static void Test(List<Bin> bins)
        {
            // Test.
            for (int i = 0; i < bins.Count; i++)
            {
                Console.Write("Bin {0}, Count: {1}, Sum:{2}, Points:", i + 1, bins[i].Points.Count, bins[i].Points.Sum(p => p));
                //foreach (var point in bins[i].Points.OrderByDescending(p => p))
                //{
                //    Console.Write("{0} ", point);
                //}
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }

    class Bin
    {
        public readonly List<int> Points;
        public int Id { get; private set; }

        public Bin(int id)
        {
            Points = new List<int>();
            Id = id;
        }

        public void Add(int point)
        {
            Points.Add(point);
        }

        public void Remove(int point)
        {
            Points.Remove(point);
        }
    }
}

Mas eu não tenho idéia de como definir o NumberOfSwaps const. Neste exemplo, eu o testei ... É claro que você não pode ter certeza de que obteve o resultado ideal.

Mas, para algoritmos mais avançados / acadêmicos / prontos para produção, você pode começar sua pesquisa aqui: Problema de empacotamento

    
por 14.07.2013 / 13:15
fonte
0

Esse problema pode ser resolvido exatamente em tempo polinomial usando programação dinâmica. Seja E [<> i, b ] o menor erro possível nos escaninhos b , b + 1 , .. ., k quando essas caixas contêm itens i , i +1, ..., n e nenhum outro . Observe que desejamos calcular E [1,1], o que faremos tabulando todos os valores E [ i, b ] para 1 & leq; i & leq; n e 1 & leq; b & k .

Vou escrever c [ b ] para a capacidade do b 'th bin, w [ i ] para o peso do item i 'e w [ i, j ] para w [ i ] + ... + w [ j ].

Primeiro, observe que, para qualquer i , E [ i, k ] = | w [ i, n ] - c [ k ] | porque esse é o único erro possível ao colocar todos os itens i através de n no bin k . Para calcular E [<> i, b ] para alguns b < k , observe que ou colocamos itens i , ..., j (para alguns j & geq; i ) em bin b e itens j +1, ..., n em compartimentos b +1, .. ., k ; ou colocamos todos os itens i , ..., n em compartimentos b +1, ..., k . Portanto,

E [ i, b ] = min ({ E [ i, b +1]} | {| w [ i, j ] - c [ b ] | + E [ j +1, b +1]: i }

Como cada E [<> i, b ] depende apenas dos valores E [ i ', b' ] para i '> i e b '> b , podemos apenas calculá-los em ordem decrescente de b e i . Então, podemos calcular E [1,1] no tempo algo como O (n 2 k) . Como a entrada contém os pesos n e k , a entrada tem comprimento pelo menos nk , então este é um verdadeiro algoritmo de tempo polinomial (como distintos dos algoritmos pseudo-polinomiais que você normalmente obtém para problemas de empacotamento).

    
por 31.12.2015 / 22:29
fonte