optimizasyon algoritması

AmeTaL · Mesaj gönderen **AmeTaL** » 19 May 2006 07:46

merhabaLar ufak bır program yazmak ıstıyorum fakat tam olarak bı algorıtma oturtabılmıs degilım

bır matrıs ıcınde (n X n bır kare matrıs) kı elemanları her satır we her sutundan sadece bır eleman secerek we toplam olarak mınımum toplamı werıcek bır algorıtma yazmak ıstıyorum aklıma ılk gelen matrısı bır strınggrıd ıcıne atıp
secılen elemanın satır we sutunları sılıp yenı bır matrıs olusturmak we bolece 1 eleman kalana kadar bu ısı dewam ettırmek olarak geldı ama hem grıdın ıcınde sectıgım sutun we satırı sılıp yenı bır gırıd ıcıne atamadım. hemde matrısın boyutları ornek olarak 100x100 oldugunda ben 100 ayrı matrısı nasıl olusturcam beceremedım.. baska bır yoll olarak ne yapabılırım acaba sımdıden ılgılenen herkese tsk ederım...

Mesaj gönderen **lazio** » 20 May 2006 12:10

iç içe 2 döngü ile satır ve sütunları dolaşıp, her satırdaki en küçük elemanı bulup toplama dahil edebilirsin..

AmeTaL · Mesaj gönderen **AmeTaL** » 20 May 2006 12:06

once cok tsk ederım

ya ılk once bende ole denedım fakat mesela matrıs

3 4 2
8 9 1
7 8 5

gıbı olsun sımdı 1. satır da en kucuk eleman 2(1,3) yı aldık 2 .satırdan artık 1(2,3)(1.satır we 3 sutun artık kullanılmayacak) secemıyorum o yuzden 9 weya 8 almam lazım 8<9 8(2,1) sectırdım 3. satırdan da artık 7(3,2)(1.satır 2.satır 1.sutun 3.sutun ıptal) yı secemıcem ıcın yıne 8(3,2) alıcak we toplam
8+8+2= 18 yapıcak oysakı burda en kucuk toplam

bırıncı satırdan 4 ıkıncı satırdan 1 son satırdan da 7 secılırseee
4+1+7= 12 yapıyor yanı en kucuk elemanı bulmak degıl en kucuk toplamı bulmam lazım . ben tek tek her eleman ıcın bu ısı yapayım dıyorum sonra tum toplamları bır dızı ıcıne ataıp dızıyı sıralatıp en kucuk elemanı alım dıyorum fakat matrısın boyutu buyuk olursa bu hem cok uzun hemde ıcınden cıkılmaz bı hal alıcak bıde daha farklı olarak nasıl cozerız? dun bıraz arastırdım da genetıc algorıtma karesel algorıtma falan dıyordu karesel optımızasyonla ılgılı bır algrıtma warmı paylasırsanız sevınırım zmn ayıran herkese cok tsk ederım

Mesaj gönderen **aslangeri** » 20 May 2006 12:26

s.a.

sanırım ihtimalleri tek tek kontrol eden recursive bir fonkisyon kullanman gerekecek.
güzel bir soru bakalım nasıl şeyler çıkacak.

kolay gelsin.

spiderman · Mesaj gönderen **spiderman** » 20 May 2006 12:38

Benim anlayamadigim her satirin en kucuk rakkamlarinin toplami en kucuk toplami vermezmi? Yani her satirdaki en kucuk elemani bulmak yeterli degilmi? eger oyle ise bence her satiri diziye atin ve siralatin boylece quick sort ile siralanmis dizinin ilk rakkami en kucuk rakkam olur.

yok eger yanlis anladiysam yanlisimi soylerseniz uzerinde calismak isterim

Mesaj gönderen **aslangeri** » 20 May 2006 01:40

bir satırdaki en küçük rakamı bulduğun zaman
diğer satırlarda o sütunu kullanmıyorsun.

Mesaj gönderen **rsimsek** » 20 May 2006 01:55

O zaman o sütunun olduğu diğer tüm satırlara 99999 gibi büyük bir rakkam yada -1 atarsın

AmeTaL · Mesaj gönderen **AmeTaL** » 21 May 2006 12:18

ya malıyet hesabı yapacagım 9999 gıbı buyuk bır rakam olmazda belkı -1 denyebılırım we sıfırdan kucuk olursa alma derım bır ıkı gundur bunu arastıyorum karesel optımızasyon dıe bıse gordum sanırım hesabını yapıyormus ama hıc bırsey anlamadım

bu konu hakkında bılgısı olan warmı ?? ama -1 olayını deneyecegım eger calısırsa kodu gonderrım herkese tsk ler

Mesaj gönderen **Murat DİCLE** » 21 May 2006 01:09

merhaba
şimdi anladığım kadarıyla

3 4 2
8 9 1
7 8 5

matrisinde bahsettiğin gibi satır taramasıyla

8+8+2= 18 sunucuna varıyorsun ama bunun aslında en küçük toplam olmadığını söylüyorsun aslında en küçük toplamın

4+1+7= 12 olması gerektiğini söylüyorsun.

şimdi bilgisayar gibi değilde insan gibi düşünürsek, şu küçük matriste aslında istediğimiz her sütündaki en küçük değeri almak oluyor..

öyleyse tarama işlemini satır değilde sütün baz alınarak yapmak mantıklı geliyor.

şöyle kafadan bir matris sallıyacam bakalım düşündüğüm olacak mı?

Kod: Tümünü seç

      01   02   03   04   05
----------------------------------------
01|   12   33   10   90   48
  |
02|   20   21   22   77   28
  |
03|   66   54   18   91   56
  |
04|   71   42   68   95   11
  |
05|   13   34   12   11   22

dediğim mantıkla her sütündaki en küçük değeri alırsak.

Kod: Tümünü seç

1. sütünda : 12   (1,1)
2. sütünda : 21   (2,2)
3. sütünda : 10   (1,3)
4. sütünda : 11   (5,4)
5. sütünda : 11   (4,5)

12+21+10+11+11 = 65

olacaktır.. yani doğrusu bu mu? tabi 1. satırdan iki değer elde edilmş oldu bu durumda, bu bir hataya sebep verecek mi? eğer evet hataya sebep verecek ise bu durumda 3. satırdan bilgi alınmadığını görüyoruz. Bu durumda 1. satırdan alınan 12 yerine 3. satırdan 18. almak mı doğru olacaktır.. (edit: burda kafayı sıyırdım düzeltemiyorum.. siz kendi mantığınızı geliştirin )

son dediğim gibi olacaksa, burada 3. satır yedek satır olarak bir kenara kaydedilecek, çünkü eğer alınan değerlerde aynı satırdan alınmış değerler var ise alınan aynı satırdaki (bu örnekte 1. satırı kastediyorum) değerlerin en büyüğü (yani 1. satırdaki 12 değeri) iptal edilip yedek satırdaki en küçük değeri alacağız. vs. vs.

şimdi..
1. önce sütün taraması yapılacak. en küçük olanlar alınacak.
2. hiç bir değer alınmamış satırlar bir yere not edilecek.
3. sütün taraması sonucunda aynı satırdan alınmış değerler var ise, sırasıyla en büyüğünden başlıyarak iptal edilip, kenara not eidlen satırlardaki en küçük ile yer değişecektir.

çözümü umarım anlatabilmişimdir. görüldüğü sorması kadar izah etmeside zor.

şimdi düşündükçe akla yeni fikirler geliyor..
1. sütün taraması yap.
2. satır taraması yap.
3. elde edilen yeni matrisi üst üste koy. çakışma olmayan kısımlar doğru olanlardır..

Aslında burada insan gibi düşünerek (komiklik olsun diye söylemiyorum) yani biz bir matrisi manuel olarak bakıpta nasıl çözümleyebiliyorsak problemede öyle yaklaşırsak daha kolay çözüleceğini biliyorum..

kolay gelsin...

AmeTaL · Mesaj gönderen **AmeTaL** » 21 May 2006 01:45

muratdicle yazdı:merhaba
Kod: Tümünü seç
      01   02   03   04   05
