Anasayfa » Algoritmalar

Dinamik Programlama (Dynamic Programming) – En Kısa Yol Problemi

14 Aralık 2011 4.192 kez okundu Yorum yok
1 Star2 Stars3 Stars4 Stars5 Stars (Henüz hiç oy kullanılmadı. İlk oyu siz verin.)
Loading...

Arkadaşlar bu yazımda, matematik ve bilgisayar bilimleri alanlarında karmaşık problemleri çözmek için kullanılan bir metoddan bahsedeceğim. Ardından metodla alakalı bir problem olan en kısa yol probleminin çözümünü  ve ilgili c kodlarını yazacağım.

Dinamik programlama, karmaşık bir problemi daha alt problemlere bölerek çözmeye çalışan yöntemdir. Bu işlem sırasında elde edilen veriler bir yere kaydedilerek. Daha sonra ihtiyaç olduğunda tekrar hesaplamak yerine buradan kullanılır ve zamandan kazanç elde edilir.

Bir problemi dinamik programlama yöntemiyle çözebilmek için bazı şartlar vardır. Şöyle ki:

  • En iyi çözümün alt çözümleri de en iyi olmak zorundadır.
  • Var olan karmaşık problemi daha basit ve alt problemlere bölüm, bu alt problemleri çözdükten sonra elde ettiğimiz verilerle büyük problemi çözebilmek.
  • Sona gelindiğinde geriye doğru giderek problemi çözmek.
  • Her aşamada elde edilen verileri bir noktada saklamak.
Şimdi örnek bir resim üzerinde problemi anlayalım.
Örneğin yukarıdaki şekilde problem şudur. Bir üretim noktasında iki tane üretim bandı vardır. S1,1 S1,2 …şeklinde devam eden sıra ilk bant, S2,1 S2,2 … şeklinde devam eden sıra ikinci banttır. Ürünümüz enter noktasından bantlara girecek ve exit noktasından çıkacaktır. Amaç en kısa yolu takip etmektir. Kısıtlamalar şöyledir. Örneğin enter noktasıyla S1,1  arasındaki mesafe e1 yani 2 birim dir. Aynı bant üzerinde devam etmek iki noktanın toplamıdır. Yani, S1,1 den S1,2 ye geçerseniz 9 birimlik yol almış olursunuz ve daha önce de 2+7 =9 yol daha aldığınız için toplamda 18 birim yol eder. Ancak 1. banttan ikinci banta atlamak veya tam tersi ekstra yol demektir. Örneğin S1,1 den S2,2 ye geçmek S2,2 den dolayı 5, e1+A1,1 den dolayı 9 ve arada atlama mesafesi olan T1,1 den 2 birim eder ve S2,2 ye gelmek 16 birime mal olur. Bu şekilde hesaplandığına exit noktasına en kısa nasıl gidebiliriz.
Problemin çözümü şu şekilde olacak.Her S noktası için bir önceki iki S noktasının karşışaltırılıp kısa olanın hesaba dahil edilmesi olacaktır. Yani örneğin S1,2 için öncelikle S1,1 =2+7  ve  S2,1 = 4+8+2 = 14 değerleri karşılaştırılacak ve S1,2 noktasına en kısa gelen yol olan S1,1 in sonucu S1,2 ye yazılacak. Bu arada S1,2 nin yol maliyeti de eklenecek. Ve ayrı bir noktada her S noktasına hangi banttan gelindiği yazılacak.
Böylece sona vardığımızda okları geriye doğrı takip ederek en kısa yolu bulmuş olacağız.
Bu problemi çözen C kodu şu şekildedir.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
void print_station(int *l1,int *l2,int n)
{
	int i =l1[n+1];
	int j;
	printf("line: %d, station: %d\n",i,n);
	for(j=n;j>=2;j--)
	{
		if(i==1)
			i=l1[j];
		else
			i=l2[j];
		printf("line: %d, station: %d\n",i,j-1);
	}
}
void fastest_way(int a[3][6],int t[3][5],int e[3],int x[3],int n)
{
	int j;
	int *f1 = (int*)malloc(sizeof(int)*n+2);
	int *f2 = (int*)malloc(sizeof(int)*n+2);
	int *l1 = (int*)malloc(sizeof(int)*n+2);
	int *l2 = (int*)malloc(sizeof(int)*n+2);
 
	f2[1] = e[2] + a[2][1];
	f1[1] = e[1] + a[1][1];
 
	for(j=2;j<=n;j++)
	{
		if(f1[j-1]+a[1][j]<=f2[j-1]+t[2][j-1]+a[1][j])
		{
			f1[j] = f1[j-1]+a[1][j];
			l1[j]=1;
		}
		else
		{
			f1[j] = f2[j-1]+t[2][j-1]+a[1][j];
			l1[j]=2;
		}
		if(f2[j-1]+a[2][j]<=f1[j-1]+t[1][j-1]+a[2][j])
		{
			f2[j]=f2[j-1]+a[2][j];
			l2[j]=2;
		}
		else
		{
			f2[j]=f1[j-1]+t[1][j-1]+a[2][j];
			l2[j]=1;
		}
	}
	if(f1[n]+x[1]<=f2[n]+x[2])
	{
		f1[n+1] = f1[n] + x[1];
		l1[n+1]=1;
	}
	else
	{
		f1[n+1] = f2[n]+x[2];
		l1[n+1]=2;
	}
	print_station(l1,l2,n);
}
void main()
{
	////İnput değerleri
	int e[3]={0,2,4};
	int x[3]={0,3,6};
	int a[3][6]={{0,0,0,0,0,0},{0,7,9,3,4,8},{0,8,5,6,4,5}};
	int t[3][5]={{0,0,0,0,0,},{0,2,3,1,3},{0,2,1,2,2}};
	////////////////////
	int n = 5; //uzunluk
 
	fastest_way(a,t,e,x,n);
}
Ayrıca dinamik programlamada en çok kullanılan örnek fibonacci serisidir. O problemin anlatımına buradan ulaşabilirsiniz.

<<< Önceki:

Sonraki: >>>


Facebookta Paylaş

Yorum Bırakın!

Yorum yaz, yada kendi sitende trackback (Geri besleme) olarak ekle. Ayrıca RSS ile bu konuya üye olabilirsin. .

Nazik olun. Temiz tutun. Konu dışına çıkmayın. Spam yaratmayın.

Bu tagları kullanabilirsiniz:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Bloğumuz gavatarı desteklemektedir. Kendi gavatarınızı edinmek için lütfen Gravatar a üye olun.