Oi Vitor,
Desculpe pela demora.
Legal você ter perguntado!
Após um tempo procurando por bugs, descobri que a implementação usada como gabarito provavelmente calcula a energia de um corte usando double.
Você tem razão. O enunciado e os teste sugerem que o caminho mínimo é calculado em double.
% more 6x5.printseams.txt
6x5.png (6-by-5 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 3 4 3 2 2 }
240.18 225.59 302.27 159.43* 181.81 192.99
124.18 237.35 151.02 234.09 107.89* 159.67
111.10 138.69 228.10 133.07* 211.51 143.75
130.67 153.88 174.01* 284.01 194.50 213.53
179.82 175.49 70.06* 270.80 201.53 191.20
Total energy = 644.467988
Horizontal seam: { 2 2 1 2 1 2 }
240.18 225.59 302.27 159.43 181.81 192.99
124.18 237.35 151.02* 234.09 107.89* 159.67
111.10* 138.69* 228.10 133.07* 211.51 143.75*
130.67 153.88 174.01 284.01 194.50 213.53
179.82 175.49 70.06 270.80 201.53 191.20
Total energy = 785.531820
o código gabarito usa uma minpq que compara tipos double?
Isso é interessante.
O checklist sugere que o algoritmo utilizado seja Dijkstra com MinPQ: execute with a MinPQ, as Dijkstra's algorithm.
Assim, a prioridade dos nós do digrafo (= pixels da imagem) na MinPQ devem a soma das energia no caminho até o nó/pixel. Essa soma é double.
o mais adequado não seria usar int, pois não só não haveria tanto cancelamento numérico, como não seria necessário calcular (custosas) raízes quadradas?
Hmm. Pode ser.
No cálculo da energia de cada pixel há uma raiz quadrada.
Suponho que dependendo do problema seja conveniente abrir mão da qualidade da imagem dada por esta modelagem com energia double em troca do tempo de processamento.
Mudando de assunto...
Eu não havia lido checklist da edição Spring 2018.
A implementação que tenho calcula os caminhos com double e não usa MinPQ e não é uma implementação de Dijkstra.
Também não utiliza uma representação explicita do digrafo como sugere o checklist: Don't use an explicit EdgeWeightedDigraph.
Como o digrafo subjacente formado pelos pixels é acíclico, podemos examinar os vértices em ordem topológica.
No caso do Seam Carving, há várias ordenações topológicas evidentes.
Isso está no checklist do ano passado:
Identifying the shortest energy path in a picture looks a lot like the COS 126 dynamic programming assignment about genetic sequencing. Can I use that approach? You are welcome to use a dynamic programming approach; however, in this case, it is equivalent to the topological sort algorithm for finding shortest paths in DAGs.
