Eu não sou um teórico da ciência da computação, mas acho que esse problema do mundo real pertence aqui.

O problema

Minha empresa possui várias unidades em todo o país.

Oferecemos aos funcionários a possibilidade de trabalhar em outra unidade. Mas há uma condição: o número total de trabalhadores em uma unidade não pode mudar.

Isso significa: permitiremos que um funcionário saia de sua unidade se alguém quiser seu lugar.

Dados de solicitação de exemplo (ficticious):

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

O acima, plotado: Visualização dos dados acima

Veja como temos que escolher entre as opções vermelha, azul ou preta?

O problema real é um pouco mais complexo, porque temos 27 unidades e 751 solicitações. Por favor, dê uma olhada na visualização

O objetivo

Tendo coletado todos os pedidos, como satisfazer a maioria deles?

Aplicação da teoria (?)

Tendo o gráfico , que cada unidade seja um vértice e uma solicitação seja uma aresta direcionada , uma troca bem-sucedida assumirá a forma de um cyle direcionado. $G(V, E)$ $V$ $E$

Cada ciclo deve usar apenas uma vez ( um trabalhador não pode deixar sua unidade duas vezes ), mas pode visitar várias vezes ( uma unidade pode ter muitos trabalhadores que desejam sair ). $E$ $V$

A questão

Se este problema for expresso como

"Como encontrar os ciclos que, juntos, envolvem o maior número de arestas não compartilhadas em um gráfico direcionado"?

Satisfazeremos a maioria dos solicitantes?

Isso é verdade, existe um algoritmo para encontrar esse conjunto ideal de ciclos?

Essa abordagem greddy resolverá o problema?

Encontre o maior ciclo direcionado em ; $G$
Remova as arestas de ; $G$
Repita 1 até que não haja um ciclo direcionado em ; $G$

Pode me ajudar?

Você conhece outra maneira de descrever o problema original (agradar a maioria dos solicitantes)?

Editar : departamento alterado para unidade, para melhor descrever o problema.

ds.algorithms graph-algorithms application-of-theory motobói
fonte

3

Tem certeza de que deseja evitar o uso da mesma borda mais de uma vez? Pela sua descrição do aplicativo, parece-me que você deve evitar usar o mesmo vértice mais de uma vez, o que é uma condição mais forte.

Tsuyoshi Ito

3

@TsuyoshiIto: Pelo que entendi pela descrição, a condição é que, em cada vértice, o indegree seja igual ao outdegree. Portanto, a desarticulação de vértices não é necessária.

Yoshio Okamoto

7

A propósito, se meu entendimento estiver correto, o problema deve ser solucionado em tempo polinomial por meio do fluxo da rede. Ou seja, se damos uma unidade de lucro para uma unidade de fluxo ao longo de uma borda, e damos uma capacidade unitária em cada borda, o problema é encontrar uma circulação do lucro máximo.

Yoshio Okamoto

3

Esta postagem discute uma generalização do seu problema okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html (pense em cada pessoa como tendo um item a ser comercializado, ou seja, sua posição no emprego).

Radu Grigore

4

Incrível pergunta, nos faz sentir que o que fazemos pode realmente ser usado na vida real :).

Gopi

9

OK, li o código do TradeMaximizer e acredito que ele resolve o seguinte problema mais geral.

PROBLEMA: Dado é um gráfico direcionado cujos arcos têm custos. Encontre um conjunto de ciclos separados por vértices que maximize o número de vértices cobertos primeiro e minimize o custo total em segundo.

Para resolver a pergunta feita aqui, faça com que os vértices sejam funcionários e desenhe um arco do custo unitário quando desejar o trabalho de . Observe que agora os funcionários são vértices e não arestas. O bom é que um funcionário pode dizer "Eu realmente quero o emprego de , mas o de também". $x\to y$ $x$ $y$ $y$ $z$

Solução:

Crie um gráfico bipartido da seguinte forma: para cada vértice no gráfico original, introduza um vértice esquerdo , um vértice direito e um arco cujo custo é enorme (maior que a soma dos custos no original) gráfico). Para cada arco no gráfico original, introduza um arco no gráfico bipartido. $x$ $x_L$ $x_R$ $x_L\to x_R$ $x\to y$ $x_L\to y_R$
Encontre uma correspondência perfeita de custo mínimo no gráfico bipartido.

Também existe algum pré-processamento do gráfico original: remova os arcos entre os SCCs e processe todos os SCCs de tamanho conforme indicado acima. $>1$

(Na verdade, o TradeMaximizer repete todas as soluções ideais, de acordo com os dois critérios acima, a fim de otimizar heuristicamente outras coisas, como a duração do maior ciclo. Grandes ciclos aumentam a chance de um "negócio" não passar porque um pessoa muda de idéia.)

PS: O autor, Chris Okasaki, confirmou que é isso que o código faz, na postagem do blog .

Radu GRIGore
fonte

Consegui encontrar uma solução para o problema original usando o TradeMaximizer. Vou postar detalhes amanhã.

Motobói 17/04/12

@ motobói, mas tudo o que você precisa fazer é o que eu escrevi no segundo parágrafo ...

Radu Grigore

Eu encontrei esta explicação sobre o algoritmo: boardgamegeek.com/wiki/page/TradeMaximizer

