PHP - calcolo matematico Difficile

Question

Descrizione del progetto

Il progetto calcola la quantità di cibo un cavallo dovrebbe avere, questo si basa su un enorme numero di variabili. L'utente inserisce le informazioni su ciascun cavallo e i feed preferiti. Ogni mangime ha più tipi di vitamine e sostanze nutritive.

1 cavallo utilizza più tipi di alimentazione.

Quello che abbiamo

Abbiamo il valori minimo e massimo per ogni sostanza nutritiva che la specifica esigenza cavallo.

Abbiamo il contenuto per uno o più tipi diversi di mangime, questo potrebbe essere di circa 20-30 diversi nutrienti e vitamine per mangime. Abbiamo anche il prezzo e vogliamo usarlo per risparmiare denaro.

(Il calcolo è solo per un cavallo al momento)

Esempio

Usiamo A, B e C per rappresentare le sostanze nutritive.

cavallo deve: (A, B, C) MIN (30,7,9) MAX (35,9,17)

Flux 1 contiene: (, B, C) i valori (16,2 , 3)
Il feed 2 contiene: (A, B, C) VALORI (0,4,9)

Una soluzione di lavoro sarebbe 2 * Feed1 e 1 * Feed2.

Problema

Voglio il sistema per calcolare l'equilibrio perfetto in base ai valori min/max per ciascun nutriente, ed ancora mantenere il prezzo più basso possibile.

soluzione

Se ho calcolare l'importo più elevato possibile per ogni alimentazione, sarà possibile rendere casuale fino a quando non sembra funzionare lavoro. E poi l'utente sarà in grado di cambiare gli importi se non è perfetto.

<?php 
function randomizerLoop(){ 
    foreach($feeds as $feed){ 
     $max['A'] = floor($horse_max['A']/$feed['A']); 
     $max['B'] = floor($horse_max['B']/$feed['B']); 
     $max['C'] = floor($horse_max['C']/$feed['C']); 
     $maxRand = MIN($max['A'], $max['B'], $max['C']); 

     $amounts[$feed['id']] = rand(0, $maxRand); 
    } 

    return $amounts; 
} 
?> 

Questo codice sarebbe continuare a provare fino a quando non ottenere un equilibrio di lavoro, invece di usare un po 'di freddo calcolo per trovare l'equilibrio al primo tentativo.

Ho solo bisogno di un'idea su come risolverlo senza rand().

Maggiori informazioni

Ogni utente sarà in grado di aggiungere il numero infinito di cavalli, ma sarà solo in grado di calcolare per un cavallo al momento (per ora).

