Problemas de otimização combinatória aparecem na indústria em áreas tão diversas como logística, telecomunicações, planejamento e escalonamento de tarefas. Devido a sua complexidade intrínseca e a seu porte, muitos destes problemas não podem ser resolvidos em forma exata com a tecnologia disponível hoje em um tempo razoável. Em várias aplicações reais a instância do problema que debe ser resolvida não é conhecida deterministicamente a priori e apenas dados probabilísticos são conhecidos. Otimização a priori tenta otimizar a média do custo das soluções a posteriori usando as probabilidades que são conhecidas. Neste projeto de pesquisa procura-se desenvolver e analisar heurísticas para obter boas soluções viáveis para o problema da árvore geradora mínima probabilística.