segunda-feira, 23 de fevereiro de 2015

[Python] - Pancake problem (problema das panquecas)


Eu gosto de panquecas e você?

O problema da ordenação das panquecas tem como objetivo organizar uma pilha de panquecas de tamanhos variados. O objetivo é fazer com que a panqueca menor fique no topo da pilha, a segunda fique logo abaixo dela e assim por diante.

A ordenação das panquecas é feita através de uma sequência de giros (flips). Um giro consiste em inserir a espátula entre duas panquecas em uma pilha  e girar todas as panquecas que estão em cima da espátula.

Cada vértice (estado) do nosso problema é uma pilha de panquecas, essa pilha nada mais é que uma lista de inteiros com os tamanhos das panquecas. Nosso objetivo é deixar ordenada como uma pirâmide.

(clique na imagem para vê-la em tamanho maior)

O estados que estão dentro da área pontilhada são os vértices da borda, ou seja, aqueles vértices que estão prestes a serem expandidos.

Bem, temos também o custo acumulado de cada estado que é a soma da aresta com o custo do estado antecessor. O custo da aresta é o número de panquecas viradas.

Fácil não é mesmo? O código foi feito em Python e está todo comentado (comentários em inglês), é só ler com atenção que você irá entender facilmente a implementação.

Mas antes de ver o código, veja só essa animação do problema das panquecas:


Mais um vídeo que servirá de referência para você entender melhor:


Agora ficou fácil não é mesmo? Lembrando que faço uso de uma fila de prioridades (priority queue) cuja prioridade é pelo menor custo acumulado. Essa fila de prioridades armazena os vértices (estados) da borda do grafo.

Lembrando que não é preciso construir todo o grafo. A ideia é só ir expandindo os nós de acordo com a estratégia. Na função "build_pancakes" (arquivo main.py) é possível passar a quantidade de panquecas e uma diferença de tamanho pra cada panqueca. Lembrando que essa diferença não influi em nada, é só mesmo para uma questão de visualização.

Na função "run" é possível passar um tempo de espera para visualizar com mais calma.

Também tem-se um módulo "priority_queue" que permite construção de filas de prioridades que utilizamos para resolver o problema e também um módulo "graph" utilizado para a estrutura de grafos.

Veja só execução do programa para o ordenamento de uma pilha com quatro panquecas (com time_sleep de 1 segundo):


O arquivo "main.py" está bem explicado, não irá oferecer dificuldades. Segue o link do repositório:



Nenhum comentário: