Encontre a melhor combinação de um determinado conjunto de múltiplos conjuntos

https://stackoverflow.com/questions/14884

08-06-2019
|

Pergunta

Digamos que você tenha uma remessa.Ele precisa ir do ponto A ao ponto B, do ponto B ao ponto C e finalmente do ponto C ao ponto D.Você precisa chegar lá em cinco dias pelo menor valor possível.Existem três remetentes possíveis para cada trecho, cada um com seu tempo e custo diferentes para cada trecho:

Array
(
    [leg0] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 5000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 5
                    [cost] => 1000
                )

        )

    [leg1] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 3
                    [cost] => 1000
                )

        )

    [leg2] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 4000
                )

            [FedEx] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 2
                    [cost] => 5000
                )

        )

)

Como você encontraria a melhor combinação programaticamente?

Minha melhor tentativa até agora (terceiro ou quarto algoritmo) é:

Encontre o remetente mais longo para cada trecho
Elimine o mais “caro”
Encontre o remetente mais barato para cada trecho
Calcule o custo total e dias
Se os dias forem aceitáveis, termine; caso contrário, vá para 1

Simulado rapidamente em PHP (observe que o array de teste abaixo funciona perfeitamente, mas se você tentar com o array de teste acima, ele não encontrará a combinação correta):

$shippers["leg1"] = array(
    "UPS"    => array("days" => 1, "cost" => 4000),
    "Conway" => array("days" => 3, "cost" => 3200),
    "FedEx"  => array("days" => 8, "cost" => 1000)
);

$shippers["leg2"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);

$shippers["leg3"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);    

$times = 0;
$totalDays = 9999999;

print "<h1>Shippers to Choose From:</h1><pre>";
print_r($shippers);
print "</pre><br />";

while($totalDays > $maxDays && $times < 500){
            $totalDays = 0;
            $times++;
            $worstShipper = null;
            $longestShippers = null;
            $cheapestShippers = null;

            foreach($shippers as $legName => $leg){
                //find longest shipment for each leg (in terms of days)
                unset($longestShippers[$legName]);
                $longestDays = null;        

                if(count($leg) > 1){
                    foreach($leg as $shipperName => $shipper){
                        if(empty($longestDays) || $shipper["days"] > $longestDays){
                            $longestShippers[$legName]["days"] = $shipper["days"];
                            $longestShippers[$legName]["cost"] = $shipper["cost"];
                            $longestShippers[$legName]["name"] = $shipperName;
                            $longestDays = $shipper["days"];
                        }
                    }           
                }
            }

            foreach($longestShippers as $leg => $shipper){
                $shipper["totalCost"] = $shipper["days"] * $shipper["cost"];

                //print $shipper["totalCost"] . " &lt;?&gt; " . $worstShipper["totalCost"] . ";";

                if(empty($worstShipper) || $shipper["totalCost"] > $worstShipper["totalCost"]){
                    $worstShipper = $shipper;
                    $worstShipperLeg = $leg;
                }
            }

            //print "worst shipper is: shippers[$worstShipperLeg][{$worstShipper['name']}]" . $shippers[$worstShipperLeg][$worstShipper["name"]]["days"];
            unset($shippers[$worstShipperLeg][$worstShipper["name"]]);

            print "<h1>Next:</h1><pre>";
            print_r($shippers);
            print "</pre><br />";

            foreach($shippers as $legName => $leg){
                //find cheapest shipment for each leg (in terms of cost)
                unset($cheapestShippers[$legName]);
                $lowestCost = null;

                foreach($leg as $shipperName => $shipper){
                    if(empty($lowestCost) || $shipper["cost"] < $lowestCost){
                        $cheapestShippers[$legName]["days"] = $shipper["days"];
                        $cheapestShippers[$legName]["cost"] = $shipper["cost"];
                        $cheapestShippers[$legName]["name"] = $shipperName;
                        $lowestCost = $shipper["cost"];
                    }
                }

                //recalculate days and see if we are under max days...
                $totalDays += $cheapestShippers[$legName]['days'];  
            }
            //print "<h2>totalDays: $totalDays</h2>";
        }

        print "<h1>Chosen Shippers:</h1><pre>";
        print_r($cheapestShippers);
        print "</pre>";

Acho que talvez tenha que fazer algum tipo de coisa em que literalmente faço cada combinação uma por uma (com uma série de loops) e some a "pontuação" total de cada uma e encontro a melhor...

EDITAR:Para esclarecer, esta não é uma tarefa de “lição de casa” (não estou na escola).Faz parte do meu projeto atual no trabalho.

Os requisitos (como sempre) têm mudado constantemente.Se eu recebesse as restrições atuais no momento em que comecei a trabalhar neste problema, estaria usando alguma variante do algoritmo A* (ou Dijkstra ou caminho mais curto ou simplex ou algo assim).Mas tudo está se transformando e mudando, e isso me leva onde estou agora.

Então, acho que isso significa que preciso esquecer toda a porcaria que fiz até agora e seguir com o que sei que deveria fazer, que é um algoritmo de localização de caminho.

Solução

Poderia alterar alguns dos algoritmos de caminho mais curto, como o de Dijkstra, para ponderar cada caminho pelo custo, mas também controlar o tempo e parar de seguir um determinado caminho se o tempo exceder seu limite.Deve encontrar o mais barato que o deixe abaixo do seu limite dessa forma

Outras dicas

Parece que o que você tem é chamado de "problema de programação linear".Também parece um problema de dever de casa, sem ofensa.

A solução clássica para um problema de LP é chamada de "Método Simplex".Pesquise no Google.

Entretanto, para usar esse método, você deve ter o problema formulado corretamente para descrever seus requisitos.

Ainda assim, pode ser possível enumerar todos os caminhos possíveis, já que você possui um conjunto tão pequeno.Tal coisa não terá escala, no entanto.

Parece um trabalho para Algoritmo de Dijkstra:

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1959, 1 é um algoritmo de busca de grafos que resolve o problema do caminho mais curto de fonte única para um grafo com custos de caminho de borda não negativos, gerando uma árvore de caminho mais curto.Este algoritmo é frequentemente usado em roteamento.

Também há detalhes de implementação no artigo da Wikipedia.

Se eu soubesse que só teria que lidar com 5 cidades, em uma ordem pré-determinada, e que só havia 3 rotas entre cidades adjacentes, eu usaria força bruta.Não adianta ser elegante.

Se, por outro lado, este fosse um trabalho de casa e eu devesse produzir um algoritmo que pudesse realmente ser escalonado, provavelmente adotaria uma abordagem diferente.

Como disse Baltimark, este é basicamente um problema de programação linear.Se apenas os coeficientes para os expedidores (1 para incluídos, 0 para não incluídos) não fossem números inteiros (binários) para cada trecho, isto seria mais facilmente solucionável.Agora você precisa encontrar algumas heurísticas de programação linear inteira (ILP) (binárias), pois o problema é NP-difícil.Ver Wikipedia sobre programação linear inteira para links;no meu curso de programação linear usamos pelo menos Filial e limite.

Na verdade, agora que penso nisso, este caso especial pode ser resolvido sem o ILP real, pois a quantidade de dias não importa, desde que seja <= 5.Agora comece escolhendo a transportadora mais barata para primeira escolha (Conway 5:1000).Em seguida, você escolhe novamente o mais barato, resultando em 8 dias e 4.000 unidades monetárias, o que é demais, então abortamos isso.Ao tentar outros também, vemos que todos eles resultam em dias> 5, então voltamos à primeira escolha e tentamos o segundo mais barato (FedEx 2:3000) e depois aumentamos na segunda e fedex na última.Isso nos dá um total de 4 dias e 9.000 unidades monetárias.

Poderíamos então usar esse custo para podar outras pesquisas na árvore que, por algum resultado de estágio de subárvore, custariam maiores do que aquela que já encontramos e deixariam essa subárvore sem pesquisa daquele ponto em diante.Isso só funciona desde que saibamos que pesquisar na subárvore não produzirá melhores resultados, como fazemos aqui quando os custos não podem ser negativos.

Espero que esta divagação tenha ajudado um pouco :).

Isto é um problema da mochila.Os pesos são os dias de trânsito, e o lucro deve ser de US$ 5.000 – custo da perna.Elimine todos os custos negativos e siga em frente!

Acho que o algoritmo de Dijkstra serve para encontrar o caminho mais curto.

cmculloh está procurando o custo mínimo, sujeito à restrição de que o consiga em 5 dias.

Portanto, simplesmente encontrar o caminho mais rápido não o levará até lá mais barato, e chegar lá pelo mais barato não o levará até lá no tempo necessário.

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

Não afiliado a StackOverflow