sábado, 28 de junho de 2014
quarta-feira, 18 de junho de 2014
O que é C#
Mais informações: http://msdn.microsoft.com/pt-br/library/kx37x362.aspx
Algorítimo Dijkistra
Concebido
pelo cientista da computação holandês Edsger
Dijkstra em 1956 e publicado em 1959. Visa solucionar o problema
do caminho mais curto num grafo dirigido ou não dirigido
com arestas de peso não negativo, em tempo
computacional.
Este algorítimo
visa solucionar o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo,
em tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número
de vértices.
Esse algoritmo calcula o caminho de custo mínimo
entre vértices de um grafo. Após, ter sido feita a escolhido de um vértice como
raiz da busca, este algoritmo irá calcular o custo mínimo desta vértice para
todos os demais vértices do grafo.
Podemos utilizar o algoritmo de Dijkstra para resolver problemas como o deslocamento
de cidade para outra. Qual das várias estradas escolher? Qual oferece uma uma trajetória de menor caminho?
Algoritmo
de Dijkstra toma uma decisão que parece ótima no momento. Se considerarmos P um
menor caminho entre 2 vértices U e V, todo sub-caminho de P é um menor caminho
entre 2 vértices pertencentes ao caminho P, desta forma construímos os melhores
caminhos dos vértices alcançáveis pelo vértice inicial determinando todos os
melhores caminhos intermediários.
Nota:'um
menor caminho' caso existam 2 'menores caminhos' apenas um será descoberto.
Este
algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial
I. Neste algoritmo cada passo irá busca nas adjacências dos vértices
pertencentes a S aquele vértice com menor distância relativa a I e irá adicioná-lo
a S, isso é repetido até que todos os vértices alcançáveis por I estejam em S.
As arestas que ligam os vértices já pertencentes a S são desconsideradas.
Podemos
citar como exemplo prático as rotas da TAM. Então,como encontrar o melhor
caminho entre dois pontos que estão interligados diretamente.
Como funciona o Algorítimo
de Dijkstra
Este algoritmo funciona da seguinte maneira: parte
de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando
esta estimativa. Ele considera que um vértice estará fechado quando já tiver
sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até
ele. Caso contrário ele dito estar aberto.
Algoritmo: Seja G(V,A) um grafo orientado e s
um vértice de G:
1.
Atribua valor zero à
estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às
demais estimativas;
2.
Atribua um valor
qualquer aos precedentes (o precedente de um vértice t é o vértice que
precede t no caminho de custo mínimo de s para t);
3.
Enquanto houver vértice
aberto:
seja k um vértice ainda aberto cuja
estimativa seja a menor dentre todos os vértices abertos;
feche o vértice k
Para todo vértice j ainda aberto que seja
sucessor de k faça:
some a estimativa do vértice k com o custo
do arco que une k a j;
caso esta soma seja melhor que a estimativa
anterior para o vértice j, substitua-a e anote k como precedente
de j.
Vejamos um exemplo de seu funcionamento:
Neste caso, quando todos os vértices estiverem sido
fechados, os valores obtidos serão os custos mínimos dos caminhos que partem do
vértice tomado como raiz da busca até os demais vértices do grafo.
O caminho propriamente dito é obtido a partir dos
vértices chamados acima de precedentes.
Podemos tomar como exemplo como o caminho de custo
mínimo que vai de s até v, cujo custo mínimo é 9. O vértice
precendente de v na última das tabelas acima é u. Sendo assim, o caminho é:
s ® ... ® u ® v
Por sua vez, o precedente de u é x. Portanto, o
caminho é:
s ® ... ® x ® u ® v
Por último, o precedente de x é o próprio vértice
s. Logo, o caminho de custo mínimo é:
s ® x ® u ® v
Então, o algoritmo de Dijkstra irá computar apenas
um único caminho de custo mínimo entre um dado par de vértices. Para se obter
todos os caminhos de custo mínimo entre dois vértices é necessário modificar a
forma de anotação dos precedentes. A modificação no passo 3 indicada a seguir é
suficiente para permitir o cômputo de todos os caminhos por um processo similar
ao descrito acima.
...
Para todo vértice j ainda aberto que seja sucessor de k faça:
Para todo vértice j ainda aberto que seja sucessor de k faça:
some a estimativa do vértice k com o custo
do arco que une k a j;
caso esta soma seja melhor que a estimativa
anterior para o vértice j, substitua-a e anote k como precedente
único de j;
caso esta soma seja igual à estimativa anterior para
o vértice j, adicione k ao conjunto dos precedentes de j;
Supondo que o peso do arco (y,v) no grafo acima
fosse 2, haveriam dois caminhos de custo mínimo do vértice s para v. Esta
duplicidade resulta em dois precedentes para o vértice v:
|
Vértices
|
s
|
u
|
v
|
x
|
y
|
|
Estimativas
|
0
|
8
|
9
|
5
|
7
|
|
Precedentes
|
s
|
x
|
u,y
|
s
|
x
|
Exemplo
das vértices, estimativas e precedentes
Sendo assim, os dois caminhos são dados por: (s ® ... ® u ® v) e (s ®
... ® y
® v).
Seguindo as precedências
para u e y nestes dois casos obtemos os dois caminhos: (s ® x ® u ® v) e (s ®
x ® y ® v)
Algorítimo de Dijkstra
Passo a Passo
1º passo: iniciamos os valores:
V[G] é o conjunto de vértices(v) que formam o Grafo
G. d[v] é o vetor de distâncias de s até cada v. Admitindo-se a pior estimativa
possível, o caminho infinito. π[v] identifica o vértice de onde se origina uma
conexão até v de maneira a formar um caminho mínimo.
2º passo: usamos o conjunto Q, cujos
vértices ainda não contém o custo do menor caminho d[v] determinado.
3º passo: realizamos uma série de relaxamentos das
arestas, de acordo com o código:
w(u, v) é o peso(weight) da aresta que vai de u a
v.
u e v são vértices quaisquer e s é o vértice
inicial. ffd extrair-mín(Q), pode usar um heap de mínimo ou uma lista de vértices onde se extrai
o elemento u com menor valor d[u].
No final do algoritmo teremos o menor caminho entre
s e qualquer outro vértice de G. O algoritmo leva tempo O(m + n log n)
caso seja usado um heap de Fibonacci, O(m
log n) caso seja usado um heap binário e
O(n²) caso seja usado um vetor para armazenar Q.
Pontos Negativos
O problema que encontramos neste a algoritmo de
Dijkstra, é que ele não consegue encontrar o menor caminho em um grafo com
pesos negativos. Neste caso teríamos que utilizar o algoritmo de Floyd-Warshall, que consegue descobrir a menor distância entre
todos os pares de vértices de qualquer grafo sem ciclos com peso negativo em
uma complexidade de tempo O(V³).
Ele não garante, a exatidão caso haja a presença de
arcos com valores negativos.
Pontos Positivos
Esse algorítimo embora seja bem simples, possui um
bom nível de performance.
Como Obter o Número de Semanas entre um Intervalo de Semanas
Para este exemplo iremos utilizar a função DATEPART. Esta função retorna um inteiro que representa uma data específica.
Datepart - É a parte de date (um valor de data ou hora) para a qual um integer será retornado. A tabela a seguir lista todos os argumentos datepart válidos. Equivalentes de variável definidos pelo usuário não são válidos.
datepart
|
Abreviações
|
year
|
yy , yyyy
|
quarter
|
qq , q
|
month
|
mm , m
|
dayofyear
|
dy , y
|
day
|
dd , d
|
week
|
wk , ww
|
weekday
|
dw
|
hour
|
hh
|
minute
|
mi, n
|
second
|
ss , s
|
millisecond
|
ms
|
microsecond
|
mcs
|
nanosecond
|
ns
|
TZoffset
|
tz
|
ISO_WEEK
|
isowk , isoww
|
O exemplo abaixo irá retornar a quantidade de semanas que existem dentro de um intervalor de datas.
SELECT DATEPART( WK, DataCompra) AS NrSemana,
NomeClinete, DataCompra
FROM [Teste].[dbo].[Compra]
WHERE DataCompra between '18/01/2014' and '15/02/2014'
ORDER BY DataCompra
Espero que tenham gostado, e até a próxima.
aspnetwf@gmail.com
Fonte:
Assinar:
Postagens (Atom)