Escolha gananciosa e matróides (greedoids)

7

Enquanto eu examinava o material sobre a abordagem gananciosa, soube que um conhecimento sobre matróides (greedoids) me ajudaria a abordar o problema adequadamente. Depois de ler sobre os matróides, entendi o que são os matróides. Mas como você usa o conceito de um matróide para resolver um determinado problema de otimização?

Veja, por exemplo, o problema de seleção de atividades . Quais são as etapas para usar a teoria matróide para resolver o problema?

Impostor
fonte
11
Dê uma olhada no Cormen et al. livro . Há um capítulo sobre algoritmos e matroids gananciosos.
Juho
Não sei ao certo como ler sua pergunta a esse respeito, mas observe que os matróides e os greedoides não são os mesmos.
Raphael

Respostas:

6

A conexão é que, se você puder representar a estrutura subjacente ao seu problema de otimização como matróide, poderá usar o algoritmo ganancioso canônico para otimizar a soma de qualquer função de peso positivo. Se seu objetivo de otimização se encaixa nesse paradigma, você pode resolver seu problema com a abordagem gananciosa.

Exemplo

Considere o problema mínimo da árvore de extensão com pesos de borda positivos¹. Mostraremos que existe um matróide correspondente a esse problema, o que implica que ele pode ser resolvido com avidez, isto é, pelo algoritmo canônico ganancioso no referido matroide.

Seja um gráfico não direcionado com a função de custo de borda. Então, comG=(V,E,c)c:ER+(E,I)

I={FE(V|F,F) is a forest} ²

é um matróide. Assim, podemos encontrar o elemento de maximizando a soma dos pesos das arestas . É uma árvore de abrangência mínima. Observe que o algoritmo ganancioso canônico é chamado algoritmo de Kruskal neste contexto por razões históricas.Ic(e)=(maxeEc(e))c(e)

Provas

  1. Para mostrar: é um matróide. Temos que verificar três propriedades :(E,I)

    • I - o gráfico vazio é uma floresta.
    • Se , todo subconjunto de estiver em - dada uma floresta arbitrária, a remoção de arestas não pode introduzir ciclos. Portanto, todo subgráfico de uma floresta é uma floresta.FIFI
    • Para cada ,implica que existe para que - considere uma floresta arbitrária e uma menor . Suponha que não exista tal . Isso significa que todas as arestas em estão em cortes induzidos por arestas em ³. Como existem apenasesses cortes, pelo menos um par de arestas em compartilham um corte ; isso contradiz que é uma floresta.F1,F2I|F1|>|F2|eF1F2F2{e}IF1F2eF1F2|F2|F1 F1
  2. Para mostrar: qualquer elemento com peso máximo em é uma árvore de cobertura mínima de . Primeiro de tudo, é claro que tem peso máximo de acordo com ; portanto, por definição de , também tem peso mínimo de acordo com . Agora, tudo o que temos a mostrar é que é uma árvore de abrangência: se não fosse, não seria o máximo no sentido de que ainda poderíamos adicionar arestas (com peso positivo), contradizendo o peso máximo.FIGFccc


  1. Podemos lidar com pesos de borda negativos adicionando o peso mínimo mais um a todos os pesos.
  2. Uma floresta é uma união disjunta de árvores.
  3. Um gráfico contém um ciclo se e somente se houver um corte com mais de uma aresta.
Rafael
fonte