Trova la migliore combinazione da un dato insieme di più insiemi

https://stackoverflow.com/questions/14884

08-06-2019
|

Domanda

Supponiamo che tu abbia una spedizione.Deve andare dal punto A al punto B, dal punto B al punto C e infine dal punto C al punto D.Ne hai bisogno per arrivare lì in cinque giorni con la minor quantità di denaro possibile.Ci sono tre possibili spedizionieri per ogni tratta, ciascuno con tempi e costi diversi per ogni tratta:

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
                )

        )

)

Come faresti per trovare la migliore combinazione a livello di programmazione?

Il mio miglior tentativo finora (terzo o quarto algoritmo) è:

Trova lo spedizioniere più lungo per ciascuna tratta
Elimina quello più “costoso”.
Trova lo spedizioniere più economico per ogni tratta
Calcola il costo totale e i giorni
Se i giorni sono accettabili, termina, altrimenti vai a 1

Simulazione rapida in PHP (nota che l'array di test di seguito funziona perfettamente, ma se lo provi con l'array di test dall'alto, non trova la combinazione corretta):

$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>";

Penso che potrei dover effettivamente fare una sorta di cosa in cui creo letteralmente ogni combinazione una per una (con una serie di loop) e sommo il "punteggio" totale di ciascuna e trovo quella migliore....

MODIFICARE:Per chiarire, questo non è un compito "compiti a casa" (non vado a scuola).Fa parte del mio attuale progetto di lavoro.

I requisiti (come sempre) sono cambiati costantemente.Se mi venissero dati i vincoli attuali nel momento in cui ho iniziato a lavorare su questo problema, utilizzerei qualche variante dell'algoritmo A* (o di Dijkstra o del percorso più breve o del simplesso o qualcosa del genere).Ma tutto si è trasformato e cambiato, e questo mi ha portato dove sono adesso.

Quindi immagino che questo significhi che devo dimenticare tutte le schifezze che ho fatto fino a questo punto e seguire semplicemente quello che so che dovrei seguire, che è un algoritmo di ricerca del percorso.

Soluzione

Potrebbe alterare alcuni dei algoritmi del percorso minimo, come quello di Dijkstra, per ponderare ogni percorso in base al costo ma anche tenere traccia del tempo e interrompere un determinato percorso se il tempo supera la soglia.Dovresti trovare il più economico che ti faccia entrare sotto la tua soglia in questo modo

Altri suggerimenti

Sembra che quello che hai sia chiamato "problema di programmazione lineare".Sembra anche un problema di compiti, senza offesa.

La soluzione classica ad un problema di LP è chiamata "metodo del simplesso".Cercalo su Google.

Tuttavia, per utilizzare questo metodo, è necessario che il problema sia formulato correttamente per descrivere le proprie esigenze.

Tuttavia, potrebbe essere possibile enumerare tutti i percorsi possibili, poiché il set è così piccolo.Una cosa del genere, però, non sarà scalabile.

Sembra un lavoro per Algoritmo di Dijkstra:

L'algoritmo di Dijkstra, ideato dall'informatico olandese Edsger Dijkstra nel 1959, 1 è un algoritmo di ricerca su grafi che risolve il problema del percorso più breve da un'unica sorgente per un grafo con costi del percorso degli archi non negativi, producendo un albero dei percorsi più brevi.Questo algoritmo viene spesso utilizzato nel routing.

Ci sono anche dettagli sull'implementazione nell'articolo di Wikipedia.

Se sapessi di avere a che fare solo con 5 città, in un ordine predeterminato, e che ci sono solo 3 percorsi tra città adiacenti, lo farei con la forza bruta.Inutile essere eleganti.

Se, d'altra parte, questo fosse un compito a casa e dovessi produrre un algoritmo realmente scalabile, probabilmente adotterei un approccio diverso.

Come ha detto Baltimark, questo è fondamentalmente un problema di programmazione lineare.Se solo i coefficienti per gli spedizionieri (1 per inclusi, 0 per non inclusi) non fossero interi (binari) per ciascuna tratta, questo sarebbe più facilmente risolvibile.Ora è necessario trovare alcune euristiche di programmazione lineare intera (ILP) (binaria) poiché il problema è NP-difficile.Vedere Wikipedia sulla programmazione lineare intera per i collegamenti;nel mio corso di programmazione lineare abbiamo usato almeno Ramificato e legato.

In realtà ora che ci penso, questo caso speciale è risolvibile senza ILP effettivo poiché il numero di giorni non ha importanza purché sia <= 5.Ora inizia scegliendo il vettore più economico come prima scelta (Conway 5:1000).Successivamente scegli ancora una volta il più economico, ottenendo 8 giorni e 4000 unità di valuta che sono troppe, quindi interrompiamo l'operazione.Provandone anche altri vediamo che tutti risultano giorni > 5 quindi torniamo alla prima scelta e proviamo la seconda più economica (FedEx 2:3000) e poi ups nella seconda e fedex nell'ultima.Questo ci dà un totale di 4 giorni e 9000 unità monetarie.

Potremmo quindi utilizzare questo costo per eliminare altre ricerche nell'albero che, a causa di alcuni risultati nella fase del sottoalbero, costerebbero maggiori di quello che abbiamo già trovato e lasciare quel sottoalbero non cercato da quel punto in poi.Funziona solo finché possiamo sapere che la ricerca nel sottoalbero non produrrà risultati migliori, come facciamo qui quando i costi non possono essere negativi.

Spero che questo divagare abbia aiutato un po' :).

Questo è un problema dello zaino.I pesi corrispondono ai giorni di transito e il profitto dovrebbe essere pari a $ 5000, ovvero il costo della tratta.Elimina tutti i costi negativi e parti da lì!

Penso che l'algoritmo di Dijkstra serva a trovare il percorso più breve.

cmcculloh cerca il costo minimo con il vincolo di riceverlo in 5 giorni.

Quindi, semplicemente trovare il modo più veloce non lo porterà a destinazione nel modo più economico, e arrivare lì per il modo più economico non lo porterà a destinazione nel tempo richiesto.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow