Ricerca elemento in un insieme
Salve,
ho un quesito da porvi: supponiamo di avere un insieme contenente elementi formati da tutte le n-ple di numeri {0,1}.
A = { x^n, n > 0 | x \in {0,1} }. L'insieme A può essere completo, nel senso che contiene gli elementi possibili, o incompleto se ne contiene solo alcuni. Per esempio n = 2, A = {00, 01, 10, 11} completo e A={10, 11} incompleto.
Data una n-upla di numeri reali, dove ciascun numero reale è compreso nell'intervallo {0,1} (a = 0.2 0.4), l'obiettivo è determinare la n-pla di numeri interi più vicina. Nel caso a = 0.2 0.4, l'elemento più vicino nel caso di A completo è 00 mentre nel caso di A incompleto 10.
Un modo efficiente per calcolare l'elemento più vicino nel caso di A completo è la ricerca dicotomica che ha complessità logaritmica. Nel caso di A incompleto le cose si fanno più difficili, l'unico approccio che mi viene in mente è la ricerca esaustiva (sbaglio o è un problema noto NP-completo).
Avete qualche suggerimento, idea?
grazie
ho un quesito da porvi: supponiamo di avere un insieme contenente elementi formati da tutte le n-ple di numeri {0,1}.
A = { x^n, n > 0 | x \in {0,1} }. L'insieme A può essere completo, nel senso che contiene gli elementi possibili, o incompleto se ne contiene solo alcuni. Per esempio n = 2, A = {00, 01, 10, 11} completo e A={10, 11} incompleto.
Data una n-upla di numeri reali, dove ciascun numero reale è compreso nell'intervallo {0,1} (a = 0.2 0.4), l'obiettivo è determinare la n-pla di numeri interi più vicina. Nel caso a = 0.2 0.4, l'elemento più vicino nel caso di A completo è 00 mentre nel caso di A incompleto 10.
Un modo efficiente per calcolare l'elemento più vicino nel caso di A completo è la ricerca dicotomica che ha complessità logaritmica. Nel caso di A incompleto le cose si fanno più difficili, l'unico approccio che mi viene in mente è la ricerca esaustiva (sbaglio o è un problema noto NP-completo).
Avete qualche suggerimento, idea?
grazie
Risposte
Ciao,
in pratica cerchi il floor in rappresentazione binaria dei numeri in $a$. Ma come computi $a$, cioè quale è la scelta di vicino.
Da come hai posto il problema, te cerchi il più piccolo elemeno di $A$ che sia completo o incompleto non importa (che corrisponde al min in base $10$, essendo l'insieme $A$ rappresentato da elementi in base $2$ alla fine).
Non dici come valuti $a$ e come lo leghi all'insieme $A$, cioè quale è la scelta di vicino.
in pratica cerchi il floor in rappresentazione binaria dei numeri in $a$. Ma come computi $a$, cioè quale è la scelta di vicino.
Da come hai posto il problema, te cerchi il più piccolo elemeno di $A$ che sia completo o incompleto non importa (che corrisponde al min in base $10$, essendo l'insieme $A$ rappresentato da elementi in base $2$ alla fine).
Non dici come valuti $a$ e come lo leghi all'insieme $A$, cioè quale è la scelta di vicino.
Ciao,
la scelta del vicino può essere fatta sia con la distanza di Hamming sia con la distanza euclidea. La seconda è migliore perchè più precisa.
Scusa se non sono stato molto chiaro: io cerco l'elemento dell'insieme A che si trova a minima distanza dall'elemento a. Se A è completo, ha un numero di elementi pari a 2^n essendo n la lunghezza di un elemento, se A è incompleto il numero di elementi è minore uguale di 2^n. Se A è completo, la procedura di ricerca dell'elemento più vicino ad a è la ricerca dicotomica che ha complessità logaritmica: infatti è sufficiente vedere se ogni elemento di a è maggiore o minore di 0.5 e associargli il valore più vicino. Se A è incompleto, non è possibile usare tale procedura: posso utilizzare la ricerca esaustiva che ha complessità esponenziale o usare un algoritmo complicato che ti spiegherò dopo se non hai un suggerimento migliore.
Grazie
la scelta del vicino può essere fatta sia con la distanza di Hamming sia con la distanza euclidea. La seconda è migliore perchè più precisa.
Scusa se non sono stato molto chiaro: io cerco l'elemento dell'insieme A che si trova a minima distanza dall'elemento a. Se A è completo, ha un numero di elementi pari a 2^n essendo n la lunghezza di un elemento, se A è incompleto il numero di elementi è minore uguale di 2^n. Se A è completo, la procedura di ricerca dell'elemento più vicino ad a è la ricerca dicotomica che ha complessità logaritmica: infatti è sufficiente vedere se ogni elemento di a è maggiore o minore di 0.5 e associargli il valore più vicino. Se A è incompleto, non è possibile usare tale procedura: posso utilizzare la ricerca esaustiva che ha complessità esponenziale o usare un algoritmo complicato che ti spiegherò dopo se non hai un suggerimento migliore.
Grazie
qua mescoli troppi concetti slegati tra loro.
Quegli insiemi cosa sono? vettori, insiemi ordinati, ...
per me si risolve ancora cercando l'elemento minimo dell'insieme A (ovvio che lo spazio di ricerca è esponenziale se è un insieme, se non possiede una relazione di ordine)
se $a$ è l'insieme di elementi di $[0,1]$ cosa serve cercare valori maggiori del minimo? Sei d'accordo su questo (poi dipende dalla natura di quegli insiemi se vettori o insiemi)?
PS: se hai un link ad un testo postalo, così tagliamo la testa al toro
Quegli insiemi cosa sono? vettori, insiemi ordinati, ...
per me si risolve ancora cercando l'elemento minimo dell'insieme A (ovvio che lo spazio di ricerca è esponenziale se è un insieme, se non possiede una relazione di ordine)
se $a$ è l'insieme di elementi di $[0,1]$ cosa serve cercare valori maggiori del minimo? Sei d'accordo su questo (poi dipende dalla natura di quegli insiemi se vettori o insiemi)?
PS: se hai un link ad un testo postalo, così tagliamo la testa al toro
Ciascun elemento dell'insieme è una n-upla, chiamala vettore se vuoi...il problema si risolve cercando l'elemento che si trova a minima distanza da quello in esame.
Non ho un link al problema, ma ti faccio un esempio e vediamo se ci capiamo...
Supponiamo di avere n = 3 e l'elemento a = [0.3 0.4 0.7]. In questo caso se l'insieme delle possibili n-ple A è completo A = {0 0 0; 0 0 1; 0 1 0; 0 1 1; 1 0 0; 1 0 1; 1 1 0; 1 1 1}, l'elemento più vicino è 0 0 1. Questo si può calcolare senza valutare tutte le distanze, ma attraverso la ricerca dicotomica guardando il valore di ogni elemento di a. Se A è incompleto A = {0 0 0; 1 1 0; 1 1 1} per esempio, l'unico algoritmo che mi viene in mente è quello che valuta tutte le possibili distanze di a dagli elementi di A e prende l'elemento a distanza minima (scelta una distanza a piacere). Adesso mi sono spiegato?
ciao
Non ho un link al problema, ma ti faccio un esempio e vediamo se ci capiamo...
Supponiamo di avere n = 3 e l'elemento a = [0.3 0.4 0.7]. In questo caso se l'insieme delle possibili n-ple A è completo A = {0 0 0; 0 0 1; 0 1 0; 0 1 1; 1 0 0; 1 0 1; 1 1 0; 1 1 1}, l'elemento più vicino è 0 0 1. Questo si può calcolare senza valutare tutte le distanze, ma attraverso la ricerca dicotomica guardando il valore di ogni elemento di a. Se A è incompleto A = {0 0 0; 1 1 0; 1 1 1} per esempio, l'unico algoritmo che mi viene in mente è quello che valuta tutte le possibili distanze di a dagli elementi di A e prende l'elemento a distanza minima (scelta una distanza a piacere). Adesso mi sono spiegato?
ciao
"erotavlas":
Ciascun elemento dell'insieme è una n-upla, chiamala vettore se vuoi...il problema si risolve cercando l'elemento che si trova a minima distanza da quello in esame.
Non ho un link al problema, ma ti faccio un esempio e vediamo se ci capiamo...
Supponiamo di avere n = 3 e l'elemento a = [0.3 0.4 0.7]. In questo caso se l'insieme delle possibili n-ple A è completo A = {0 0 0; 0 0 1; 0 1 0; 0 1 1; 1 0 0; 1 0 1; 1 1 0; 1 1 1}, l'elemento più vicino è 0 0 1. Questo si può calcolare senza valutare tutte le distanze, ma attraverso la ricerca dicotomica guardando il valore di ogni elemento di a. Se A è incompleto A = {0 0 0; 1 1 0; 1 1 1} per esempio, l'unico algoritmo che mi viene in mente è quello che valuta tutte le possibili distanze di a dagli elementi di A e prende l'elemento a distanza minima (scelta una distanza a piacere). Adesso mi sono spiegato?
ciao
ok, è qualcosa di diverso quello che hai descritto ora. L'insieme $A$ è un rappresentante della distanza celing-floor del numero reale. Ora comprendo perchè parlavi di $n$-eupla consideravo l'insieme $001$ come un numero binario, e non un insieme o vettore, te lo hai rappresentato in maniera fuorviante, per questo parlavo di mescolanza di argomenti.
Se $S$ è l'insieme delle soluzioni con $n=3$: $S = ((0,0,...),(0,0,...),(0,1,...))$.
$A$ è un riduzione dell'insieme delle soluzioni $S$ composto dall rappresentazione binaria (una compressione di informazione se si vuole).
Sì un po' la stessa cosa, cambia un pochetto secondo me, ma l'importante è capirsi.
In tutti i casi ci sono due limiti insormontabili:
- Sia $k$ il numero di bit della massima rappresentazione intera di un calcolatore (se fai un long es. 128 elementi), allora $n=O(k)$ perciò sarà la massima cardinalità di $a$.
- Lo spazio di ricerca è ovviamente $O(2^n)$
considerando un altro tipo di rappresentazione non utilizzando i bit come valore rappresentante dell'insieme $S$, i limiti saranno molto più alti, tipo se si utilizza un array il limite si sposta a $n=O(2^k)$ e lo spazio di ricerca sarà
$O(2^n) = O(2^(2^k)) = O(4^k)$. Un po' grande
caso completo: perchè dici di utilizzare $0,5$ come punto di di separazione, è un valore fisso o può variare?
Nel senso non pensi di utilizzare funzioni di arrotondamento (ceil floor come detto) perchè se prendiamo $0.46$ è più vicino a $1$ che $0$ se prendiamo l'arrotondamento $0.46 \cong 0.5 \cong 1$ nel tuo caso sarà $0$.
l'algoritmo migliore nel caso di rappresentazione binaria di $S$ mi pare sia la ricerca dicotomica, e su questo siam d'accordo (forse c'è di ancora meglio si può vedere), da tenere in considerazione l'insieme deve essere ordinato.
Nel caso di rappresentazione di insiemi es. con array, qua il discorso si complica assay. Sarà da includere cose come funzioni hash secondo, rappresentanti dell'array per ogni elemento (sarebbe multi-dimensionale)
caso incompleto: secondo me si può fare di meglio, abbiamo parecchie informazioni. La cardinalità dell'insieme $A$ la possiedi? Cioè da dove viene generato questo caso dove mancano delle soluzioni?
altra domanda: te parli di "elemento $a$" desumo che siano tanti e non esamini un unico caso, giusto?
l'algoritmo con rappr. binaria nel caso pessimo deve vedersi $O(2^n-2)$ elementi. Penso si possa fare pruning su alcuni casi ma dipende da come rispondi alle questioni che ti ho posto nel topic. Di meglio in senso di complessità non saprei, vediamo.
Comunque ora ho capito di cosa si sta parlando e della tua perplessità sulla ricerca esaustiva. Così a caldo a me pare tanto un lavoro di pattern e l'idea della distanza di hamming non è male. Se conosci informazioni su come viene generato $A$ incompleto si potrebbe lavorare anche su quello.
EDIT:
ho aggiunto alcune considerazioni.
Ciao,
sembra che ci siamo capiti..
a = [0.3 0.4 0.7]
Caso A completo. Uso 0.5 come soglia perchè: scorro i valori di a partendo da 0.3 se è inferiore a 0.5 allora la ricerca prosegue con tutti gli elementi di A che iniziano per 0 (gli altri sono sicuramente più lontani) poi prendo 0.4 che è di nuovo inferiore...alla fine prendo 1 perchè 0.7 è superiore a 0.5. L'elemento a minima distanza è 0 0 1. Questa è la ricerca dicotomica che ha complessita O(log(n)): dato che le possibili combinazioni sono O(2^n) si ottiene una complessità lineare O(n).
Caso A incompleto: il numero di elementi di A è noto perchè l'insieme A lo genero io. In questo caso non posso usare la ricerca dicotomica perchè alcuni elementi non sono presenti in A. Ho in mente un algoritmo che nel caso peggiore ha complessità O(2^n) mentre nel caso medio è molto inferiore. Se non hai idee migliori te lo presento.
grazie
ciao
sembra che ci siamo capiti.
.a = [0.3 0.4 0.7]
Caso A completo. Uso 0.5 come soglia perchè: scorro i valori di a partendo da 0.3 se è inferiore a 0.5 allora la ricerca prosegue con tutti gli elementi di A che iniziano per 0 (gli altri sono sicuramente più lontani) poi prendo 0.4 che è di nuovo inferiore...alla fine prendo 1 perchè 0.7 è superiore a 0.5. L'elemento a minima distanza è 0 0 1. Questa è la ricerca dicotomica che ha complessita O(log(n)): dato che le possibili combinazioni sono O(2^n) si ottiene una complessità lineare O(n).
Caso A incompleto: il numero di elementi di A è noto perchè l'insieme A lo genero io. In questo caso non posso usare la ricerca dicotomica perchè alcuni elementi non sono presenti in A. Ho in mente un algoritmo che nel caso peggiore ha complessità O(2^n) mentre nel caso medio è molto inferiore. Se non hai idee migliori te lo presento.
grazie
ciao
domanda: Su $n$ hai un limite superiore fissato di elementi?
con questo capisco che i dati ${0,1}$ li memorizzi in valori unitari cioè $A$ è un array multidimensionale, cioè non sono numeri interi rappresentanti con i bit.
Come sai quando $A$ è completo ed incompleto? Non mi pare serva fare una ricerca dicotomica se sei te a generare $A$.
Basta che lo calcoli te direttamente analizzando $a$ con il tuo fattore punto, costo $O(n)$ ma non legato alla ricerca dicotomica, non servirebbe nemmeno che generi $A$.
es. solito $a=[0.3,0.4,0.7]$
basta una ciclo for sche scandisce i vari elemento e sceglie la distanza
capito cosa intendo? è implicita la risposta (presenza o meno in A)cperchè il pattern (0,0,1) sai già essere elemento di $A$ se completo. Se no manca qualche dato che non dici a cui è legato $A$ oppure $a$.
Stando così la tua descrizione, se hai detto tutto, questo problema è simile ai classici SAT e capire se una data formula è soddisfacibile ed in questo caso la risposta alla tua prima domanda è Sì un problema NP.
Ma in questo caso è un'istanza decisionale di questo problema. Se consideriamo $a$ come la formula chiusa, il pattern formato da ${0,1}$ è l'assegnazione valida che rende vero $a$. In pratica noi abbiamo già in mano la soluzione, ma non sappiamo se è valido non sapendo se è tra le nostre soluzioni in $A$ (nondeterminismo...
che brutta parola...).
Quindi il problema si divide in:
- capire se un dato pattern è soddisfacibile (è presente in A?)
- in caso contrario trovarne un'approssimazione (distanza minima in A).
Lasciando perdere SAT che è solo per farti capire a cosa si lega il problema (penso che sia corretto).
C'è poco da fare nel caso pessimo ma si può utilizzare un po' inventiva con qualche tecnica. Tipo backtracking con pruning: analizzando i vari valori del pattern, al primo caso di insuccesso nella ricerca in A possiamo flippare un valore e continuare la ricerca o tornare indietro.
Comunque se vuoi descrivi l'algoritmo, così vediamo cosa fare
"erotavlas":
Ciao,
sembra che ci siamo capiti.
a = [0.3 0.4 0.7]
Caso A completo. Uso 0.5 come soglia perchè: scorro i valori di a partendo da 0.3 se è inferiore a 0.5 allora la ricerca prosegue con tutti gli elementi di A che iniziano per 0 (gli altri sono sicuramente più lontani) poi prendo 0.4 che è di nuovo inferiore...alla fine prendo 1 perchè 0.7 è superiore a 0.5. L'elemento a minima distanza è 0 0 1. Questa è la ricerca dicotomica che ha complessita O(log(n)): dato che le possibili combinazioni sono O(2^n) si ottiene una complessità lineare O(n).
con questo capisco che i dati ${0,1}$ li memorizzi in valori unitari cioè $A$ è un array multidimensionale, cioè non sono numeri interi rappresentanti con i bit.
Come sai quando $A$ è completo ed incompleto? Non mi pare serva fare una ricerca dicotomica se sei te a generare $A$.
Basta che lo calcoli te direttamente analizzando $a$ con il tuo fattore punto, costo $O(n)$ ma non legato alla ricerca dicotomica, non servirebbe nemmeno che generi $A$.
es. solito $a=[0.3,0.4,0.7]$
basta una ciclo for sche scandisce i vari elemento e sceglie la distanza
for int i = 0 to n
if(a[i]<0.5)
print 0
else print 1capito cosa intendo? è implicita la risposta (presenza o meno in A)cperchè il pattern (0,0,1) sai già essere elemento di $A$ se completo. Se no manca qualche dato che non dici a cui è legato $A$ oppure $a$.
Caso A incompleto: il numero di elementi di A è noto perchè l'insieme A lo genero io. In questo caso non posso usare la ricerca dicotomica perchè alcuni elementi non sono presenti in A. Ho in mente un algoritmo che nel caso peggiore ha complessità O(2^n) mentre nel caso medio è molto inferiore. Se non hai idee migliori te lo presento.
Stando così la tua descrizione, se hai detto tutto, questo problema è simile ai classici SAT e capire se una data formula è soddisfacibile ed in questo caso la risposta alla tua prima domanda è Sì un problema NP.
Ma in questo caso è un'istanza decisionale di questo problema. Se consideriamo $a$ come la formula chiusa, il pattern formato da ${0,1}$ è l'assegnazione valida che rende vero $a$. In pratica noi abbiamo già in mano la soluzione, ma non sappiamo se è valido non sapendo se è tra le nostre soluzioni in $A$ (nondeterminismo...
che brutta parola...).Quindi il problema si divide in:
- capire se un dato pattern è soddisfacibile (è presente in A?)
- in caso contrario trovarne un'approssimazione (distanza minima in A).
Lasciando perdere SAT che è solo per farti capire a cosa si lega il problema (penso che sia corretto).
C'è poco da fare nel caso pessimo ma si può utilizzare un po' inventiva con qualche tecnica. Tipo backtracking con pruning: analizzando i vari valori del pattern, al primo caso di insuccesso nella ricerca in A possiamo flippare un valore e continuare la ricerca o tornare indietro.
Comunque se vuoi descrivi l'algoritmo, così vediamo cosa fare
Se ho capito il problema (non ho letto tutti i post) tu vuoi cercare il punto $q in A subset RR^n$ più vicino ad un dato punto $p$. Se il problema è questo ti consiglio di utilizzare di utilizzare delle strutture dati che permettono il partizionamento dello spazio e di rispondere efficientemente a query di questo tipo. Credo che ad esempio i k-d tree potrebbero fare al caso tuo.
Lavori con un numero di dimensioni piuttosto basso oppure elevato? Nel secondo caso generalmente gli algoritmi di geometria computazionale fanno un po' fatica su dimensioni elevate.
Lavori con un numero di dimensioni piuttosto basso oppure elevato? Nel secondo caso generalmente gli algoritmi di geometria computazionale fanno un po' fatica su dimensioni elevate.
Ciao,
il limite su n non c'è in teoria. In pratica n è compreso tra 2 e 20.
Ci siamo capiti, ma se leggi i post io non ho mai parlato di rappresentazione binaria. Ho solo parlato di n-uple di 0 e 1.
Siccome A lo genero io, so quando è completo e quando non lo è.
Il caso A completo l'ho già risolto, come ti ho detto più volte nei vari post. La ricerca ha complessità lineare. (Uso la ricerca dicotomica e lo spazio degli stati è esponenziale).
L'algoritmo che hai riportato tu è quello che ti ho detto io nel post precedente.
Esatto!!! Se controlli il mio primo post ti avevo detto che è un problema NP-Completo. Ho chiesto a voi per vedere se avevate qualche buona idea nel caso di A incompleto.
Penso che la mia idea di algoritmo dovrebbe essere migliore del backtracking con pruning il quale analizza tutto lo spazio degli stati.
Algoritmo caso A incompleto
Con lo stesso criterio di ricerca del caso A completo trovo la n-pla a minima distanza euclidea a* (complessità lineare). Questo n-pla può o non essere nell'insieme A. Se c'è ho finito altrimenti procedo cosi: prendo tutte le n-ple a distanza di Hamming pari a 1 da a* e verifico se sono presenti in A. Di quelle presenti calcolo la distanza euclidea e prendo la n-pla a minima distanza euclidea e ho finito. Se non è presente nessuna n-pla a distanza di Hamming pari a 1 ripeto lo stesso procedimento con distanza di Hamming pari a 2 e cosi via. In questo caso la complessità è molto diminuita e dipende dagli elementi che sono presenti nell'insieme A incompleto.
Capito o ti devo fare un esempio?
il limite su n non c'è in teoria. In pratica n è compreso tra 2 e 20.
con questo capisco che i dati {0,1} li memorizzi in valori unitari cioè A è un array multidimensionale, cioè non sono numeri interi rappresentanti con i bit.
Ci siamo capiti, ma se leggi i post io non ho mai parlato di rappresentazione binaria. Ho solo parlato di n-uple di 0 e 1.
Siccome A lo genero io, so quando è completo e quando non lo è.
Il caso A completo l'ho già risolto, come ti ho detto più volte nei vari post. La ricerca ha complessità lineare. (Uso la ricerca dicotomica e lo spazio degli stati è esponenziale).
for int i = 0 to n
if(a[i]<0.5)
print 0
else print 1
L'algoritmo che hai riportato tu è quello che ti ho detto io nel post precedente.
Stando così la tua descrizione, se hai detto tutto, questo problema è simile ai classici SAT e capire se una data formula è soddisfacibile ed in questo caso la risposta alla tua prima domanda è Sì un problema NP.
Ma in questo caso è un'istanza decisionale di questo problema. Se consideriamo a come la formula chiusa, il pattern formato da {0,1} è l'assegnazione valida che rende vero a. In pratica noi abbiamo già in mano la soluzione, ma non sappiamo se è valido non sapendo se è tra le nostre soluzioni in A (nondeterminismo...
Quindi il problema si divide in:
- capire se un dato pattern è soddisfacibile (è presente in A?)
- in caso contrario trovarne un'approssimazione (distanza minima in A).
Lasciando perdere SAT che è solo per farti capire a cosa si lega il problema (penso che sia corretto).
C'è poco da fare nel caso pessimo ma si può utilizzare un po' inventiva con qualche tecnica. Tipo backtracking con pruning: analizzando i vari valori del pattern, al primo caso di insuccesso nella ricerca in A possiamo flippare un valore e continuare la ricerca o tornare indietro.
Esatto!!! Se controlli il mio primo post ti avevo detto che è un problema NP-Completo. Ho chiesto a voi per vedere se avevate qualche buona idea nel caso di A incompleto.
Penso che la mia idea di algoritmo dovrebbe essere migliore del backtracking con pruning il quale analizza tutto lo spazio degli stati.
Algoritmo caso A incompleto
Con lo stesso criterio di ricerca del caso A completo trovo la n-pla a minima distanza euclidea a* (complessità lineare). Questo n-pla può o non essere nell'insieme A. Se c'è ho finito altrimenti procedo cosi: prendo tutte le n-ple a distanza di Hamming pari a 1 da a* e verifico se sono presenti in A. Di quelle presenti calcolo la distanza euclidea e prendo la n-pla a minima distanza euclidea e ho finito. Se non è presente nessuna n-pla a distanza di Hamming pari a 1 ripeto lo stesso procedimento con distanza di Hamming pari a 2 e cosi via. In questo caso la complessità è molto diminuita e dipende dagli elementi che sono presenti nell'insieme A incompleto.
Capito o ti devo fare un esempio?
"Deckard":
Se ho capito il problema (non ho letto tutti i post) tu vuoi cercare il punto $q in A subset RR^n$ più vicino ad un dato punto $p$. Se il problema è questo ti consiglio di utilizzare di utilizzare delle strutture dati che permettono il partizionamento dello spazio e di rispondere efficientemente a query di questo tipo. Credo che ad esempio i k-d tree potrebbero fare al caso tuo.
Lavori con un numero di dimensioni piuttosto basso oppure elevato? Nel secondo caso generalmente gli algoritmi di geometria computazionale fanno un po' fatica su dimensioni elevate.
Ciao, esatto devo fare una cosa simile. Non conosco i k-d tree, ma mi informerò. Le dimensioni sono piuttosto basse n è compreso tra 2 e 20.
il limite su n non c'è in teoria. In pratica n è compreso tra 2 e 20.
....
Ci siamo capiti, ma se leggi i post io non ho mai parlato di rappresentazione binaria. Ho solo parlato di n-uple di 0 e 1.
Siccome A lo genero io, so quando è completo e quando non lo è.
infatti io sono andato ad ipotesi su più rappresentazioni che avresti potuto usare, binaria, array od altro.
Chiederti il limite era per capire se avresti potuto utilizzare la rappresentazione binaria e le operazioni chiamate bit-wise. Comprimendo le informazioni ed avendo operazioni più efficienti, in casi esponenziali, possono essere molto d'aiuto.
Il caso A completo l'ho già risolto, come ti ho detto più volte nei vari post. La ricerca ha complessità lineare. (Uso la ricerca dicotomica e lo spazio degli stati è esponenziale).
...
L'algoritmo che hai riportato tu è quello che ti ho detto io nel post precedente.
Quello che cidi te ha complessità $O(nlogn)$. Mi baso su ciò che hai descritto. Per ogni elemento di $a$ cerchi il corrispondente elemento in $A$ (ristretto ogni volta a tutti gli elementi validi all'elemento corrento cercato).
Basterebbe una scansione lineare su $a$ calcolare il suo valore {0,1}, e non servirebbe guardare $A$ perchè sai già essere compreso.
es. se hai
$a=[0.4 0.5]$
$A=[00,01,10,11]$
il tuo algoritmo:
guardi $0.4$ e confronti con $0.5$ risultato $0$
fai ricerca binaria su $A$ risultati: $A'={00,01}$
guardi $0.5$ risultato $0$
fai ricerca binaria su $A'$ risultato: ${00}$
ma cosa serve fare la ricerca? basta guardare solo $a$.
guardi $0.4$ e confronti con $0.5$ = 0
guardi $0.5$ risultato = 0
risultato finale ${00}$
è incluso in $A$? certo, perchè è completo da definizione.
Esatto!!! Se controlli il mio primo post ti avevo detto che è un problema NP-Completo. Ho chiesto a voi per vedere se avevate qualche buona idea nel caso di A incompleto.
pensavo ti servisse una conferma.
Algoritmo caso A incompleto
Con lo stesso criterio di ricerca del caso A completo trovo la n-pla a minima distanza euclidea a* (complessità lineare). Questo n-pla può o non essere nell'insieme A. Se c'è ho finito altrimenti procedo cosi: prendo tutte le n-ple a distanza di Hamming pari a 1 da a* e verifico se sono presenti in A. Di quelle presenti calcolo la distanza euclidea e prendo la n-pla a minima distanza euclidea e ho finito. Se non è presente nessuna n-pla a distanza di Hamming pari a 1 ripeto lo stesso procedimento con distanza di Hamming pari a 2 e cosi via. In questo caso la complessità è molto diminuita e dipende dagli elementi che sono presenti nell'insieme A incompleto.
prendere gli insiemi a distanza $1$ vuol dire calcolare ogni coppia di elementi, e perciò spaziare tutto l'insieme $A$. Suppongo avendo detto che non hai limiti teorici tilizzi degli array, la complessità teorica solo in questo passo è esponenziale. Visto che in pratica $n<=20$ utilizzare una rapprezentazione binaria è qualcosa di parecchio consigliato.
L'idea della distanza di Hamming con valutazione della distanza euclidea non è male, ma bisogna utilizzarla in altro modo con tecniche più sofisticate, a mio parere si è ancora in casi con troppe possibili divergenze esponenziali. Io ci vedrei bene una tecnica che dirigie la soluzione valutando a priori una parte di A (per ridurre la ricerca esaustiva), ci penso ti faccio sapere...
Oppure se l'idea di Deckard è applicabile si può sbordare in altri algoritmi, ma che non conosco.
Quello che cidi te ha complessità O(nlogn). Mi baso su ciò che hai descritto. Per ogni elemento di a cerchi il corrispondente elemento in A (ristretto ogni volta a tutti gli elementi validi all'elemento corrento cercato).
Basterebbe una scansione lineare su a calcolare il suo valore {0,1}, e non servirebbe guardare A perchè sai già essere compreso.
es. se hai
a=[0.40.5]
A=[00,01,10,11]
il tuo algoritmo:
guardi 0.4 e confronti con 0.5 risultato 0
fai ricerca binaria su A risultati: A′={00,01}
guardi 0.5 risultato 0
fai ricerca binaria su A′ risultato: {00}
ma cosa serve fare la ricerca? basta guardare solo a.
guardi 0.4 e confronti con 0.5 = 0
guardi 0.5 risultato = 0
risultato finale {00}
è incluso in A? certo, perchè è completo da definizione.
Il mio algoritmo fa quello che dici tu semplicemente fa il confronto degli elementi. Dato che i possibili elementi sono O(2^n) e la ricerca è logaritmica O(log n) si arriva a O(n).
prendere gli insiemi a distanza 1 vuol dire calcolare ogni coppia di elementi, e perciò spaziare tutto l'insieme A. Suppongo avendo detto che non hai limiti teorici tilizzi degli array, la complessità teorica solo in questo passo è esponenziale. Visto che in pratica n≤20 utilizzare una rapprezentazione binaria è qualcosa di parecchio consigliato.
L'idea della distanza di Hamming con valutazione della distanza euclidea non è male, ma bisogna utilizzarla in altro modo con tecniche più sofisticate, a mio parere si è ancora in casi con troppe possibili divergenze esponenziali. Io ci vedrei bene una tecnica che dirigie la soluzione valutando a priori una parte di A (per ridurre la ricerca esaustiva), ci penso ti faccio sapere...
Per esempio se n=4 a = [0.3 0.8 0.45 0.6] a* = [0 1 0 1] nel caso A fosse completo ci sarebbero 4 elementi a distanza di Hamming 1 6 elementi a distanza di Hamming 2 4 elementi a distanza di Hamming 3 e 1 elemento a distanza di Hamming 4. Nella pratica A è incompleto e il numero di elementi è molto minore. In casi fortunati la ricerca si arresta agli elementi a distanza di Hamming 1 nel caso peggiore si arriva all'elemento a distanza di Hamming massima 4 (questo accade solo se l'insieme A contiene un solo elemento 1 0 1 0). Per la rappresentazione dell'insieme A uso un contenitore associativo che ha complessità di ricerca degli elementi logaritmica (std::set del STL del C++).
Se ti viene in mente qualcosa migliore sono felice
Oppure se l'idea di Deckard è applicabile si può sbordare in altri algoritmi, ma che non conosco.
Ho guardato i k-d tree, praticamente fanno la stessa cosa che fa il mio algoritmo quando A è completo. Suddividono i dati in due parti per ogni variabile presente. Non mi è chiaro cosa succede se il k-d tree non è pieno ma ci sono solo alcuni elementi. C'è un modo efficiente per calcolare l'elemento a minore distanza?
ciao
"erotavlas":
Il mio algoritmo fa quello che dici tu semplicemente fa il confronto degli elementi. Dato che i possibili elementi sono O(2^n) e la ricerca è logaritmica O(log n) si arriva a O(n).
azz hai ragione, ho fatto due conti su carta, mi son ingannato da solo...sorry.
Il mio era per non creare l'insieme $A$ se completo visto che usavi quel parametro $0.5$. Serviva più per risparmiare memoria guardando solo $a$, diciamo ottimizzazione inutile.
a* = [0 1 0 1]
una cosa non chiarita, a* lo calcoli ancora valutandolo con il fattore 0.5 per sapere se è vicino a $0$ od $1$ od utilizzi un altro fattore o criterio nei due casi?
dopo questo dovrebbe esserci più o meno tutto ciò riguarda il problema, spero.
Per la rappresentazione dell'insieme A uso un contenitore associativo che ha complessità di ricerca degli elementi logaritmica (std::set del STL del C++).
ok.
Secondo me l'idea che proposi ieri
è ben applicabile senza troppi giramenti di tecniche, semplicemente utilizziamo quella che è chiamata perturbative search (all'incirca) modifichiamo un valore per dirigeci alla soluzione cercata.
Sia $a*$ un insieme ordinato di valori ${0,1}$ (pattern), e $A$ l'insieme delle nostra soluzioni composto anch'esso da insiemi ${0,1}$.
Il problema è cercare $a*$ in $A$, se non lo contiene, cercare la soluzione parziale più vicina ad $a*$. Questo vuol dire trovare la soluzione che abbia distanza di Hamming minima (e distanza euclidea conforme). Fin qui è il tuo formulazione.
Ma possiamo forzare noi a far corrispondere $a*$ agli elementi di $A$, perturbando il pattern finchè la distanza minima di hamming sia $0$.
In pratica senza troppi discorsi.
Prendi la ricerca binaria, se c'è SEMPRE corrispondenza il caso è sempre quello, se non c'è corrispondenza con l'elemento attuale di $a*$ flippiamo il valore da $0->1$ o $1->0$ (flippare: complementare un valore) e facciamo ripartire la ricerca binaria su questo valore allo stesso livello. E continuamo... alla fine avremo il valore minimo cercato.
che ne dici? a me pare sensato, dipende se ha significato anche nel problema orginale (visto che si parla di insiemi reali).
analizzando i vari valori del pattern, al primo caso di insuccesso nella ricerca in A possiamo flippare un valore e continuare la ricerca o tornare indietro
è ben applicabile senza troppi giramenti di tecniche, semplicemente utilizziamo quella che è chiamata perturbative search (all'incirca) modifichiamo un valore per dirigeci alla soluzione cercata.
Sia $a*$ un insieme ordinato di valori ${0,1}$ (pattern), e $A$ l'insieme delle nostra soluzioni composto anch'esso da insiemi ${0,1}$.
Il problema è cercare $a*$ in $A$, se non lo contiene, cercare la soluzione parziale più vicina ad $a*$. Questo vuol dire trovare la soluzione che abbia distanza di Hamming minima (e distanza euclidea conforme). Fin qui è il tuo formulazione.
Ma possiamo forzare noi a far corrispondere $a*$ agli elementi di $A$, perturbando il pattern finchè la distanza minima di hamming sia $0$.
In pratica senza troppi discorsi.
Prendi la ricerca binaria, se c'è SEMPRE corrispondenza il caso è sempre quello, se non c'è corrispondenza con l'elemento attuale di $a*$ flippiamo il valore da $0->1$ o $1->0$ (flippare: complementare un valore) e facciamo ripartire la ricerca binaria su questo valore allo stesso livello. E continuamo... alla fine avremo il valore minimo cercato.
che ne dici? a me pare sensato, dipende se ha significato anche nel problema orginale (visto che si parla di insiemi reali).
una cosa non chiarita, a* lo calcoli ancora valutandolo con il fattore 0.5 per sapere se è vicino a 0 od 1 od utilizzi un altro fattore o criterio nei due casi?
dopo questo dovrebbe esserci più o meno tutto ciò riguarda il problema, spero.
Si come hai detto tu.
Mi potresti fare un esempio del tuo algoritmo? Supponiamo a = [0.3 0.8 0.75] e A = {0 0 0; 0 1 0; 1 1 1}.
"erotavlas":
Mi potresti fare un esempio del tuo algoritmo? Supponiamo a = [0.3 0.8 0.75] e A = {0 0 0; 0 1 0; 1 1 1}.
ah forse cambia un attimo la scelta del vicino, visto che considera la distanza euclidea che m'ero scordato.
con la descrizione sopra il minimo risulterebbe: [010]
dimmi un po' considerando questo:
a*=[1000] ed A=[0000,1001] quale consideri minimo? mi pare sia un insieme e non solo uno.
a*=[0100] ed A=[0110,1100] uguale.
cioè in questi casi la soluzione non è unica!! all'inizio mi pareva parlassi di "insieme di distanze minime".
a seconda della risposta cambia la scelta, perchè in caso si introduce una tecnica simile al backtracking, ma si mette una proibizione sulla massima profondità di ramificazione di $1$ sulla distanza di hamming.
con l'algoritmo che ho proposto il singolo minimo sarebbe:
1. [1001]
2. [0110]
Il minimo è singolo. Con il mio algoritmo lo cerco in un sottoinsieme di n-plu che sono quelle a minima distanza di Hamming. Date le n-ple che si trovano a minima distanza cerco il minimo con la distanza euclidea. In questo modo si evitano problemi di minimi multipli.
Ti torna?
prendo tutte le n-ple a distanza di Hamming pari a 1 da a* e verifico se sono presenti in A. Di quelle presenti calcolo la distanza euclidea e prendo la n-pla a minima distanza euclidea e ho finito.
Ti torna?
Allora,
La distanza euclidea allora la calcoli utilizzando $a$ modificato con 0 o 1 in corrispondenza del valore approssimato contenuto in $A$. confermi?
Ti torna?[/quote]
devo dirti che non ci avevo fatto caso a questa caratteristica, cioè avevo letto un po' in fretta e compreso altro (troppi impegni...).
Te ti calcoli ad ogni insuccesso un nuovo sottoinsieme (al massimo $n$ insiemi) e verifichi. Il caso peggiore è quando la distanza di hamming è $n$ perciò sarà genererato, a fine iterazione, tutto lo spazio che è $2^n$.
Io avevo compreso che calcolavi e raggruppavi le distanze direttamente su $A$ e su questo cercavi.
Sì l'algoritmo è migliore come lo hai descritto ora (lo avevi..) Diciamo che non è malaccio ma c'è sempre il rischio di divergere all'esponenziale e questo non è buono.
Perciò vedo due possibili strade se si vuole migliorare (od altre che non sono tra le mie competenze v. es. di Deckard):
- Una possibilità è utilizzare tecniche di ricerca (es. ricerca perturbativa). L'algoritmo che ho proposto non funziona con alcuni pattern, e questo sarà sempre esponenziale se non si introducono (come ho più volte accennato) tecniche particolari, una di queste è la ricerca locale (nelle sue varianti) che però devo trovare il tempo di verificarne l'applicabilità.
- Una seconda idea così che mi è venuta in mente, sarebbe quella di utilizzare una proprietà sulla distanza di hamming, cioè il concetto di peso di hamming esteso per ogni coppia (invece che il solo numero 0) oppure un concetto simile ad una distribuzione probabilistica nel raggruppamento delle distanze. Rimanendo all'incirca sul tuo algoritmo. Invece che generarci le distanze di hamming, utilizziamo la distribuzione sul nostro pattern per indovinare che ci sta in $A$ e vincolare/indicizzare l'algoritmo di ricerca. Ho trovato qualcosa su questo tema sembra interessante, è una possiblità.
EDIT: aggiunte alcune considerazioni
"erotavlas":
Il minimo è singolo. Con il mio algoritmo lo cerco in un sottoinsieme di n-plu che sono quelle a minima distanza di Hamming. Date le n-ple che si trovano a minima distanza cerco il minimo con la distanza euclidea. In questo modo si evitano problemi di minimi multipli.
La distanza euclidea allora la calcoli utilizzando $a$ modificato con 0 o 1 in corrispondenza del valore approssimato contenuto in $A$. confermi?
[quote]
prendo tutte le n-ple a distanza di Hamming pari a 1 da a* e verifico se sono presenti in A. Di quelle presenti calcolo la distanza euclidea e prendo la n-pla a minima distanza euclidea e ho finito.
Ti torna?[/quote]
devo dirti che non ci avevo fatto caso a questa caratteristica, cioè avevo letto un po' in fretta e compreso altro (troppi impegni...).
Te ti calcoli ad ogni insuccesso un nuovo sottoinsieme (al massimo $n$ insiemi) e verifichi. Il caso peggiore è quando la distanza di hamming è $n$ perciò sarà genererato, a fine iterazione, tutto lo spazio che è $2^n$.
Io avevo compreso che calcolavi e raggruppavi le distanze direttamente su $A$ e su questo cercavi.
Sì l'algoritmo è migliore come lo hai descritto ora (lo avevi..) Diciamo che non è malaccio ma c'è sempre il rischio di divergere all'esponenziale e questo non è buono.
Perciò vedo due possibili strade se si vuole migliorare (od altre che non sono tra le mie competenze v. es. di Deckard):
- Una possibilità è utilizzare tecniche di ricerca (es. ricerca perturbativa). L'algoritmo che ho proposto non funziona con alcuni pattern, e questo sarà sempre esponenziale se non si introducono (come ho più volte accennato) tecniche particolari, una di queste è la ricerca locale (nelle sue varianti) che però devo trovare il tempo di verificarne l'applicabilità.
- Una seconda idea così che mi è venuta in mente, sarebbe quella di utilizzare una proprietà sulla distanza di hamming, cioè il concetto di peso di hamming esteso per ogni coppia (invece che il solo numero 0) oppure un concetto simile ad una distribuzione probabilistica nel raggruppamento delle distanze. Rimanendo all'incirca sul tuo algoritmo. Invece che generarci le distanze di hamming, utilizziamo la distribuzione sul nostro pattern per indovinare che ci sta in $A$ e vincolare/indicizzare l'algoritmo di ricerca. Ho trovato qualcosa su questo tema sembra interessante, è una possiblità.
EDIT: aggiunte alcune considerazioni
Allora, ho guardato quello che si poteva fare con la ricerca locale, rimanendo su un modello generale come Iterative Improvement (ibrida con funzione di proibizione), si potrebbe generare un algoritmo abbastanza interessante.
La cosa che però deve esserci è che l'insieme sia ordinato secondo la struttura numerica (binaria od intera), visto che utilizzi qualcosa che è un insieme con chiave, questo forse non è garantito perciò non mi dilungo oltre non avendo molta voglia di disquisire su strutture dati, penso che ormai le hai implementate.
L'algoritmo che proposi qualche post sopra è backtracking con funzione di step 1-flip. E' implementabile e corretto, ma è pur sempre esponenziale. Se si vuole andare su questa strada esiste un algoritmo chiamata A*. Utilizza delle euristiche particolari per tagliare nettamente percorsi non ottimi, e simile al branch&bound, ma il discorso è sempre quello, si introducono cose complesse.
comunque metto in spoiler quello che potrebbe essere un modello di ricerca locale, anche se si complica.
Se vorrai si può far tutto, ma non so se ne vale la pena, essendo il tuo algoritmo possibilmente esponenziale, ma semplice.
La cosa che però deve esserci è che l'insieme sia ordinato secondo la struttura numerica (binaria od intera), visto che utilizzi qualcosa che è un insieme con chiave, questo forse non è garantito perciò non mi dilungo oltre non avendo molta voglia di disquisire su strutture dati, penso che ormai le hai implementate.
L'algoritmo che proposi qualche post sopra è backtracking con funzione di step 1-flip. E' implementabile e corretto, ma è pur sempre esponenziale. Se si vuole andare su questa strada esiste un algoritmo chiamata A*. Utilizza delle euristiche particolari per tagliare nettamente percorsi non ottimi, e simile al branch&bound, ma il discorso è sempre quello, si introducono cose complesse.
comunque metto in spoiler quello che potrebbe essere un modello di ricerca locale, anche se si complica.
Se vorrai si può far tutto, ma non so se ne vale la pena, essendo il tuo algoritmo possibilmente esponenziale, ma semplice.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo