quarta-feira, dezembro 14, 2005

Algoritmos e Heurística

Um algoritmo é um conjunto definido de instruções computacionais sequenciais, utilizado para obter um determinado resultado a partir de dados fornecidos. As heurísticas também são algoritmos, mas que se aplicam a problemas demasiado complexos para serem resolvidos explicitamente— aqueles para os quais não há um "caminho" computacional para encontrar "a solução". As heurísticas são portanto directivas ou "regras por alto" de como resolver um problema. Utilizam-se heurísticas para resolver problemas em que o meio é demasiado complexo mas também quando é dinâmico, enquadrando-se nesta última categoria aqueles em que o sistema está sujeito a interacção com o meio exterior.

Na vida real, um algoritmo "simples" pode ser uma linha de montagem de um qualquer processo industrial; ou uma receita de culinária onde é suposto não haver imprevistos; ou o processo de ir de um sítio ao outro de comboio. Uma heurística pode ser o projecto de arquitectura de uma fábrica, a resolução de problemas de uma receita de culinária que deu para o torto; ou ir de um sítio para ou outro conduzindo um carro através do trânsito automóvel. Nestes últimos exemplos, há uma componente de "decisão" que escapa à especificação procedimental.

Em meios matemáticos ou computacionais, utilizam-se algoritmos (do primeiro tipo) por exemplo no cálculo estrutural de um edifício. As heurísticas utilizam-se por exemplo na elaboração um programa que "saiba" jogar o jogo do galo, ou damas, xadrês ou Go.

Na implementação computacional de heurísticas, e tomamos o exemplo de um jogo de xadrês, não basta que o jogo saiba mexer as peças e como são capturadas, que saiba que o objectivo é "ganhar" e que ganha o primeiro jogador que faça um cheque ao Rei sem resposta possível. Nem há avaliações qualitativas como as que o cérebro humano realiza. É preciso que o jogo tenha um algoritmo (uma "função posicional"), que a partir de uma dada configuração de peças no tabuleiro, e de um conjunto de ponderações internas, devolva valores numéricos que sirvam para alimentar o sistema de decisão.

Para um determinado tabuleiro, o programa determina quais são as suas jogadas "legais". Para cada uma avalia o "valor" correspondente. E depois repete o processo para possíveis contra-jogadas do adversário; e depois repete o processo até à "profundidade" possível ou desejada. No fundo, está a "ver várias jogadas à frente", avaliando cada uma de acordo com a sua escala de valoração. No fim, tem uma árvore de alternativas, cada uma com uma avaliação numérica, e considerando que o jogador adversário vai tentar maximizar as suas possibilidades de ganhar [aqui entra uma ramificação interessante da Teoria dos Jogos], escolhe uma jogada. Eventualmente este processo conduzirá a uma vitória da máquina sobre o adversário.

Na programação de uma heurística do género, o mais difícil não é mover peças, ou determinar as jogadas legais, ou mesmo montar o sistema de construção da "árvore" de jogadas, ou problemas técnicos muito complexos como tornar mais eficiente o imenso volume de cálculo envolvido— mas sim a construção da função de valor, e a calibração dos respectivos parâmetros.

9 comentários:

  1. Caro amigo,isto faz-me lembrar inteligencia artificial que tive na faculdade....;)

    ResponderEliminar
  2. Caro Pantera,

    Então vou ter que me desculpar por este primer tão pouco técnico!

    ...mas quero fazer passar algumas noções básicas aos leitores, com o único intuito de chegar à conclusão que pelas heurísticas mal aplicadas, principalmente por parte do Estado, obtêm-se soluções artificiais regidas por uma grande falta de inteligência...

    (uma forma alternativa do problema do cálculo económico...)

    ResponderEliminar
  3. Do National Institute of Standards and Technology:

    - Algorythm: A computable set of steps to achieve a desired result.

    - Heuristic: (algorithmic technique) An algorithm that usually, but not always, works or that gives nearly the right answer.

    ResponderEliminar
  4. Da Wikipédia:

    In mathematics and computer science an algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state. Algorithms can be implemented by computer programs (...) The concept of an algorithm is often illustrated by the example of a recipe.

    In computer science, a heuristic is a technique designed to solve a problem that ignores whether the solution can be proven to be correct, but which usually produces a good solution or solves a simpler problem that contains or intersects with the solution of the more complex problem. (...) Heuristics are intended to gain computational performance or conceptual simplicity potentially at the cost of accuracy or precision.

    ResponderEliminar
  5. Escusava de ter posto a wikipédia, que explicou muito bem. Embora, acredito que seja util ter uma linguagem mais acessivel, principalmente se tiver pretençoes politicas

    De resto, adorei o seu comentário aqui, sobre a Heuristica mal aplicada . Espetacular
    Não estava a ver qual o seu objectivo do seu artigo, e acho que o comentário só o torna mais util

    Quando tiver tempo, irei falar dele no meu blog
    (sou mesmo daqueles que não tem tempo, se vir o meu blog . Já agora, era bom a JC passar a dedicar mais tempo (estou disponivel mais os pais da 26-4 ) para tão horrivel assunto

    Isto, num dia em que mais uma criança (como era de prever ) foi noticia.

    Quando parará o feminismo de esquerda, que tanta vitimas tem feito, NOS NOSSOS TRIBUNAIS ANTI-PAIS E CRIANÇAS ?


    PQ,

    ResponderEliminar
  6. hummmm, desconfio que nem sabem do que estou a falar

    E como não sabem , de certeza, essa é a parte tenebrosa do assunto

    ResponderEliminar
  7. Obrigado, este post ainda vai ter continuação...

    ResponderEliminar
  8. Ah, já percebi. O algoritmo equivale mais ou menos à Razão e a heurística equivale à Fé ...

    ResponderEliminar
  9. Um pouco... a heurística é a "arte de decidir". O problema é quando a arte precisa de se socorrer de números, e se esquece que os números não cobrem tudo. Aí entramos pelo campo dos tecnicismos e tecnocracias, porque as vidas das pessoas não se regulam por equações...

    ResponderEliminar