Todo algoritmo ganancioso tem estrutura matróide?

Está bem estabelecido que, para cada matróide $M$ e qualquer função de ponderação $w$ , não sai um algoritmo $\mbox{GreedyBasis}(M,w)$ que devolve uma base de peso máximo de $M$ . Então, a direção inversa também é verdadeira? Ou seja, se existe algum algoritmo ganancioso, também deve haver alguma estrutura matróide.

O algoritmo ganancioso não é um conceito formalmente definido. Existem vários modelos tentando capturar essa noção intuitiva, mas não há consenso sobre o que é um algoritmo ganancioso. A menos que você especifique uma definição formal do que você entende por algoritmo ganancioso, a pergunta não pode ser respondida como sim ou não.

Existe uma generalização de matróides chamada greedoid, que é inspirada em algoritmos gananciosos que você pode querer ver.

Na verdade, a descrição geral e completa de um problema que pode ser resolvido por um algoritmo ganancioso é uma incorporação matróide , que generaliza tanto o conceito de um matróide quanto o de um greedoide . A resposta é não - um problema solucionável por um algoritmo ganancioso não precisa ter uma estrutura matróide, mas terá a estrutura de uma incorporação matróide (que é, infelizmente, muito mais complicada).

Um modelo mental para isso pode ser o número mínimo de árvores abrangidas. A estrutura usada pelo algoritmo de Kruskal é matróide, mas a estrutura usada pelo algoritmo de Prim (que requer um nó inicial) não é. (É, no entanto, um greedoide - e uma incorporação matróide.)

$(S,\mathcal{C})$$S$$\mathcal{C}$$S$ $f:2^S\rightarrow\mathbb{R}$$S$

O algoritmo ganancioso, definido em termos desse formalismo, é bastante simples: você começa com o conjunto vazio e adiciona sucessivamente um único elemento até chegar a uma base, sempre garantindo que (i) seu conjunto seja viável a cada etapa e ( ii) o elemento que você adiciona maximiza a função objetivo do resultado resultante, wrt. todos os elementos alternativos que você poderia ter adicionado. (Ou seja, conceitualmente, você tenta adicionar todas as alternativas possíveis e escolhe a que produz o maior valor objetivo.)

Talvez você possa argumentar que pode haver outras formas de algoritmo ganancioso, mas existem vários livros sobre algoritmos e otimização combinatória que descrevem esse algoritmo baseado em sistema de conjunto como o algoritmo ganancioso. Isso não impede que você descreva algo que não se encaixa, mas ainda pode ser chamado de ganancioso, suponho. (Ainda assim, isso faz cover qualquer coisa que poderia potencialmente ter uma estrutura matróides, por exemplo, embora seja muito mais geral.)

O que Helman et al. o que eles descrevem quando esse algoritmo funcionará. Mais especificamente:

1. Eles mostram que, para funções objetivas lineares (onde o valor objetivo é a soma dos pesos dos elementos), o algoritmo ganancioso funcionará exatamente na estrutura que eles definem como uma incorporação matróide;

2. Eles fornecem uma caracterização semelhante para os objetivos de gargalo (onde o valor objetivo de um conjunto é igual ao mínimo sobre os pesos dos elementos individuais); e

3. Eles fornecem uma caracterização exata de quais funções objetivas (além das lineares) são otimizadas pelo algoritmo ganancioso em aplicações matróides.

Considere os seguintes problemas: EURO DE CORRENTE DE MOEDAS: Com uma quantidade infinita de notas de 1,2,5,10 euros, pague X euros usando o mínimo de notas possível. Isso pode ser resolvido usando o algoritmo ganancioso, que leva a maior nota possível. Mas não há estrutura matróide nesse problema.

COBERTURA DO FURO: Existem furos nas posições x_1, x_2, ..., x_n. Você tem um pedaço de comprimento 10 cm. Corrija os orifícios usando o menor número possível de patches. Novamente, isso pode ser resolvido de maneira gananciosa (basta colocar o patch o mais correto possível), mas não há estrutura matróide.