Exercícios MT2

Melhor valor: $17$, selecionando os objetos 2 e 3. A gulosa por $v/w$ devolve $5$.

Com $\mathrm{val}[i,j]$ o melhor valor considerando objetos até $i$ e capacidade $j$, a recorrência compara ignorar o objeto $i$ com incluí-lo. A tabela (linhas objeto 1, 2, 3; colunas capacidade 0 a 5) é: objeto 1: $0,5,5,5,5,5$; objeto 2: $0,5,8,13,13,13$; objeto 3: $0,5,8,13,14,17$. Logo $\mathrm{val}[3,5]=17$. A gulosa escolhe o objeto 1 (razão 5) e fica sem capacidade para mais nada, obtendo 5. Em geral pode ser arbitrariamente má: com $W=B$, $v=\{1,B-1\}$ e $w=\{1,B\}$, a gulosa escolhe o primeiro objeto e o rácio gulosa/ótima é $1/(B-1)$, que tende para 0 quando $B$ cresce.

Ótimo de programação dinâmica: $10$ (objetos 2 e 3, ou 1 e 4). Gulosa: $9$.

A tabela (capacidades 0 a 10) dá: objeto 1: $0,0,0,0,4,4,4,4,4,4,4$; objeto 2: $0,0,0,0,4,5,5,5,5,9,9$; objeto 3: $0,0,0,0,4,5,5,5,5,9,10$; objeto 4: $0,0,0,0,4,5,6,6,6,6,10$. Todas as razões $v/w$ valem 1, logo a gulosa escolhe os dois primeiros objetos e obtém $4+5=9$, abaixo do ótimo 10.

«baab» pertence a $L(G)$, pois a célula $S_{1,4}$ contém $S$.

Células de comprimento 1: $S_{1,1}=\{B\}$, $S_{2,1}=\{A\}$, $S_{3,1}=\{A\}$, $S_{4,1}=\{B\}$. Comprimento 2: $S_{1,2}=\{A\}$ (por $A\to BA$), $S_{3,2}=\{S,B\}$ (por $S\to AB$ e $B\to AB$). Comprimento 3: $S_{2,3}=\{S,B\}$ (por $S\to AB$ e $B\to AB$ com $S_{2,1}=\{A\}$, $S_{3,2}=\{S,B\}$). Comprimento 4: $S_{1,4}$ usa a divisão $k=2$: $S_{1,2}=\{A\}$ e $S_{3,2}=\{S,B\}$, donde $S\to AB$ e $B\to AB$, obtendo $S_{1,4}=\{S,B\}$. Como $S\in S_{1,4}$, a cadeia pertence à linguagem. Uma derivação completa é $S\Rightarrow AB\Rightarrow BAB\Rightarrow bAB\Rightarrow baB\Rightarrow baAB\Rightarrow baaB\Rightarrow baab$. O método preenche uma tabela triangular de $O(n^2)$ células, cada uma com $O(n)$ divisões, pelo que o tempo é $O(n^3)$ para gramática fixa e o espaço é $O(n^2)$.

Não se poda o nó de soma 15. Na subárvore ficam 22 estados por explorar (9 visitados de 31). Solução: $x=(1,1,0,0,0,1)$, com soma $5+10+18=33$.

Como a soma parcial 15 ainda não ultrapassa $M=33$, o nó não pode ser podado. Já o nó $(1,1,1)$ tem soma 27 e o próximo elemento vale pelo menos 13, logo $27+13=40>33$: é podado. O nó $(1,1,0,1)$ tem soma 28 e o próximo elemento vale 15, logo $28+15=43>33$: também é podado. Restam os nós $(1,1,0,0)$ (soma 15), $(1,1,0,0,1)$ (soma 30, podado pois $30+18>33$), $(1,1,0,0,0)$ e as duas folhas, num total de 9 nós visitados entre os 31 nós da subárvore (15 internos e 16 folhas). A única solução encontrada é $x=(1,1,0,0,0,1)$.

Redução: $w(u,v)=1$ se $(u,v)\in E$ e $w(u,v)=\rho N+1$ caso contrário, com $\rho>1$.

Dado um grafo conexo $G$ com $N$ nós, constrói-se $G'$ completo com pesos 1 nas arestas existentes e $\rho N+1$ nas que não existem. Se $G$ tem ciclo hamiltoniano, esse ciclo tem custo $N$ em $G'$. Se não tem, qualquer circuito em $G'$ usa pelo menos uma aresta de peso $\rho N+1$, tendo custo superior a $\rho N+1>N$. A construção cria no máximo $N^2$ arestas, logo é polinomial. Se existisse um algoritmo de aproximação de razão polinomial $p(n)$, ele devolveria um circuito de custo $\le p(n)\cdot N$ quando existe ciclo hamiltoniano, que para $\rho>p(n)$ é menor que $\rho N+1$; assim, distinguir os dois casos decidiria o ciclo hamiltoniano em tempo polinomial.

Cobertura devolvida: 2 vértices (fator 2 sobre o ótimo 1). Iterações: $n-1$.

Numa estrela com $n$ nós há $n-1$ arestas, todas incidentes no nó central. O algoritmo escolhe uma aresta de cada vez; como as arestas escolhidas não partilham extremidades além do centro, em cada iteração apenas uma aresta nova é eliminada, pelo que são precisos $n-1$ passos. O conjunto dos dois extremos de uma última aresta forma uma cobertura de 2 vértices, enquanto o nó central, sozinho, cobre todas as arestas: o rácio é 2, o pior caso do algoritmo.

Gulosa: $\{s_1,\dots,s_6\}$ (6 conjuntos). Ótimo: $\{s_7,s_8\}$ (2 conjuntos). Rácio 3.

Como há sempre empate no número de pontos por cobrir, o desempate pelo menor identificador faz a gulosa escolher $s_1$, depois $s_2$, e assim sucessivamente até $s_6$, num total de 6 conjuntos. Os conjuntos $s_7$ e $s_8$ cobrem sozinhos os 32 pontos, pelo que a cobertura ótima tem 2 conjuntos. O rácio $6/2=3$ mostra que a heurística gulosa pode afastar-se do ótimo neste problema.

Custo do algoritmo: 18; ótimo: 12. Sem garantia de razão fixa, por falta da inequação triangular.

O algoritmo da 2-aproximação para o TSP métrico garante fator 2 porque os pesos respeitam a inequação triangular, permitindo atalhar arestas repetidas. Neste problema, o tempo de uma tarefa depende da tarefa seguinte, pelo que arestas com a mesma origem podem ter pesos diferentes consoante o destino e a inequação triangular pode falhar. Sem essa condição, o custo 18 do algoritmo não fica limitado por qualquer fator do ótimo 12.

Redução: $G$ tem clique de tamanho $k$ se e só se $\bar G$ tem cobertura de $|V|-k$ vértices.

Para mostrar que Vertex-Cover está em NP, dado um subconjunto $V'$ de vértices, basta verificar para cada aresta $(u,v)$ se $u\in V'$ ou $v\in V'$, o que demora $O(V+E)$. Para a redução, dado $G=(V,E)$, constrói-se o complementar $\bar G$ com os mesmos vértices e arestas onde não havia. Um conjunto $C$ é clique em $G$ se e só se $V\setminus C$ é cobertura de vértices em $\bar G$: toda a aresta de $\bar G$ tem pelo menos uma extremidade fora de $C$, ou seja, não liga dois vértices de $C$. Assim, $G$ tem clique de tamanho $k$ se e só se $\bar G$ tem cobertura de tamanho $|V|-k$. O complementar tem no máximo $|V|^2$ arestas, logo a transformação é polinomial.

$G'$ = complementar de $G$, com $k'=k$: $G$ tem clique de tamanho $k$ se e só se $G'$ tem conjunto independente de tamanho $k$.

Se $C$ é clique em $G$, todas as arestas entre os nós de $C$ existem em $G$ e, portanto, nenhuma existe em $G'$, logo $C$ é independente em $G'$. Reciprocamente, se $C$ é independente em $G'$, não há arestas de $G'$ entre os nós de $C$, ou seja, todas as pares de nós de $C$ estão ligados em $G$, logo $C$ é clique. A construção do complementar é polinomial, pelo que a redução é válida.

Redução: $z_i\in\{0,1\}$ e, por cada cláusula, a restrição soma dos literais (com $1-z_i$ para literais negados) é pelo menos 1.

Para a versão de decisão do ILP, basta «adivinhar» o vetor inteiro $\vec x$, avaliar a função objetivo e verificar as restrições, o que é polinomial; logo ILP está em NP. Dada uma fórmula 3-CNF-SAT com variáveis $x_1,\dots,x_n$, definem-se variáveis inteiras $z_1,\dots,z_n$ com $0\le z_i\le 1$, onde $z_i=1$ representa $x_i=$ verdadeiro. Cada cláusula como $(x_1\lor\lnot x_2\lor x_3)$ transforma-se na restrição $z_1+(1-z_2)+z_3\ge 1$: para a satisfazer, pelo menos um dos termos tem de ser positivo, o que corresponde a tornar verdadeiro pelo menos um dos literais da cláusula. A fórmula é satisfazível se e só se o ILP resultante tem solução inteira, e a construção tem um número polinomial de variáveis e restrições.

Ótimo do PL e do ILP: $(x_1,x_2)=(0,0)$, valor $0$.

Introduzindo as variáveis de folga, obtém-se $x_3=4-x_1-x_2$ e $x_4=2-2x_1+x_2$. Como ambos os coeficientes da função objetivo são negativos, o máximo ocorre na origem: $(0,0)$, com valor 0, que é também inteiro, pelo que é a solução ótima do ILP. A região é um polígono fechado (interseção de duas semiplanos com o primeiro quadrante), logo o problema é exequível e limitado.

PL: $(x,y)=(2{,}5,2{,}5)$, valor 5 em $\max\;2y$. ILP: $(2,2)$ ou $(3,2)$, valor 4.

Passando a minimização de $-2y$ para maximização de $2y$ e multiplicando as restrições por $-1$, obtém-se $-x+y\le 0$ e $x+y\le 5$. A região exequível é o triângulo com vértices $(0,0)$, $(5,0)$ e $(2{,}5,2{,}5)$; como se maximiza $2y$, o ótimo é $(2{,}5,2{,}5)$ com valor 5. No ILP, $y$ inteiro fica limitado por $y\le 2$ (pois $x\ge y$ e $x+y\le 5$), pelo que o ótimo é $(2,2)$ ou $(3,2)$ com valor 4. Arredondar $(2{,}5,2{,}5)$ daria $(3,3)$, que viola $x+y\le 5$, logo não é exequível.

Ótimo: 30 questões de escolha múltipla e 3 dissertativas, num total de 210 pontos.

As restrições são $2x+10y\le 90$ (tempo), $x\ge 10$, $x\le 50$, $y\ge 3$, $y\le 10$. Os vértices da região exequível com interesse são $(10,3)$, $(10,7)$ e $(30,3)$ (o vértice $(30,3)$ vem de $2x+10y=90$ com $y=3$). Os valores da função objetivo são 60, 190 e 210, respetivamente. O máximo é 210, com 30 questões de escolha múltipla e 3 dissertativas.

n7: podado por incumbent 28 > 26. n6: z ≤ 29, logo não pode ser 30. BFS: n1, n2, n11.

(1) Ao chegar a $n_7$ já existe uma solução inteira com valor 28 (em $n_4$) e, como se maximiza, todos os nós abaixo de $n_7$ têm valor $\le 26$; a exploração abaixo de $n_7$ é abandonada. (2) O nó $n_6$ está abaixo de $n_5$, onde a relaxação linear vale 29, pelo que qualquer solução inteira abaixo de $n_5$ vale no máximo 29; 30 é impossível. (3) Em BFS exploram-se primeiro $n_1$, depois os filhos $n_2$ e $n_{11}$. Como $n_{11}$ é inteiro com 38 e $n_2$ só vale 31, todos os nós abaixo de $n_2$ ficam com valor $\le 31<38$ e podem ser podados de imediato.

Distâncias de $a$: $b=2$, $c=1$, $d=2$. Com $d\to a=-3$, há ciclo negativo e o algoritmo falha.

Como existe uma aresta de peso negativo, Dijkstra não é adequado; Bellman-Ford trata pesos negativos. No algoritmo de Johnson, adiciona-se um nó $s$ com arestas de peso 0 para todos os nós e corre-se Bellman-Ford, obtendo $h(a)=h(b)=h(d)=0$ e $h(c)=-1$. Reponderam-se as arestas com $w'(u,v)=w(u,v)+h(u)-h(v)$: $a\to b$ fica 2, $b\to c$ fica 0, $c\to d$ fica 0, $d\to a$ fica 3, $a\to c$ fica 5 e $b\to d$ fica 2, todos não negativos. Dijkstra a partir de $a$ dá distâncias reponderadas 0, 2, 2, 2; voltando aos pesos originais com $d(u,v)+h(v)-h(u)$, obtém-se $d(a,b)=2$, $d(a,c)=1$, $d(a,d)=2$. Se $d\to a=-3$, o ciclo $a\to b\to c\to d\to a$ tem peso $2-1+1-3=-1<0$, pelo que não existem caminhos mais curtos bem definidos e Johnson não se aplica.

No grafo original, $d(A,B)=0$ e o algoritmo acerta. Exemplo de falha: $A\to B=1$, $A\to C=2$, $C\to B=-2$ (ótimo 0, Dijkstra devolve 1). Complexidade $O((V+E)\log V)$.

No grafo original, depois de processar $A$, o min-heap contém $B$ com 2 e $C$ com 1; sai $C$ primeiro e relaxa $B$ para $1+(-1)=0$, que é a distância correta. O algoritmo falha quando um nó é retirado definitivamente do heap antes de todas as arestas negativas que lhe chegam serem consideradas: com $A\to B=1$, $A\to C=2$ e $C\to B=-2$, o nó $B$ sai com distância 1 e é finalizado, embora o caminho $A\to C\to B$ tenha custo 0. Em geral, o Dijkstra assenta na monotonicidade dos pesos (todo o prefixo de um caminho mais curto é ele próprio mais curto), que deixa de valer com arestas negativas. Com min-heap, cada nó entra e sai no máximo uma vez e cada aresta pode provocar uma atualização, donde $O((V+E)\log V)$.