Come trovare i fornitori che possono fornirmi?

Question

Come trovare i fornitori che possono fornirmi?

#1 da (2 voti)
#2 da (0 voti)

1

Non sono in grado di cercare algoritmi che possono aiutarmi a risolvere questo problema, non sono sicuro in quale categoria questo problema cada o quale algoritmo usare.

Dichiarazione del problema:

Ci sono N numero di fornitori che forniscono zucchero, ogni fornitore ha la posizione del fornitore (latitudine, longitudine) del proprio magazzino da cui fornirà e hanno anche un "maximum_radius" al quale possono fornire.

Ora, se arriva un utente e fornisce la sua posizione Utente posizione (latitudine, longitudine), come faccio a trovare chi possono fornire tutti i fornitori in quel luogo.

L'unica soluzione che posso pensare se andare a ciascuna posizione del fornitore, calcolare la distanza dalla posizione dell'utente e controllare se rientra nel massimo_radius del fornitore. Ma questo sembra lento, poiché il numero di fornitori aumenterà nel tempo.

algorithms

posta rjvim 08.06.2016 - 11:42

fonte

2 risposte

0

Dovrai considerare ogni singolo fornitore, dato che ognuno ha un raggio diverso. Non è possibile smettere di controllare i fornitori una volta che si fallisce il test a distanza poiché un altro ulteriore potrebbe fornire un raggio più grande!

Quello che puoi fare è ridurre i calcoli considerando tutti i fornitori in orizzontale, quindi se sono più vicini della loro distanza di consegna, controlla la distanza diretta. Questo tipo di approccio funziona bene per gli algoritmi di routine in cui la distanza di guida su una rete stradale è più importante della distanza in linea retta (ad esempio se c'è un fiume nel modo!) - si riduce rapidamente il set di possibilità e si esegue il costoso controllo .

Detto questo, a meno che tu non abbia prestazioni matematiche particolarmente lente, il solo calcolo della distanza pitagorica diretta per ogni fornitore sarà abbastanza veloce.

risposta data 08.06.2016 - 12:15

fonte

Leggi altre domande sui tag algorithms

Qt / QML / C ++ Visibilità dell'oggetto di connessione al database dell'applicazione Tabella con 2 colonne che sono chiavi esterne. Solo uno può essere impostato per ogni record

score 2 · Accepted Answer

Dai commenti, sembra che tu abbia a che fare con 1 000 punti.

Il modo usuale per calcolare una distanza tra due punti, p1 e p2 , è:

sqrt(pow(p1.x - p2.x, 2), pow(p1.y - p2.y, 2))

Ho provato a misurare il tempo necessario per eseguire l'operazione in C # su una CPU a 2,10 GHz (nessuna parallelizzazione, quindi il numero di core non ha importanza) e non è riuscito. Con 10.000.000 di punti, ci vogliono circa 2 050 millisecondi, il che significa 0,205 ms. per 1 000 punti.

Prima di provare a ottimizzare il tuo codice, assicurati che questa parte sia effettivamente il collo di bottiglia , ovvero che sia stato identificato da un profiler come parte che rende l'applicazione più lenta. Altrimenti, stai facendo un'ottimizzazione prematura e non dovresti farlo .

Se il profiler ha effettivamente indicato che questa è la parte più lenta del tuo codice, ti suggerirei di esplorare alcune alternative di ottimizzazione:

Confronta le% effettive x e y prima di fare pow e sqrt roba. Se abs(p1.x - p2.x) è 200 e la distanza massima è 100, non è necessario continuare: i punti sono troppo distanti l'uno dall'altro.
Usa una mappa (simile a un cubo OLAP con coordinate e distanze corrispondenti alle dimensioni del cubo) e avvicina le coordinate del punto per rendere la mappa abbastanza piccola. Nota che dovresti fare molta attenzione: il tempo per eseguire I / O potrebbe avere un impatto molto più grande rispetto al calcolo effettivo.