Otimizando pedidos cartesianas com custos afins

https://stackoverflow.com/questions/1403933

05-07-2019
|

Pergunta

Eu tenho um pedido a otimização de custos que eu não sei como se há literatura sobre. É um pouco difícil de explicar, então eu peço desculpas antecipadamente para o comprimento de questão.

Há um servidor que eu estou acessando que funciona da seguinte forma:

uma solicitação é feita em registros (R1 ... RN) e campos (f1, ... fp)
você só pode solicitar o produto cartesiano (r1, ..., rp) x (f1, ... fp)
O custo (tempo e dinheiro) associado a um tal pedido um é afim no tamanho do pedido:

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

Sem perda de generalidade (apenas através da normalização), podemos assumir que b=1 por isso o custo é:

T((r1, ...,rn)x(f1,...fp)) = a + n * p

Eu preciso apenas para solicitar um subconjunto de pares (r1, f(r1)), ... (rk, f(rk)), um pedido que vem dos usuários. Meu programa atua como um intermediário entre o usuário eo servidor (que é externo). Eu tenho um monte de pedidos como este que vêm em (dezenas de milhares por dia).

Graficamente, podemos pensar nisso como uma matriz p escassa n x, para o qual eu quero cobrir os valores diferentes de zero com uma submatriz retangular:

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

Tendo:

o número de submatrizes sendo mantido razoável por causa do custo constante
todo o 'x' deve situar-se dentro de uma submatriz
a área total coberta não deve ser muito grande por causa do custo linear

vou citar g o coeficiente de escassez do meu problema (número de pares necessários sobre o total de pares possíveis, g = k / (n * p). Eu sei que a a coeficiente.

Existem algumas observações óbvias:

se um é pequeno, a melhor solução consiste em solicitar cada par (ficha, campo) de forma independente, e o custo total é: k * (a + 1) = g * n * p * (a + 1)
Se um é grande, a melhor solução é pedir o produto cartesiano, eo custo total é: a + n * p
A segunda solução é melhor assim que g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
, claro, os pedidos feitos nos produtos cartesianos não são importantes, para que eu possa transpor as linhas e as colunas da minha matriz para torná-lo mais facilmente cobertos, por exemplo:

   f1 f2 f3
r1  x    x
r2     x 
r3  x    x

pode ser reordenada como

   f1 f3 f2
r1  x  x
r3  x  x
r2       x

E há uma solução ideal que é a solicitação (f1,f3) x (r1,r3) + (f2) x (r2)

Tentando todas as soluções e procurando o menor custo não é uma opção, porque os combinatória explodir:

for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

então eu estou procurando uma solução aproximada. Eu já tenho algum tipo de algoritmo guloso que encontra uma cobertura dada uma matriz (começa com células unitárias, em seguida, junta-se a proporção de célula vazia na fusão é inferior a algum limiar).

Para colocar alguns números em mente, meu n está em algum lugar entre 1 e 1000, e meu p algum lugar entre 1 e 200. O padrão de cobertura é realmente 'blocos', porque os registros vêm em classes para as quais os campos solicitados são semelhantes . Infelizmente, não posso acessar a classe de um registro ...

Pergunta 1 : Tem alguém uma idéia, uma simplificação inteligente, ou uma referência para um papel que poderia ser útil? Como tenho um monte de pedidos, um algoritmo que funciona bem , em média, é o que estou procurando (mas eu não posso pagar para o trabalho muito mal em algum caso extremo, por exemplo solicitando a toda matriz quando n e p são grandes, eo pedido é realmente muito escassa).

Pergunta 2 : Na verdade, o problema é ainda mais complicado: o custo é de fato mais como a forma: a + n * (p^b) + c * n' * p', onde b é uma constante <1 (uma vez que um registro for solicitado para uma campo, não é muito caro para pedir outros campos) e n' * p' = n * p * (1 - g) é o número de células que não querem solicitação (porque eles são inválidos, e há um custo adicional em pedir coisas inválidos). Eu não posso sequer sonhar em encontrar uma solução rápida para este problema, mas ainda assim ... uma idéia alguém?

Solução

Selecionar as submatrizes para cobrir os valores solicitados é uma forma de o conjunto cobrindo problema portanto, NP completar. Seu problema acrescenta a este problema já dura que os custos dos conjuntos diferentes.

Que você permitir que a permutar as linhas e colunas não é um problema tão grande, porque você pode apenas considerar submatrizes desconectados. Remar um, colunas 4-7 e linha de cinco, colunas quatro dois sete são um conjunto válido porque você pode apenas linha de swap dois e fileira cinco e obter o conectado uma linha submatrix, coluna quatro para a linha dois, coluna sete. Claro que isso irá adicionar algumas restrições - não todos os conjuntos são válidos em todas as permutações - mas eu não acho que este é o maior problema

O artigo da Wikipedia dá os resultados inapproximability que o problema não pode ser resolvido em tempo polinomial melhor então com um 0.5 * log2(n) fator onde n é o número de sets. No seu caso 2^(n * p) é um (muito pessimista) limite superior para o número de conjuntos e os rendimentos que você só pode encontrar uma solução até um factor de 0.5 * n * p em tempo polinomial (além N = NP e ignorando os custos variável).

Um otimista limite inferior para o número de conjuntos ignorando permutações de linhas e colunas é 0.5 * n^2 * p^2 produzindo um fator muito melhor do log2(n) + log2(p) - 0.5. Em conseqüência, você só pode esperar encontrar uma solução no seu pior caso de n = 1000 e p = 200 até um factor de cerca de 17 no caso otimista e até um factor de cerca de 100.000 no caso pessimista (ainda ignorando os custos variando).

Assim, o melhor que você pode fazer é usar um algoritmo heurístico (Wikipedia menciona um algoritmo guloso quase ideal) e aceitar que haverá casos em que o algoritmo executa (muito) ruim. Ou você vai para o outro lado e usar um algoritmo de otimização e tentar encontrar uma solução boa estar usando mais tempo. Neste caso, eu gostaria de sugerir tentando usar A * procurar .

Outras dicas

Eu tenho certeza que há realmente um bom algoritmo para esta lá fora em algum lugar, mas aqui estão as minhas próprias idéias intuitivas:

Lance-algumas-retângulos se aproxima:
- Determine um tamanho rectângulo "mais ou menos ideal" com base em a .
- Coloque estes retângulos (talvez aleatoriamente) mais de seus pontos necessários, até que todos os pontos são cobertos.
- Agora pegue cada retângulo e reduzi-lo tanto quanto possível sem "perder" quaisquer pontos de dados.
- Encontre retângulos próximos uns dos outros e decidir se combiná-los seria mais barato do que mantê-los separados.
Grow
- começar com cada ponto em seu próprio retângulo 1x1.
- Localize todos os retângulos dentro de n linhas / colunas (onde n podem ser baseadas em a ); veja se você pode combiná-los em um retângulo para nenhum custo (ou custo negativo: D).
- Repetir.
Encolher
- Comece com um grande retângulo, que cobre todos os pontos.
- Procure uma sub-retângulo que compartilha um par de lados com um dos grandes, mas contém muito poucos pontos.
- Corte-o para fora da grande, produzindo dois retângulos menores.
- Repetir.
Quad
- Divida o avião em 4 retângulos. Para cada um deles, veja se você obter uma melhor relação custo por recursão mais, ou apenas incluindo todo o retângulo.
- Agora pegue seus retângulos e veja se você pode mesclar qualquer um deles com pouco / nenhum custo. \

Além disso: manter em mente que às vezes ele vai ser melhor ter dois sobreposição retângulos do que um grande retângulo que é um super deles. Por exemplo. o caso quando dois retângulos apenas se sobrepõem em um canto.

Ok, o meu entendimento da questão mudou. Novas idéias:

loja cada linha como uma longa bit-string. E pares de bit-strings juntos, tentando encontrar pares que maximizam o número de bits 1. Crescer esses pares em grupos maiores (tipo e tentar igualar as realmente grandes uns com os outros). Em seguida, construir um pedido que vai bater o maior grupo e, em seguida, esquecer todos esses bits. Repita até que tudo feito. Talvez mudar de linhas em colunas, às vezes.
Olhe para todas as linhas / colunas com zero, ou poucos, pontos neles. "Delete"-los temporariamente. Agora você está olhando para o que seria coberto por um pedido que deixa-los fora. Agora, talvez, aplicar uma das outras técnicas, e lidar com as linhas ignoradas / cols depois. Outra maneira de pensar sobre isso é:. Negócio com pontos mais densos em primeiro lugar, e depois passar para os esparsas

Uma vez que seus valores são escassos, pode ser que muitos usuários estão pedindo valores semelhantes? É o cache dentro de sua aplicação uma opção? Os pedidos podem ser indexados por um hash que é uma função da posição (x, y), de modo que você pode facilmente identificar conjuntos em cache que se enquadram na área correta da grade. Armazenar os conjuntos em cache em uma árvore, por exemplo, permitiria que você encontrar subconjuntos mínimos em cache que cobrem a gama pedido muito rapidamente. Você pode então fazer uma pesquisa linear no subconjunto, que é pequeno.

Eu considero os registros de n (linhas) e campos p (cols) mencionados no conjunto solicitação do usuário como n pontos no espaço p-dimensional ({0,1} ^ p) com o om coordenar sendo 1 sse tem um X, e identificar uma hierarquia de grupos , com o conjunto mais grosseira na raiz incluindo todos o X. Para cada nó na hierarquia clustering, considerar o produto que cobre todas as colunas necessárias (isto é linhas (qualquer subnó) x cols (qualquer subnó)). Em seguida, decidir a partir de cima inferior se fundir os revestimentos criança (pagando para toda a cobertura), ou mantê-los como pedidos separados. (As coberturas não são de colunas contíguas, mas exatamente os necessários, isto é pensar em um vetor de bits)

Eu concordo com Artelius que a sobreposição de produtos-solicitações poderia ser mais barato; minha abordagem hierárquica precisaria de melhoria para incorporar isso.

Eu tenho trabalhado um pouco sobre ele, e aqui é um óbvio, O (n ^ 3) ganancioso, simetria algoritmo de quebra (registros e campos são tratados separadamente) em python-como pseudo-código.

A idéia é trivial: começamos por tentar um pedido por registro, e nós fazemos o merge mais digno até que não há mais nada digno de mesclagem. Este algo tem a desvantagem óbvia de que ele não permite que pedidos de sobreposição, mas eu esperar que ele funcione muito bem no caso da vida real (com a função + custo n * (p^b) + c * n * p * (1 - g)):

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

Este é O (n3 * p) porque:

após a inicialização começamos com pedidos n
o loop while remove exatamente um pedido da piscina a cada iteração.
os itera interior laço for no (ni^2 - ni) / 2 pares distintos de pedidos, com ni indo de n para um no pior caso (quando mesclar tudo em um grande pedido).
1. Alguém pode me ajudar a apontar os casos muito maus do algoritmo. Soa reasonnable usar este?
2. É O (n ^ 3) que é demasiado dispendioso para as grandes entradas. Qualquer ideia de otimizá-lo?

Agradecemos antecipadamente!

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow