sdbx (Normal User)
Newbie
Messaggi: 3
Iscritto: 06/09/2014
|
Ciao a tutti, ho una retta in cui sono collocati dei punti X1, X2... Xn fissi su di essa. A questo punto mi danno un numero N. Io devo inserire N nuovi punti sulla retta in modo che la somma totale di tutte le distanze fra ciascuna X e il più vicino nuovo punto inserito sia minima.
Con un esempio è più chiaro:
Dati i punti X1=1; X1=3 X2=20 X3=40; collocati su una retta:
-X0---X1-----------------X2--------------------X3------------>
Ora prendiamo a caso N = 3, devo collocare altri 3 punti in modo che la distanza tra i nuovi 3 punti e quello più lontano tra quelli vecchi sia minima, cioè inserisco 3 nuovi punti alle coordinate:
X4=2; X5=X2=20; X6=X3=40 così la distanza tra i nuovi punti e quelli vecchi è la minima.
Se N fosse stata = 1 allora avrei aggiunto un punto X4 = |X3 - X1|/2 = 19.5 così la distanza massima tra il nuovo punto e quello più lontano è 19.5 ed è il minimo che si possa avere.
Se N fosse stato = 2 allora avrei aggiunto due punti X4 = 10.5 e X5 = 30.5 così la distanza massima tra i nuovi punti e quelli più lontani è 10.5 ed è il minimo che si possa avere (credo XD).
Se N fosse stato = 3 (come scritto prima) allora avrei aggiunto 3 punti X4=2; X5=20; X6=40; così la distanza massima tra i nuovi punti e quelli più lontani è 1 ed è il minimo che si possa avere.
Se N fosse stato = 4 allora avrei aggiunto 4 nuovi nunti esattamente sui vecchi punti così la distanza è minima, quindi X4=X0; X5=X1; X6=X2; X7=X3;
Il mio problema è realizzare un algoritmo che mi inserisca i nuovi punti! Conoscete qualche algoritmo "famoso" che svolge questo compito? se no come lo risolvereste? Help!!!! Non ho idea di come fare!!! 
Ultima modifica effettuata da sdbx il 06/09/2014 alle 20:28 |
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Ho riletto il testo 3 volte e non riesco a capire cosa stai cercando di minimizzare. La tua definizione del problema e' ambigua.
Data una retta con punti X1, X2, ... Xn e dato un numero N, inserire N nuovi punti Y1, Y2, ... Yn in modo che la somma totale delle distanze tra .... ? e il piu' vicino nuovo punto (Y1? Y2? Yn? Tutti? Yn - Y1? Sono Y1, Y2, Yn definiti in maniera che Y1 <= Y2 <= ... <= Yn?) sia minima (eh?)
|
|
|
TheDarkJuster (Member)
Guru^2
Messaggi: 1620
Iscritto: 27/09/2013
|
piero, qui manca la notazione matematica (per le formule) aggiungerla non sarebbe male *.* comunque passando a cose serie..... Come fai ad avere punti alla stessa distanza senza spostare quelli vecchi? mmmmmmmmhhhhh non credo di aver capito la tua domanda. Puoi essere più chiaro?
Ok ho riletto più volte, ma non basta che aggiungi i punti vicini al primo e all' ultimo?
Ultima modifica effettuata da TheDarkJuster il 06/09/2014 alle 21:15 |
|
|
sdbx (Normal User)
Newbie
Messaggi: 3
Iscritto: 06/09/2014
|
Eh lo so scusate è complicato da spiegare! Anche io c'ho messo un po' a capire quello che mi richiedevano! Allora un esempio pratico potrebbe essere:
abbiamo 4 città collegate tra di loro da una linea ferroviaria:
-Milano-------Bologna------------------Roma------------------Catanzaro--->
Supponiamo che Milano è posizionata al KM 0 della ferrovia, Bologna al KM 3, Roma al KM 10 e Catanzaro al KM 20.
X0=0--X1=3-------X2=10----------X4=20--->
Ora dato un numero N di stazioni io devo posizionarle nel modo più corretto.
Se mi dicono che posso costruire una sola stazione la metterò esattamente a metà per cui tra Milano e Catanzaro, Quindi al KM 10;
Se mi dicono che posso costruire 2 stazioni ne costruirò una al KM 5 e una al KM 15;
Se mi dicono che posso costruire 3 stazioni ne costruirò una a Roma una a Catanzaro e una tra Milano e Bologna, in modo che la distanza tra le sazione e le città sia la minore possibile.
Se mi dicono che si possono costruire 4 stazioni ne costruisco una per città.
Quindi in base alle città che ho mi danno il numero di stazioni da costruire, per cui mi occorre sceglie le posizioni delle stazioni in modo tale che la distanza tra le città e le stazioni sia minima.
Spero così di essere stato un po' più chiaro! Il fatto è che non so come tradurlo in matematichese e quindi trirare fuori l'algoritmo che risolve il problema!
Ultima modifica effettuata da sdbx il 06/09/2014 alle 22:06 |
|
|
Roby94 (Member)
Guru
Messaggi: 1170
Iscritto: 28/12/2009
|
Allora se ho capito bene, avendo dei punti fissi su una retta, quindi con delle distanze tra di loro ben definite e avendo la possibilita di inserire una seconda serie di punti tu vorresti porre questi punti tra le singole tratte piu lunghe?
|
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Se mi dicono che posso costruire una sola stazione la metterò esattamente a metà per cui tra Milano e Catanzaro, Quindi al KM 10;
|
E perche' non al KM 9, oppure 8, o 7?
abs(10 - 0) = 10
abs(10 - 3) = 7
abs(10 - 10) = 0
abs(10 - 20) = 10
Tot: 27
abs(9 - 0) = 9
abs(9 - 3) = 6
abs(9 - 10) = 1
abs(9 - 20) = 11
Tot: 27
Ultima modifica effettuata da pierotofy il 07/09/2014 alle 18:52
|
|
|
sdbx (Normal User)
Newbie
Messaggi: 3
Iscritto: 06/09/2014
|
Perchè se metto una stazione al decimo kilometro la distanza massimatra tra la stazione e la città più lontana è 10. Mentre se la metto al nono kilometro la distanza massima tra la stazione e la città più lontana è 11. Io devo fare si che la distanza massima sia la minima.
È un macello!
L'unica idea che mi è venuta è creare tutte le combinazioni possibili delle stazioni sulla linea e memorizzare quella la cui somma delle distanze tra le stazioni e le città è la minima. Ma è estremamente inefficiente.
|
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Non è ancora chiaro... forse dovresti darci la fonte originale del problema? Sembra che sia un esercizio universitario oppure un problema preso da qualche gara.
Per il caso N = 2, perchè le stazioni sono a 5 e 15?
abs(0 - 5) = 5, abs(0 - 15) = 15 (Min: 5)
abs(3 - 5) = 2, abs(3 - 15) = 12 (Min: 2)
abs(10 - 5) = 5, abs(10 - 15) = 5 (Min: 5)
abs(20 - 5) = 15, abs(20 - 15) = 5 (Min: 5)
Tot: 5 + 2 + 5 + 5 = 17
Perchè non 5 e 20?
abs(0 - 5) = 5, abs(0 - 20) = 15 (Min: 5)
abs(3 - 5) = 2, abs(3 - 20) = 12 (Min: 2)
abs(10 - 5) = 5, abs(10 - 20) = 5 (Min: 5)
abs(20 - 5) = 15, abs(20 - 20) = 0 (Min: 0)
Tot: 5 + 2 + 5 = 12
Postaci la fonte originale del problema, in forma completa.
|
|
|
