Come modellare l'incertezza euristica durante l'ordinamento dei dati?

Question

Come modellare l'incertezza euristica durante l'ordinamento dei dati?

#1 da (2 voti)
#2 da (2 voti)
#3 da (1 voti)

3

Gli algoritmi di ordinamento presuppongono che tu abbia un comparatore definito. Ad esempio, se si ordinano gli interi A e B, l'operazione A > B consente di determinare se A deve essere prima o dopo B.

Immagina di voler implementare un ordinamento, ma piuttosto che un comparatore definito e coerente, il confronto usa un'euristica di un certo senso - quindi è non una garanzia che sarà corretta. Un esempio potrebbe essere analogo a come gli oculisti identificano la tua prescrizione. Mostrano due ricette e chiedono quale è meglio. In alcuni casi, come paziente potresti non rispondere correttamente per due valori vicini. Per valori molto distanti, sarai più preciso.

Se ad esempio vuoi confrontare i valori numerici, puoi modellarlo come un comparatore personalizzato come:

public class HeuristicComparator implements Comparator {

    @Override
    public int compare(double val1, double val2) {
        double adjustedVal1 = val1 + Math.random();
        double adjustedVal2 = val2 + Math.random();    

        return Double.compare(adjustedVal1, adjustedVal2);
    }

}

In questo esempio di base, assegno arbitrariamente alcune variazioni casuali all'operazione di confronto, dicendo efficacemente che qualsiasi doppio valore inferiore a 1.000 potrebbe potrebbe essere ordinato in modo errato. 1.5 potrebbe essere inferiore a 1,3, ma solo alcune volte.

Quali altre strategie ci sono per modellare un comportamento euristico come questo piuttosto che un comparatore? Sembra che tu possa modificare anche la logica di ordinamento (forse saltare i punti casuali, modificare un ordinamento per non "finire" tutti i tipi adiacenti)? Quali algoritmi di ordinamento possono essere facilmente modificati per abbinare questo comportamento?

O sarebbe sempre preferibile modificare il comparatore?

algorithms sorting heuristics

posta enderland 17.11.2015 - 04:25

fonte

3 risposte

2

Sei sicuro di voler implementare l'interfaccia Comparator , invece di crearne uno più adatto?

Ad esempio, l'esempio randomizzato che fornisci non può soddisfare il requisito di transitività di Comparator e, naturalmente, non può mai essere coerente con equals .

Quindi potresti ottenere alcune brutte sorprese (compresa la possibilità di non terminare) se dovessi usarlo con contenitori standard e / o algoritmi di ricerca / ordinamento

risposta data 18.11.2015 - 21:56

fonte

1

Per il tuo esempio, puoi visualizzare ogni elemento dell'array come un intervallo dal valore minimo possibile al valore massimo possibile. Quindi potresti scegliere un intervallo a caso, ridurlo iterativo all'incrocio di ciò che ne è rimasto e uno qualsiasi degli intervalli originali che ancora interseca, quindi ordinare rapidamente usando quell'intervallo come perno e considerando l'intersezione come uguaglianza. (Effettivamente si utilizza l'ordinamento rapido, leggermente modificato perché è necessario ridurre l'intervallo tramite l'intersezione per garantire la correttezza).

Nel caso generale, dovresti specificare cosa vuoi e come funziona l'euristica. Ti interessa la tolleranza agli errori per un euristico non deterministico non sempre accurato (se così, le reti di ordinamento fault tolerant potrebbero essere rilevanti)? Se si desidera la tolleranza ai guasti per un'euristica deterministica difettosa, non c'è davvero nulla da fare. Ci sono vari gradi di successo nel tipo di cui vuoi negoziare per tempo? Il caso generale della tua domanda è troppo ampio per rispondere.

risposta data 17.11.2015 - 23:54

fonte

Leggi altre domande sui tag algorithms sorting heuristics

Perché Node non supporta più loop di eventi in un processo? Quale struttura dati Lisp usare?

score 2 · Accepted Answer

È preferibile modificare il comparatore solo se puoi accettare un numero come risultato sfocato e il calcolo richiede solo i valori di confronto sinistro e destro.

public int compare(double val1, double val2) {

    int magic = andThenAMiracleOccurs(val1, val2);    

    return magic;
}

Cosa potrebbe esserci in andThenAMiracleOccurs ? Quasi niente. Mi viene in mente una rete logica adattiva. L'utilizzo di un ALN consentirebbe di eseguire minimi quadrati adatti a una curva; l'output dato l'input potrebbe essere quasi qualsiasi tipo di mappatura o approssimazione da input a output.

Ovviamente, le funzioni essendo ciò che sono, val1 e val2 potrebbero essere praticamente qualsiasi cosa.

public int compare(Vector set1, Vector set2) {

    int magic = someFuzzyComparator(set1, set2);    

    return magic;
}

Ecco qualcosa di un po 'meno astratto:

public int Compare(string string1, string string2)
{
    return SignedLevenshteinDistance(string1, string2);
}

che ti direbbe non solo se due stringhe sono uguali, ma ti dirà anche se sono diverse se non sono uguali e quale direzione variano in ordine alfabetico.

I comparatori possono essere enormemente flessibili, nelle giuste circostanze (vale a dire ovunque sia necessario un ordinamento speciale in una raccolta che può essere modellato sul confronto di due input e produrre un output intero con segno).