Algoritmo para verificar a transitividade da relação?
-
08-07-2019 - |
Pergunta
Eu preciso verificar se relação é transitiva ou não?
Você poderia por favor sugerir algum algoritmo para verificar a transitividade das relações?
Eu estou armazenando relação como um boolean matriz não é 1 se os elementos estão relacionados outro sábio 0 como em gráficos.
Graças.
Solução
Muito mais simples algoritmo como minha versão Mapa / Set (excluído), agora com matriz de boolean. Talvez este seja mais fácil de entender, mesmo se você não sabe Java?
public class Trans
{
final static int SIZE = 4;
static boolean isTransitive(boolean[][] function)
{
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
{
if (function[i][j])
{
for (int k = 0; k < SIZE; k++)
{
if (function[j][k] && !function[i][k])
{
return false;
}
}
}
}
}
return true;
}
public static void main(String[] args)
{
boolean[][] function = new boolean[SIZE][SIZE];
for (int i = 0; i < SIZE; i++)
{
function[i] = new boolean[SIZE];
}
function[0][1] = true;
function[1][2] = true;
function[0][2] = true;
function[0][3] = true;
function[1][3] = true;
System.out.println(isTransitive(function));
}
}
Outras dicas
Apesar de isso soa totalmente como lição de casa ...
Você precisa para armazenar suas relações de modo que você pode procurá-los pelo antecedente muito rapidamente. Depois, você pode descobrir as relações transitivos do tipo A-> B-> C, adicioná-los ao mesmo armazenamento, e continuar a olhar para cima A-> B-> C-> D, etc etc ...
ordenação topológica pode ser a direção certa. A relação é transitória, se não houver circuitos na sua representação grafo orientado. Se você se preocupa com velocidade, algoritmos de grafos são provavelmente o caminho a percorrer.