Sarà inoltre possibile aggiungere un numero infinito di feed (definiti dall'utente) e ciascun feed potrebbe contenere 20-30 variabili. A seconda della soluzione, questo probabilmente richiederebbe un limite di feed per ogni auto-calcolo.

Ci sarebbero molte combinazioni se usassimo 20 feed diversi, 20-30 variabili per ogni feed, e anche quando definiamo la quantità in int invece che in booleani.

Answer 1

Quello che vuoi fare è provare ogni combinazione di ogni feed. Supponiamo che ci siano 5 tipi di feed. Sai già come calcolare il massimo di ogni tipo di feed. Quindi, io suppone che si abbia qualcosa di simile:

$feeds_cost = array of costs for each feed 
$feeds_ingredient_A = array of how much ingredient A each feed has 
$feeds_ingredient_B = array of how much ingredient B each feed has 
$feeds_ingredient_C = array of how much ingredient C each feed has 
$feeds_max = array of maximum quantity of each feed allowed 

Ora, per i 5 tipi, si vuole provare quantità {0,0,0,0,0}, {0,0,0,0, 1}, {0,0,0,0,2} ... {$ feeds_max [0], $ feeds_max [1], $ feeds_max [2], $ feeds_max [3], $ feeds_max [4]}. Per ciascun set di quantità, è necessario: 1. Assicurarsi che la quantità soddisfi il requisito minimo. 2. Se soddisfa il requisito minimo, calcola il costo.

Quindi, a questo punto, si ha il costo per ogni quantità che soddisfa il requisito minimo, ma non supera il requisito massimo. Non è necessario archiviarli tutti. Mantieni due variabili: $ best_quantities (una serie di conteggi di ciascun feed) e $ best_cost. Se una quantità ha un costo inferiore nel soddisfare i requisiti, sostituisci $ best_quantities e $ best_cost.

Tutto è banale tranne il passaggio attraverso tutte le quantità. Questo non è davvero molto difficile. Si mantiene l'indice che si sta incrementando. Inizialmente, è zero, ma sale al più alto indice di feed (4 se hai 5 feed). La funzione di incremento è:

function increment_counts($feeds_max, $quantities, $index) 
{ 
    if($index>sizeof($quantities)) return null; 
    $quantities[$index]++; 
    if($quantities[$index] > $feeds_max[$index]) 
    { 
     $quantities[$index]=0; 
     return increment_counts($feeds_max, $quantities, $index+1); 
    } 
    return $quantities; 
} 

Supponendo che ho digitato correttamente che la parte superiore della mia testa, conterà attraverso le quantità. Continui a chiamarlo incrementando l'indice 0 e sostituendo la quantità corrente con il valore restituito. Quando restituisce null, hai finito.

Sono certo che ho fatto almeno una supervisione, ma è così che vorrei affrontare questo problema.

Answer 2

Questo è un problema linear programming.

 MIN  MAX 
A 30  35 
B 7  9 
C 9  17 

      A B C 
Feed1  16 2 3 
Feed2  0 4 9 

Lasciare che il cibo contenga il x numero di feed1 e y numero di feed2. Secondo il vostro domanda:

30<16*x+0*y<35 
=> 30<16x<35 

uso ceil() per dividere 30 da 16, che darà u x (che è 2). Dopo di che hai 3 < 4y < 5, analogamente usa ceil() e otterrai y = 1.

Ora pensare in termini di voi proiettare,

Per gran numero di feed sarà difficile calcolare tante equazioni.

dovremmo usare matrici per simplification.The martix per le equazioni di cui sopra saranno: -

A * B = C 
|16 0| | x | | 30 | 
|2 4| | y | = | 7 | 
|3 9|   | 9 | 

Ora utilizzate Lapack::pseudoInverse() per calcolare l'inversa della matrice A e moltiplicarlo con C. Poi semplicemente equiparare la valore di xey nella matrice B alla risposta e uso ceil().

Answer 3

Mi concentrerei sui valori MIN per ridurre al minimo il costo.In ogni caso, l'intero punto dell'approccio suggerito è quello di soddisfare determinati obiettivi, che potrebbero essere variabili come richiesto (ad esempio: forzare i nutrienti E & G per ottenere, almeno, il valore mezzo tra MIN & MAX).

La struttura di base è formata da tre anelli: uno principale che attraversa tutte le sostanze nutritive; e due interni che provano tutte le possibili combinazioni tra i feed.

NUTRIENT A 
Trying feed1 until reaching minimum (because feed2 is zero). 
Best so far: 2*feed1=32A. 

NUTRIENT B 
Starting from 2*feed1=4B, +feed2 reaches minimum. 
Best so far: 2*feed1+feed2=8B. 

NUTRIENT C 
Starting from 2*feed1+feed2=15C which is fine already. 
Best so far: 2*feed1+feed2=15C. 

Una versione più avanzata di questo approccio sarebbe tornato a controllare (ad esempio, nei casi in cui si raggiunge il bersaglio poiché un primo momento, come accade con nutrienti C) se una migliore alternativa sarebbe possibile. In ogni caso, la complessità di tale implementazione e il numero di combinazioni sarebbero notevolmente più elevati.

Penso che questo sia un approccio abbastanza adattabile e accurato. L'implementazione dell'algoritmo per la versione base non è troppo difficile (ma neanche troppo semplice, ecco perché non l'ho scritto qui) e dovrebbe fornire una precisione e una velocità ragionevolmente buone. Dopo averlo provato e aver avuto un'idea delle sue prestazioni, potresti iniziare a pensare di migliorarlo ulteriormente (ad esempio, tornando indietro per analizzare nuovamente il caso o rendere conto di obiettivi non MIN).