motobói

Você poderia explicar ou apontar para uma explicação sobre por que é necessário remover arcos entre os Componentes Comnectados Fortes?

Motobói

@ motobói, é uma otimização (para o caso médio). Os passos (1) e (2) devem ser suficientes.

Radu GRIGore #

22

$1$ $-1$

Como todos os custos e capacidades são limitados por constantes, um algoritmo simples de cancelamento de ciclo encontrará a circulação necessária em tempo polinomial. Isso é quase o mesmo que o algoritmo ganancioso óbvio:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

$O(VE)$ $0$ $-E$ $E$ $O(VE^2)$

Este não é o algoritmo mais rápido conhecido.

Jeffε
fonte

acha que isso funciona desde que uma pessoa não queira trabalhar em mais de uma "unidade", certo? usando fraseado da pergunta original. mas se as pessoas quiserem trabalhar em mais de uma unidade, suspeite que essa abstração se quebre. O OP declarou um problema em termos de apenas uma unidade, mas isso me parece bastante artificial. [que humano tem apenas uma preferência ...?]

vzn 16/04

1

O que é uma "pessoa" e uma "unidade"? Esta é uma pergunta sobre gráficos.

Jeffε

Estou confuso: meu exemplo não é um contra-exemplo para esse algoritmo? Depois de escolher C, os ciclos C_1 e C_2 não são mais ciclos (porque cada ciclo tem uma aresta invertida); C não será usado novamente porque tem um custo positivo depois de reverter suas arestas e não há novos ciclos introduzidos. Estamos falando do mesmo problema? Gostaria de ter uma formulação matemática do problema.

FiB

3

C

$C$

C

$C$

C_{1}

$C_1$

C_{2}

$C_2$

C^{'}

$C'$

C^{'}

$C'$

C_{1}

$C_1$

C_{2}

$C_2$

C^{'} = C_{1} + C_{2} - C

$C' = C_1 + C_2 - C$

aparentemente uma "unidade" é algo como um "departamento" e os usuários estão registrando solicitações de transferências entre departamentos [posições não exatamente específicas nos departamentos]? O diagrama de FIBs parece ter unidades como vértices e arestas conforme pedidos empl entre unidades. FiB-- "adoraria ter uma formulação matemática do problema" .. é realmente até você para fornecer uma formulação precisa .. você parece estar no meio do caminho ..

vzn

4

Essa abordagem gananciosa nem sempre oferece a melhor solução.

$C$ $n$ $\{(v_1, v_2),\dots,(v_n,v_1)\}$ $C_1$ $C_2$ $n-1$ $C$

$C$ $n$ $C_1$ $C_2$

$C_1$ $C_2$ $2(n-1)=2n-2$

$\lfloor\frac{n}{2}\rfloor$

FiB
fonte

-3

provavelmente existe uma maneira / formulação da teoria dos grafos para resolver isso, mas esse problema me parece mais um problema de permutação, onde algumas de todas as permutações são rejeitadas e outras são válidas. as permutações são funcionários e os cargos são "cargos" na empresa. uma permutação é rejeitada se não atender aos requisitos de "pessoa [x] quer posição [y]". a distinção dos limites de unidades / depts / org é aparentemente um tanto supérflua para a solução nesse caso.

esse tipo de problema de permutação com restrições pode ser facilmente convertido em uma instância do problema SAT (satisfação). as atribuições de variáveis booleanas representam funcionários e as cláusulas de restrição representam as restrições "pessoa [x] deseja posição [y]". existem exemplos clássicos próximos disso, geralmente chamado de "mesa de jantar", onde você tem lugares sentados e convidados e nem todos querem sentar um ao lado do outro (ou muito similarmente, alguns convidados querem sentar ao lado de outros convidados).

e, é claro, existem sofisticados solucionadores SAT para instâncias razoavelmente grandes, envolvendo aproximadamente centenas de variáveis e cláusulas no PC e, se o problema não for "difícil", aos milhares.

veja, por exemplo, [1] para uma referência profissional e [2] para um exercício de classe. há também alguma semelhança estrutural com o que é conhecido como "problemas nos buracos dos pombos", que é bem estudado nos círculos do SAT, onde os pombos são designados aos buracos dos pombos e você tem mais ou menos buracos que os pombos. nesse caso, no entanto, os pombos são geralmente vistos como intercambiáveis. em outras palavras, o problema da mesa de jantar é como o problema do pombo com restrições mais fortes e os convidados / pombos exigiram preferências.

observe, é claro / tenha em mente que, para esses tipos de problemas, dependendo das restrições, a resposta pode ser "não existe uma solução restrita".

[1] o algoritmo da mesa de jantar, por crato

[2] CS402 Princeton HW SAT

[3] Problema de satisfação, wikipedia

vzn
fonte

Eu tentei a permutação usando trademaximizer. Defina um funcionário como um usuário que deseja trocar sua unidade X para a unidade Y . Mas o software não permitirá que mais de um usuário negocie o mesmo item (sua unidade). Cada item deve ser único. Para acomodar isso, eu tinha que ter, digamos, [(Jones) quer trocar Unit-C-James para a Unidade-D-Laura ou Unit-D-Sergio ou Unit-D-Mary]