Come ordinare gli oggetti basati solo su relazioni "meno delle" relazioni?
-
29-09-2020 - |
Domanda
Dì che ho n oggetti, ognuno con un valore sconosciuto, e una matrice Z. Z. In tale che Z (I, J)= 1 se il valore dell'oggetto sono inferiore al valore dell'oggetto J e Z (I, J)= 0 altrimenti.Come posso ordinare questi oggetti n, data solo la matrice Z?
Soluzione
Quello che stai cercando è un Complison Sort . Si prega di dare un'occhiata a quell'articolo.
.
Dichiariamo chiaramente il requisito per eventuali due oggetti dati, oggetto I e oggetto J quando appaiono nell'elenco ordinato finale. Oggetto che dovrei verificarsi prima dell'oggetto J se z (I, J)= 1. Oggetto che posso verificare prima o dopo l'oggetto J se z (I, J)= Z (J, I)= 0.
Come menzionato Vonbrand, dovremmo supporre che la matrice Z specifica una relazione "inferiore a" ben definita o, in termini di matematica, un ordine rigoroso totale sui valori degli oggetti. In caso contrario, gli oggetti dati potrebbero non essere ordinati.
- .
- z [i, j]= 0 se z [j, i]= 1. Altrimenti, non possiamo ordinare oggetto I e oggetto j.
- z [j, i]= 0 se z [i, k]= 1 e z [k, j]= 1 per alcuni k. Altrimenti, non possiamo ordinare oggetto I, J e K (pensa a carta-forbici-rock).
.
Supponiamo che Z specifica una relazione "inferiore a" ben definita. Quindi definisce anche una " $ \ LE $ " Funzionamento del confronto naturalmente. Vale a dire, se z (j, i)= 0, allora oggetto I $ \ le $ oggetto j. Quindi possiamo applicare qualsiasi tipo di confronto per ordinare la $ n $ oggetto.
Quasi tutti gli algoritmi di smistamento sono ordinamenti di confronto. Ad esempio, Quicksort, MergeSort, ordinamento di inserimento, selezione ordinamento e bolla ordinamento. Un'eccezione notevole è Conteggio Ordina .