5

Bom, como trabalho da faculdade, tenho que criar um algoritmo que, dado certo arquivo com x números, seja capaz de verificar qual a maior sequência de números que, em base 6, respeitem as as seguintes regras:

  1. A sequência deve ser crescente
  2. De um número para outro da sequência, somente um dígito pode mudar
  3. Todos os números da sequência tem que ter o mesmo número de digitos (15-->10015 não é válido)

Um exemplo seria:

O arquivo contém os números 782, 229, 446, 527, 874, 19, 829, 70, 830, 992, 430 e 649.

Ou seja, em base 6: 3342, 1021, 2022, 2235, 4014, 31, 3501, 154, 3502, 4332, 1554 e 3001.

Portanto, a maior sequência respeitando essas regras seria: 649, 829 e 830, que corresponde a 3001, 3501 e 3502 em base 6.

Certo, os arquivos não são assim tão simples, há arquivos que chegam a ter até 100.000 números, portanto, criei um grafo. Eu tentei tanto com matriz como com lista de adjacências. Adicionar os vértices e as arestas (ou seja, quais são os números que respeitam as regras para um número x) não foi um problema, meu problema é caminhar no grafo, pois pesquisando na internet só achei caminhamento mínimo, mas o que eu preciso é: achar o maior caminho.

Tentei com DFS mas o resultado não é o que eu quero.