----------------------------------------
01|   12   33   10   90   48
  |
02|   20   21   22   77   28
  |
03|   66   54   18   91   56
  |
04|   71   42   68   95   11
  |
05|   13   34   12   11   22
dediğim mantıkla her sütündaki en küçük değeri alırsak.
Kod: Tümünü seç
1. sütünda : 12   (1,1)
2. sütünda : 21   (2,2)
3. sütünda : 10   (1,3)
4. sütünda : 11   (5,4)
5. sütünda : 11   (4,5)

12+21+10+11+11 = 65
olacaktır.. yani doğrusu bu mu? tabi 1. satırdan iki değer elde edilmş oldu bu durumda, bu bir hataya sebep verecek mi? eğer evet hataya sebep verecek ise bu durumda 3. satırdan bilgi alınmadığını görüyoruz. Bu durumda 1. satırdan alınan 12 yerine 3. satırdan 18. almak mı doğru olacaktır.. (edit: burda kafayı sıyırdım düzeltemiyorum.. siz kendi mantığınızı geliştirin )

once paylasımınız ıcın tsk ederım evet hocam 1 satırdan aldınız 2 deger olan 10 degerı hataya sebep olucak cunku kullanılan satır we sutun 2. bır kez kullanılmıyacaktır yanı matrısden alınan deger ler
12 (1,1)+21(2,2)+18(3,3)+11(4,5)+11(5,4) =73 seklınde olmalı (bu matrıs ıcın ) daha kucuk bır toplam cıkmıyor sanırsam denedım ama belkı yanlısım olabılır ozetle kullanılan satır we sutun bır daha kullanılmayacak ve en kucuk toplam bulunmaya calısıcak ve her satır ve sutun kullanılacak ..

muratdicle yazdı:şimdi..
1. önce sütün taraması yapılacak. en küçük olanlar alınacak.
2. hiç bir değer alınmamış satırlar bir yere not edilecek.
3. sütün taraması sonucunda aynı satırdan alınmış değerler var ise, sırasıyla en büyüğünden başlıyarak iptal edilip, kenara not eidlen satırlardaki en küçük ile yer değişecektir.

çözümü umarım anlatabilmişimdir. görüldüğü sorması kadar izah etmeside zor.

şimdi düşündükçe akla yeni fikirler geliyor..
1. sütün taraması yap.
2. satır taraması yap.
3. elde edilen yeni matrisi üst üste koy. çakışma olmayan kısımlar doğru olanlardır..

su an saat 01:39 we werdınız fıkrı tam anlamadım ama denemeden bılemem yarın ılk ısım bunu denemek olacaktırr tsk ederım umarım becerebılırım -1 fıkrıde aklımda belkı ıkısını bırlestırıp bıseler cıkartabılırızz ALLAH razı olsun hepınızden

Mesaj gönderen **bluekid** » 21 May 2006 03:13

pointer kullanarak -matrisi fonksiyona parametre olarak göndermek için lazım - şöyle bir fonksiyon oluşturarak ve recursive olarak çağırarak fonksiyon kendine parametre olarak gelen matrisi alıp en küçük elemanını bulup o elemanın bulunduğu satır ve sütunu silip yeni bir matris oluşturup kendini çağırır
C kullanıyorum kusura bakma kod veremiyeceğim

Opt2000 · Mesaj gönderen **Opt2000** » 21 May 2006 06:30

Selam,

Birşeyler yazdım ve senin verdiğin örnekte problemsiz çalıştı. Temel mantığı da aşağıdaki gibi.

1. Matrisi, normalin aksine iki boyutlu değil, tek boyutlu bir dizi olarak tanımladım. Bu aslında gerekli değil elbette, ama eğer kodun çok hızlı çalışması gerekiyor gibi bir durum varsa, iki boyutlu dizi yerine tek boyutlu bir dizide pointer işlemi yaptırmak daha hızlıdır.

2. Öncelikle matrisin her satırını özel olarak ifade edebileceğim bir yapı tanımladım. Bu yapı içinde de satırın min ve max değerlerini özel olarak tutabileceğim bir yapı kullanıyorum. Aşağıda ikisi de var.

