Problema da linha de montagem

Problema: Em uma fábrica há duas linhas de montagem, cada uma com n estações, a j-ésima estação na linha i é denotada por Si,j e o tempo de montagem nessa estação é ai,j. Um chassi de automóvel entra na fábrica e vai para a linha i (onde i = 1 ou 2), demorando o tempo ei. Depois de passar pela j-ésima estação em uma linha, o chassi vai para a (j+1)-ésima estação de uma das linhas. Não há nenhum custo de transferência se ele ficar na mesma linha, mas demora o tempo ti,j para transferir o automóvel para a outra linha após a estação Si,j. Depois de sair da n-ésima estação em uma linha, decorre o tempo xi para oautomóvel concluído sair da fábrica. O problema é determinar que estações escolher na linha 1 e quais escolher na linha 2 para minimizar o tempo total de passagem de um automóvel pela fábrica.
Solução: Em termos gerais, podemos dizer que uma solução ótima para um problema (encontrar o caminho mais rápido passando pela estação Si,j) contém em seu interior uma solução ótima para subproblemas. (encontrar a passagem mais rápida por S1,j-1 ou S2,j-1). Referimos a essa propriedade como subestrutura ótima, e e ela é uma das indicações de aplicabilidade da programação dinâmica.

Se examinarmos um caminho mais rápido através da estação S1,j ele tem de passar pela estação j-1 na linha 1 ou na linha 2. Desse modo, o caminho mais rápido pela estação S1,j é:

• O caminho mais rápido pela estação S1,j-1, e depois diretamente pela estação S1,j.

• O caminho mais rápido pela estação S2,j-1, uma transferencia da linha 2 para a linha 1, e depois através da estação S1,j.
  

Usando o raciocínio simétrico fazemos a mesma coisa para o caminho mais rápido através da estação S2,j.

Para resolver o problema de encontrar o caminho mais rápido através da estação j de uma das linhas, resolvemos os subproblemas de encontrar os caminhos mais rápidos pela estação j-1 em ambas as linhas. Deste modo, podemos elaborar uma solução ótima para uma instância do problema de programação da linha de montagem pela elaboração de soluções ótimas para subproblemas.

Uma solução recursiva: No problema de programação da linha de montagem, escolhemos como nossos subproblemas os problemas de encontrar o caminho mais rápido pela estação j em ambas as linhas, para j = 1, 2, ..., n. Seja f[i][j] o tempo mais rápido possível para levar um chassi desde o ponto de partida até a estação Si,j.
Nosso objetivo final é descobrir o tempo mais rápido para levar um chassi por todo o percurso na fábrica, que denotamos por F. O chassi tem de passar por todo o caminho até a estação n na linha 1 ou 2, e depois até a saída da fábrica. Tendo em vista que o mais rápido desses caminhos é o caminho mais rápido através da fabrica inteira, temos:
F = min( f[1][n] + x1 , f[2][n] + x2 ) .
Também é fácil raciocinar sobre f[1][1] e f[2][1]. Para chegar até a estação 1 em qualquer linha, basta um chassi ir diretamente até essa estação. Assim,
f[1][1] = e1 + a[1][1] ,
f[1][2] = e2 + a[2][1] .
Agora, vamos considerar como calcular f[i][j] para j = 2, 3, ... n (i = 1 ou 2). Temos que:
f[1][j] = min ( f[1][j-1] + a[1][j] , f[2][j-1] + t[2][j-1] + a[1][j] ) .
Simetricamente temos
f[2][j] = min ( f[2][j-1] + a[2][j] , f[1][j-1] + t[1][j-1] + a[2][j] ) .

CakePHP - Configurando

Os pré-requisitos para o bom funcionamento do seu CakePHP são:
- Servidor Apache (com o módulo re_write ativado)
- PHP
- Banco de dados MySQL

Agora você pode baixar o CakePHP e descompactar o arquivo.

No meu caso criei uma pasta 'blog' no servidor '/var/www/blog' e movi os arquivos que estão dentro da pasta descompactada para o diretório do blog. Então ficará assim:


Agora acesse http://localhost/blog, você verá a seguinte janela:


De uma olhada nas mensagens que aparecem.

Para configurar corretamente a primeira coisa é dar a permissão de escrita na pasta '/var/www/blog/app/tmp/' com o comando no terminal:
chown -R www-data /var/www/blog/app/tmp/

O CakePHP apresenta um erro 'Your database configuration file is NOT present.', para corrigir este erro você apenas precisa renomear o arquivo de configuração do banco de dados (database.php.default) da sua aplicação:
mv /var/www/blog/app/config/database.php.default /var/www/blog/app/config/database.php

No arquivo renomeado 'database.php' colocamos as informações sobre nosso banco de dados:


Agora apenas precisamos alterar a chave do 'Security.salt', que serve para gerar as hash's em senhas que precisam ser criptografadas. Abrimos o arquivo 'core.php', que está localizado no diretório '/var/www/blog/app/config/', e alteramos a seguinte linha:
Configure::write('Security.salt', 'DYhG93b0qyJfIxfs2guVoUubWwvniR2G0FgaC9mi');
para
Configure::write('Security.salt', 'HadsfEdasfADYhG93b0qyJfIxfs2guVoUubWwvniR2G0FgaC9mi');

Acesse novamente http://localhost/blog, então você deverá ver:


Configurado!


Como este é o meu primeiro post espero comentários para que eu possa melhorar. O que vocês acham? Devo ser mais detalhado ou neste nível já está bom?

Uma introdução!!!

Neste blog vou começar a escrever assuntos relacionados a algoritmos, como técnicas de programação, frameworks, padrões de projeto, coisas que eu achar interessantes na faculdade e experiências que eu tive enquanto estudava estes assuntos.
Especificamente me interesso com programação de sistemas para web e maratona de programação.
Até hoje já participei de duas maratonas de programação, onde tivemos resultados razoáveis. Constumo treinar no site: http://br.spoj.pl/
E quanto a programação para Web já programo a alguns anos.

Vamos começar a mágica...