Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar o problema conhecido como "Longest integer subsequence" usando backtracking?

0 votos
60 visitas
perguntada Mai 11, 2016 em Ciência da Computação por danielcajueiro (5,776 pontos)  

Dada uma sequência de inteiros \(A\), nós queremos encontrar a subsequencia mais longa cujos elementos estão em ordem crescente.

Ou seja, buscamos a sequência mais longa dos índices \(1\le i_1 < \cdots < i_k \le n\) tal que \(A[i_j]\lt A[i_{j+1}]\) para todo \(j\).

Compartilhe

1 Resposta

0 votos
respondida Mai 11, 2016 por danielcajueiro (5,776 pontos)  

Abaixo eu apresento 3 soluções diferentes usando backtracking.

A primeira solução é baseada no pseudo-código na Lecture 3 do E-book Algorithms de Jeff Erickson. As outras soluções usam explicitamente a representação usando árvore binária usual para resolver problemas com essas características.

1) Calcula o tamanho da subsequência

import numpy as np


def longest_increasing_subsequence(sequence,previous):
    n=len(sequence)
    if(n==0):
        return 0
    else:
        theMax=longest_increasing_subsequence(sequence[1:],previous)
        if (sequence[0]>previous):
            aux=1+longest_increasing_subsequence(sequence[1:],sequence[0])
            if (aux>theMax):
                theMax=aux

        return theMax        


    if __name__ == '__main__':

        sequence=[3,81,1,5,1,4,6,1,1,79,7]
        previous=-np.Inf
        print longest_increasing_subsequence(sequence,previous)

2) Apresenta todas as subsequências

a) Usando uma fila

import numpy as np
import Queue

class Node:
    def __init__(self, level,after,possibleSolution):
        self.level = level # The level within the tree (depth)
        self.after=after
        self.possibleSolution = possibleSolution    # list of items our node contains
        #print "level",level,"after",after,"possibleSolution",possibleSolution

def solution_exists(solution,possibleSolution):
    n=len(solution)
    m=len(solution[0])        
    solutionExists=False
    i=0
    while(i<n and (not solutionExists)):
        count=0
        for j in range(m):
            if(solution[i][j]==possibleSolution[j]):
                count=count+1
        if(count==m):
            solutionExists=True
        i=i+1
    return solutionExists    

def longest_increasing_subsequence(sequence):
    solution=[]
    n=len(sequence)
    queue = Queue.Queue()
    root = Node(-1,np.Inf,[]) # level,previous,possibleSolution
    queue.put(root)            
    while not queue.empty():
        u=queue.get()  
        if(u.level<n-1):
            # With the extra element
            vLevel=u.level+1
            if(sequence[n-vLevel-1]<u.after):
                v=Node(vLevel,sequence[n-vLevel-1],[sequence[n-vLevel-1]]+u.possibleSolution) 
                queue.put(v)                       
            if((len(solution)==0) or (len(v.possibleSolution)>len(solution[0]))): # Short Circuit
                solution=[v.possibleSolution]
            else:
                if(len(v.possibleSolution)==len(solution[0])):
                    if(not solution_exists(solution,v.possibleSolution)):
                        solution.append(v.possibleSolution)
            # Without the extra element
            v=Node(vLevel,u.after,u.possibleSolution[:])
            queue.put(v)
    return solution

if __name__ == '__main__':

    sequence=[3,81,1,5,1,4,6,1,1,79,7,90]
    print longest_increasing_subsequence(sequence)

b) Usando uma pilha

import numpy as np

class Node:
    def __init__(self, level,after,possibleSolution):
        self.level = level # The level within the tree (depth)
        self.after=after
        self.possibleSolution = possibleSolution    # list of items our node contains
        #print "level",level,"after",after,"possibleSolution",possibleSolution
    def printNode(self):
        print(self.possibleSolution,self.level, ' ,',end=' ')



def solution_exists(solution,possibleSolution):
    n=len(solution)
    m=len(solution[0])        
    solutionExists=False
    i=0
    while(i<n and (not solutionExists)):
        count=0
        for j in range(m):
            if(solution[i][j]==possibleSolution[j]):
                count=count+1
        if(count==m):
            solutionExists=True
        i=i+1
    return solutionExists    

def longest_increasing_subsequence(sequence):
    solution=[]
    n=len(sequence)
    root = Node(-1,np.Inf,[]) # level,previous,possibleSolution
    stack=[root]            
    iteration=0
    while len(stack)!=0:
        iteration=iteration+1
        print('\n',iteration)
        for i in range(len(stack)):
            stack[i].printNode()         
        u=stack.pop()
        if(u.level<n-1):
            # With the extra element
            vLevel=u.level+1
            # Without the extra element
            v=Node(vLevel,u.after,u.possibleSolution[:])
            stack.append(v)
            if(sequence[n-vLevel-1]<u.after):
                v=Node(vLevel,sequence[n-vLevel-1],[sequence[n-vLevel-1]]+u.possibleSolution) 
                stack.append(v)                      
            if((len(solution)==0) or (len(v.possibleSolution)>len(solution[0]))): # Short Circuit
                solution=[v.possibleSolution]
                print('\n','new solution',solution)
            else:
                if(len(v.possibleSolution)==len(solution[0])):
                    if(not solution_exists(solution,v.possibleSolution)):
                        solution.append(v.possibleSolution)
                        print('\n','extra solution',solution)
    return solution

if __name__ == '__main__':

    sequence=[3,81,1,5,1,4,6,1,1,79,7,90]

    print ('\n','Solution',longest_increasing_subsequence(sequence))
...