Kod: Tümünü seç

type
  TRowItemValue = record
  AValue : double;
  ACol : integer;
end;

type
  PRowInfo = ^TRowInfo;
  TRowInfo = record
  RowIndex:integer;
  RowSum:Double;
  RowMin:TRowItemValue;
  RowMax:TRowItemValue;
end;

RowIndex:Kaçıncı satır olduğu
RowSum:Satırın toplamı (Buna gerek yok)
RowMin:Satırın en küçük elemanı ve elemanın sutunu değeri
RowMax:Satırın en büyük elemanı ve elemanın sutunu değeri

Daha sonra da aşağıdaki kodu yazdım.

Kod: Tümünü seç

  AList:=TList.Create;

  Total:=0;
  for J:=0 to Mat.RowCount-1 do
  begin
    //Her satırın detaylı bilgilerini al ve listeye ekle
    for I:=0 to Mat.RowCount-1 do
    begin
      New(RowInfo);
      RowInfo.RowIndex:=I;
      RowInfo.RowSum:=Mat.RowSum[I];
      RowInfo.RowMin:=Mat.RowMin[I];
      RowInfo.RowMax:=Mat.RowMax[I];

      AList.Add(RowInfo);
    end;

    //Listeyi sırala
    AList.Sort(RowListCompare);

    //Listedeki ilk elemanı kullan Sort fonksiyonuna bakarsan daha iyi anlaşılacak
    RowInfo:=AList.Items[0];
    Total:=Total + RowInfo.RowMin.AValue;
  
    //Değerini aldığın satırın tamamını ve değeri aldığın sütunun tamamını, matrisin en büyük değerinin bir üstüne ayarla. Böylece bir daha asla minimum olma olasılığı olmaz
    for I:=0 to Mat.ColCount-1 do
      Mat.Value[RowInfo.RowIndex, I]:=Mat.MaxValue;

    for I:=0 to Mat.RowCount-1 do
      Mat.Value[I, RowInfo.RowMin.ACol]:=Mat.MaxValue;

    //Listeyi temizle
    for I:=0 to Mat.RowCount-1 do
    begin
      RowInfo:=AList.Items[I];
      Dispose(RowInfo);
    end;
    AList.Clear;
  end;
  AList.Free;

Sıralama kodu da aşağıda

Kod: Tümünü seç

function RowListCompare(Item1, Item2: Pointer): Integer;
var
  I1, I2:PRowInfo;
begin
  Result:=0;

  I1:=PRowInfo(Item1);
  I2:=PRowInfo(Item2);

  if (I1.RowMax.AValue - I1.RowMin.AValue) < (I2.RowMax.AValue - I2.RowMin.AValue) then Result:=1;
  if (I1.RowMax.AValue - I1.RowMin.AValue) > (I2.RowMax.AValue - I2.RowMin.AValue) then Result:=-1;
end;

Temel mantık çok basit. Satırların minimum ve maksimum değerleri arasındaki fark ne kadar büyükse, ilk başta o satırı kullan.

Kolay gelsin,
Bahadır Alkaç

AmeTaL · Mesaj gönderen **AmeTaL** » 22 May 2006 04:36

hocam cok tsk ederım ederım kod ıcın
yanlız ben bunu calıstıramadım bu mat nesnesını ne beceremedım bır turlu calısan bır ornegı gonderebılırsın sımdıden cok tsk ederım

Opt2000 · Mesaj gönderen **Opt2000** » 22 May 2006 07:13

Selam,

Aşağıda linkten projenin tamamını indirebilirsin. Yalnız ufak bir konuda uyarmam gerekiyor, bazı yerlerde col ve row olayını karıştırmışım, o yüzden ters yazılmış gibi görünen yerler olabilir.

http://rapidshare.de/files/21108354/Matrix.rar.html

Kolay gelsin,
Bahadır Alkaç

AmeTaL · Mesaj gönderen **AmeTaL** » 22 May 2006 08:53

ALLAH razı olsun .... ya emeklerın ıcın cok cok tsk ederım