Meu código é o seguinte:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class DirectedGraphList
{
    private class Vertice
    {
        private String item;
        private boolean Visitado;
        private ArrayList<Vertice> lst = new ArrayList<Vertice>();

        public Vertice(String item) {
            this.item = item;
        }
        public String getItem() {
            return this.item;
        }
        public void setItem(String item) {
            this.item = item;
        }
        public void addAdjacent(Vertice v) {
            if (!lst.contains(v))
                lst.add(v);
        }
        public ArrayList<Vertice> getAdjacents() {
            return lst;
        }
        public Vertice getAdjacent(int i) {
            Vertice res = null;
            if ((i >= 0) && (i < lst.size()))
                res = lst.get(i);
            return res;
        }
        public int getDegree(){
            return lst.size(); 
        }
    }

    private ArrayList<Vertice> vert;

    public DirectedGraphList() {
        vert = new ArrayList<Vertice>();
    }

    private Vertice searchVerticeRef(String item)
    {
        Vertice res = null;
        int i;

        for (i = 0; ((i < vert.size()) && !vert.get(i).getItem().equals(item)); i++);

        if (i < vert.size())
            res = vert.get(i);

        return res;
    }

    public void addVertice(String item)
    {
        if (searchVerticeRef(item) == null) 
        {
            Vertice novo = new Vertice(item);
            vert.add(novo);
        }
    }

    public void addEdge(String strOrig, String strDest)
    {
        Vertice vAux1 = searchVerticeRef(strOrig);
        Vertice vAux2 = searchVerticeRef(strDest);

        if (vAux1 == null)
            throw new IllegalArgumentException("Aresta origem invalida: " + strOrig);
        else if (vAux2 == null)
            throw new IllegalArgumentException("Aresta destino invalida: " + strDest);
        else
        {
            vAux1.addAdjacent(vAux2);
        }
    }

    public int getNumVertices() {
        return vert.size();
    }

    public int getDegree(String vertice)
    {
        int i, j, c = 0;
        Vertice v = searchVerticeRef(vertice);
        if (v != null)
        {
            // grau de saida
            c += v.getDegree();

            // grau de entrada
            for (i = 0; i < vert.size(); i++)
            {
                if (!vert.get(i).getItem().equals(vertice))
                {
                    for (j = 0; j < vert.get(i).getDegree(); j++)
                    {
                        if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
                            c++;
                    }                    
                }
            }
        }
        return c;
    }

    public ArrayList<String> getAllAdjacents(String vertice)
    {
        ArrayList<String> res = null;
        Vertice v = searchVerticeRef(vertice);
        if (v != null)
        {
            res = new ArrayList<String>();
            for (int j = 0; j < v.getDegree(); j++)
                res.add(v.getAdjacent(j).getItem());
        }
        return res;
    }

    public ArrayList<String> getSources()
    {
        ArrayList<String> res = new ArrayList<String>();
        boolean checked;
        String vertice;

        for (int k=0; k<vert.size(); k++)
        {
            vertice = vert.get(k).getItem();

            checked = false;
            for (int i=0; i<vert.size(); i++)
            {
                for (int j=0; j<vert.get(i).getDegree(); j++)
                {
                    if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
                    {
                        checked = true;
                        break;
                    }
                }
            }

            if (!checked)
                res.add(vertice);
        }
        return res;
    }

    public ArrayList<String> getSinks()
    {
        ArrayList<String> res = new ArrayList<String>();

        for (int i=0; i<vert.size(); i++)
        {
            if (vert.get(i).getAdjacents().isEmpty())
                res.add(vert.get(i).getItem());
        }
        return res;
    }

    public void showInfo()
    {
        System.out.print("V = { ");
        for (int i = 0; i < vert.size()-1; i++)
            System.out.printf("%s, ", vert.get(i).getItem());
        System.out.printf("%s }\n", vert.get(vert.size()-1).getItem());

        ArrayList<String> arestas = new ArrayList<String>();
        for (int i = 0; i < vert.size(); i++)
            for (int j = 0; j < vert.get(i).lst.size(); j++)
                arestas.add(String.format("(%s, %s)", vert.get(i).getItem(), vert.get(i).getAdjacent(j).getItem()));

        System.out.print("E = {\n");
        if (!arestas.isEmpty()) {
            System.out.printf("      %s", arestas.get(0));

            for (int i = 1; i < arestas.size(); i++)
                System.out.printf(",\n      %s", arestas.get(i));
        }
        System.out.println("\n    }");
    }
    public static void criaArray(ArrayList<Integer> a,String nome) throws FileNotFoundException{
        try{
            FileReader ler= new FileReader(nome);
            BufferedReader arq=new BufferedReader(ler);
            int parsedStr;
            String str=arq.readLine();
            while(str!=null){
                parsedStr=Integer.parseInt(str);
                a.add(parsedStr);
                str=arq.readLine();
            }
        }
        catch(IOException e){
            System.out.println("Erro na abertura do arquivo: "+
                    e.getMessage());
        }
    }
    public static int diferente(String a,String b){
        int diferentes=0;
        if(a.length()==b.length()){
            for(int i=0;i<a.length();i++){
                if(a.charAt(i)!=b.charAt(i))
                    diferentes++;
            }
        }
        else 
            diferentes=2;
        return diferentes;
    }

    public static boolean possibilidades(DirectedGraphList graph,String a,ArrayList<Integer> array){
        int diferentes=0;
        for(int i=0;i<array.size();i++){
            String numero=Integer.toString(array.get(i),6);
            diferentes=diferente(numero,a);
            if(diferentes==1){
                graph.addEdge(a,numero);
            }    
        }
        return true;
    }
    
    public void DFS(Vertice a){
        a.Visitado=true;
        for(int i=0;i<a.lst.size();i++){
            Vertice b=a.lst.get(i);
            if(!b.Visitado){
                DFS(b);
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException
    {
        ArrayList<Integer> numeros=new ArrayList<Integer>();
        criaArray(numeros,"/home/geovane/Documentos/CC/ALPROII/teste5000b");
        DirectedGraphList g = new DirectedGraphList();
        HeapSort.heapsort(numeros);
        for(int j=0;j<numeros.size();j++){
        g.addVertice(Integer.toString(numeros.get(j),6));
        }
        for(int i=0;i<numeros.size();i++){
            String numer=Integer.toString(numeros.get(i), 6);
            possibilidades(g,numer,numeros);
        }
    }
}
4
  • 2
    Você precisa exibir a sequência em si, ou achar o tamanho dela é suficiente pra você? Eu posso pular, por exemplo, de 15 para 10015 (sob a teoria de que 00015 e 10015 diferem em exatamente um dígito)?
    – user25930
    Commented 4/06/2015 às 9:39
  • Certo, esqueci de mencionar que todos os números tem que ter o mesmo numero de digitos, vou editar. Ou seja, não pode pular de 15 para 10015. Além disso, eu preciso printar a sequência. Commented 4/06/2015 às 19:34
  • 2
    Olá Geovane, o problema do maior caminho é NP-Hard; a exceção são grafos acíclicos dirigidos; nesse caso é possível inverter os pesos (e.g, -1 por aresta) e usar um algoritmo de caminho mínimo. Commented 4/06/2015 às 20:01
  • Para fazer isso então eu teria que mudar a forma que faço minhas arestas, alguma sugestão? Commented 4/06/2015 às 20:06

2 Respostas 2

2

Já que a gente não pode misturar números de tamanhos diferentes, o primeiro passo é separar a entrada em conjuntos contendo números de mesmo comprimento: no caso {31}, {154}, {3342, 1021, 2022, 2235, 4014, 3501, 3502, 4332, 1554, 3001}; a resposta necessariamente tem que ser igual à resposta de algum desses subconjuntos; eu vou usar pra ilustrar o algoritmo, não o seu exemplo, mas o conjunto {101, 322, 325, 342, 345, 422, 501, 502, 522} (em base 6, naturalmente).

grafo de possíveis pares da sequência

Eu listei os números já em ordem crescente pra tornar a primeira pergunta bem fácil: qual é a maior sequência que atende as condições do problema começando no 522? Obviamente é a sequência {522}, já que a restrição da sequência ser crescente garante que a gente não tem pra onde ir depois do 522.

A minha segunda pergunta: qual é a maior sequência começando no 502? Obviamente a resposta é {502, 522}, já que do {502} só dá pra ir pro {522}. Analogamente, é fácil ver que a maior sequência começando no 501 é {501, 502, 522}, etc.

Se você for analisando os números do exemplo em ordem decrescente, você não precisa pensar muito — você sempre vai ter zero ou uma alternativas — até chegar no 322.

grafo parcial no nó 322

(Os nós cinzas são nós que a gente já considerou; o número entre parênteses é o tamanho do maior caminho que começa naquele nó. O nó em vermelho — 322 é o nó que a gente está considerando agora.)

Agora a gente tem quatro possibilidades de continuar a sequência: {322, 522, …}, {322, 422, …}, {322, 342, …}, {322, 325, …}. Qual delas é maior? Ora, a gente sabe que, com exceção da sequência que começa em 522 (que só pode ter um termo), as outras escolhas permitem continuar por mais dois números. Logo a maior sequência que começa em 322 tem 1 + 2 = 3 termos.

Depois disso, é fácil ver que a maior (e única) sequência que começa em 101 tem 4 termos, e portanto é a solução do problema (pois se você olhar pra todos os nós do grafo, a maior sequência que começa em algum deles é 4).


Resumindo, a ideia do algoritmo é essa daqui:

para cada número n, em ordem decrescente:
    maior_sequência[n] := 1;  // sempre posso fazer a sequência unitária {n}
    para cada número “vizinho” v seguindo as regras do problema:
        // posso fazer a sequência {n, v, …}
        maior_sequência[n] := máximo(maior_sequência[n], 1 + maior_sequência[v]);        

retorne máximo(maior_sequência);

Faz sentido? Essa ideia funciona porque achar a maior sequência que começa em um dado número depende apenas do número: não importa como eu cheguei em n até agora; o caminho até n nunca afeta o caminho que eu posso seguir depois de n. Só é possível fazer isso porque o gráfico é acíclico — eu nunca posso voltar devido à restrição dos números serem crescentes.

Se eu não tivesse essa restrição, uma resposta válida para esse exemplo seria e.g. {101, 501, 502, 522, 422, 322, 342, 345, 325}, que passa por todos os números, mas esse problema é muito mais difícil, já que aí eu teria que de alguma forma guardar os números que eu já visitei. Neste exemplo, se eu não fizesse isso, eu poderia ter a sequência infinita, {322, 342, 345, 325, 322, 342, 345, 325, 322, …}.

Essa ideia é um exemplo de uma ideia muito mais geral chamada programação dinâmica; o link da Wikipedia acho que confunde mais do que esclarece, mas eu não achei muito material em português. A wiki da Maratona de Programação na UFMG tem mais problemas e algumas referências em inglês se você quiser estudar ideias parecidas.

8
  • (ficou clara a ideia do algoritmo? eu escrevi tudo num stream of conciousness; se alguma coisa não tiver ficado clara eu posso editar)
    – user25930
    Commented 4/06/2015 às 20:20
  • Esse algoritmo que tu postou, seria para adicionar em cada vértice o numero que está em parentesis ali no desenho do grafo, ou seja, o tamanho da sequencia que vem a seguir? Commented 4/06/2015 às 21:10
  • 1
    Isso — a sua classe Vertice teria que ter um campo a mais armazenando um inteiro (o tamanho da sequência que se segue). Se o seu programa precisar produzir uma testemunha (um exemplo explícito de uma sequência válida), você também precisa ter um campo guardando uma referência pro próximo vértice da sequência (caso ocorra empate, qualquer vértice com o tamanho máximo serve; caso o vértice seja o último da sequência, você guarda null nesse campo); aí na saída você acha um vértice de início aceitável e vai avançando por esse campo pelo grafo.
    – user25930
    Commented 4/06/2015 às 21:13
  • Sim, eu preciso ter uma testemunha. Eu tentei implementar aqui o algoritmo que tu postou alí, mas os resultados não deram muito certo. Adicionei na classe vértice o atributo int. public void atribuiTamanhoSequencia(){ for(int i=vert.size()-1;i>=0;i--){ vert.get(i).maiorSequencia=1; for(int k=vert.get(i).lst.size();k>=0;k--){ vert.get(i).maiorSequencia=Math.max(vert.get(i).maiorSequencia, vert.get(k).maiorSequencia+1); } } } Commented 4/06/2015 às 21:27
  • Ah, desculpe, eu não sei ainda como botar código aqui nos comentários. Commented 4/06/2015 às 21:33
1

Só para atualizar e ajudar alguém que por um acaso queira o código resolvido.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class DirectedGraphList
{
private class Vertice
{
    private String item;
    private boolean Visitado;
    int maiorSequencia;
    Vertice proximo;
    private ArrayList<Vertice> lst = new ArrayList<Vertice>();

    public Vertice(String item) {
        this.item = item;
        Visitado=false;
        maiorSequencia=0;
        lst=new ArrayList<Vertice>();
        proximo=null;
    }
    public String getItem() {
        return this.item;
    }
    public void setItem(String item) {
        this.item = item;
    }
    public void addAdjacent(Vertice v) {
        if (!lst.contains(v))
            lst.add(v);
    }
    public ArrayList<Vertice> getAdjacents() {
        return lst;
    }
    public Vertice getAdjacent(int i) {
        Vertice res = null;
        if ((i >= 0) && (i < lst.size()))
            res = lst.get(i);
        return res;
    }
    public int getDegree(){
        return lst.size(); 
    }
}

private ArrayList<Vertice> vert;

public DirectedGraphList() {
    vert = new ArrayList<Vertice>();
}

private Vertice searchVerticeRef(String item)
{
    Vertice res = null;
    int i;

    for (i = 0; ((i < vert.size()) && !vert.get(i).getItem().equals(item)); i++);

    if (i < vert.size())
        res = vert.get(i);

    return res;
}

public void addVertice(String item)
{
    if (searchVerticeRef(item) == null) 
    {
        Vertice novo = new Vertice(item);
        vert.add(novo);
    }
}

public void addEdge(String strOrig, String strDest)
{
    Vertice vAux1 = searchVerticeRef(strOrig);
    Vertice vAux2 = searchVerticeRef(strDest);

    if (vAux1 == null)
        throw new IllegalArgumentException("Aresta origem invalida: " + strOrig);
    else if (vAux2 == null)
        throw new IllegalArgumentException("Aresta destino invalida: " + strDest);
    else
    {
        vAux1.addAdjacent(vAux2);
    }
}

public int getNumVertices() {
    return vert.size();
}

public int getDegree(String vertice)
{
    int i, j, c = 0;
    Vertice v = searchVerticeRef(vertice);
    if (v != null)
    {
        // grau de saida
        c += v.getDegree();

        // grau de entrada
        for (i = 0; i < vert.size(); i++)
        {
            if (!vert.get(i).getItem().equals(vertice))
            {
                for (j = 0; j < vert.get(i).getDegree(); j++)
                {
                    if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
                        c++;
                }                   
            }
        }
    }
    return c;
}

public ArrayList<String> getAllAdjacents(String vertice)
{
    ArrayList<String> res = null;
    Vertice v = searchVerticeRef(vertice);
    if (v != null)
    {
        res = new ArrayList<String>();
        for (int j = 0; j < v.getDegree(); j++)
            res.add(v.getAdjacent(j).getItem());
    }
    return res;
}

public ArrayList<String> getSources()
{
    ArrayList<String> res = new ArrayList<String>();
    boolean checked;
    String vertice;

    for (int k=0; k<vert.size(); k++)
    {
        vertice = vert.get(k).getItem();

        checked = false;
        for (int i=0; i<vert.size(); i++)
        {
            for (int j=0; j<vert.get(i).getDegree(); j++)
            {
                if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
                {
                    checked = true;
                    break;
                }
            }
        }

        if (!checked)
            res.add(vertice);
    }
    return res;
}

public ArrayList<String> getSinks()
{
    ArrayList<String> res = new ArrayList<String>();

    for (int i=0; i<vert.size(); i++)
    {
        if (vert.get(i).getAdjacents().isEmpty())
            res.add(vert.get(i).getItem());
    }
    return res;
}

public void showInfo()
{
    System.out.print("V = { ");
    for (int i = 0; i < vert.size()-1; i++)
        System.out.printf("%s, ", vert.get(i).getItem());
    System.out.printf("%s }\n", vert.get(vert.size()-1).getItem());

    ArrayList<String> arestas = new ArrayList<String>();
    for (int i = 0; i < vert.size(); i++)
        for (int j = 0; j < vert.get(i).lst.size(); j++)
            arestas.add(String.format("(%s, %s)", vert.get(i).getItem(), vert.get(i).getAdjacent(j).getItem()));

    System.out.print("E = {\n");
    if (!arestas.isEmpty()) {
        System.out.printf("      %s", arestas.get(0));

        for (int i = 1; i < arestas.size(); i++)
            System.out.printf(",\n      %s", arestas.get(i));
    }
    System.out.println("\n    }");
}
public static void criaArray(ArrayList<Integer> a,String nome) throws FileNotFoundException{
    try{
        FileReader ler= new FileReader(nome);
        BufferedReader arq=new BufferedReader(ler);
        int parsedStr;
        String str=arq.readLine();
        while(str!=null){
            parsedStr=Integer.parseInt(str);
            a.add(parsedStr);
            str=arq.readLine();
        }
    }
    catch(IOException e){
        System.out.println("Erro na abertura do arquivo: "+
                e.getMessage());
    }
}
public static int diferente(String a,String b){
    int diferentes=0;
    if(a.length()==b.length()){
        for(int i=0;i<a.length();i++){
            if(a.charAt(i)!=b.charAt(i))
                diferentes++;
        }
    }
    else 
        diferentes=2;
    return diferentes;
}
public static boolean maior(String str1,String str2){
    int aux=Integer.parseInt(str1, 6);
    int aux1=Integer.parseInt(str2, 6);
    if(aux>aux1)
        return true;
    else return false;
}

public static boolean possibilidades(DirectedGraphList graph,String a,ArrayList<Integer> array){
    int diferentes=0;
    for(int i=0;i<array.size();i++){
        String numero=Integer.toString(array.get(i),6);
        diferentes=diferente(numero,a);
        if(diferentes==1 && maior(numero,a)){
            graph.addEdge(a,numero);
        }   
    }
    return true;
}

public void printaSequencia(Vertice a){
    System.out.println(a.item);
    Vertice atual=a;
    while(atual.proximo!=null){
        atual=atual.proximo;
        System.out.println(atual.item);
    }
}

public void atribuiTamanhoSequencia(){
    for(int i=vert.size()-1;i>=0;i--){
        vert.get(i).maiorSequencia=1;
        for(int k=vert.get(i).lst.size()-1;k>=0;k--){
            if (vert.get(i).lst.get(k).maiorSequencia+1 > vert.get(i).maiorSequencia){
                vert.get(i).maiorSequencia=vert.get(i).lst.get(k).maiorSequencia+1;
                vert.get(i).proximo=vert.get(i).lst.get(k);
            }
        }
    }

}
public Vertice getVerticeInicial(){
    Vertice aux=null;
    int tamanho=0;
    for(int i=0;i<vert.size();i++){
        if(vert.get(i).maiorSequencia>tamanho){
            aux=vert.get(i);
            tamanho=vert.get(i).maiorSequencia;
        }
    }
    return aux;
}


public static void main(String[] args) throws FileNotFoundException
{
    ArrayList<Integer> numeros=new ArrayList<Integer>();
    criaArray(numeros,"/home/geovane/Documentos/CC/ALPROII/test100000a");
    DirectedGraphList g = new DirectedGraphList();
    HeapSort.heapsort(numeros);
    for(int j=0;j<numeros.size();j++){
    g.addVertice(Integer.toString(numeros.get(j),6));
    }
    for(int i=0;i<numeros.size();i++){
        String numer=Integer.toString(numeros.get(i), 6);
        possibilidades(g,numer,numeros);
    }
    g.atribuiTamanhoSequencia();
    Vertice inicial=g.getVerticeInicial();
    g.printaSequencia(inicial);
}
}

Problema resolvido!! Obrigado @ctgPi

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .