[]
Algoritma Sorusu: Optimal Storage on Tape Problem
Namı diğer "Cassette filling problem" için çözüm algoritması arıyorum. Bilen bilir, bilmeyenler için bir varyasyonu şöyle bir şey: Elimizde farklı ya da aynı uzunluklarda n adet şarkı var ve biz bunları en kısa teyp gidecek şekilde bir kasede kaydedeceğiz. Yani misal n=9 için 1,3,6,7 numaralı şarkılar A yüzüne, 2,4,5,8,9 numaralar B yüzüne olursa en kısa teyp gider gibi. Bunun çözüm algoritması nedir? Yalnız pseudocode lazım, pseudocode olmazsa pek işime yaramaz :)
Hatta şu sayfadaki tüm problemlerin çözüm algoritmaları olursa pek bir şahane olur: www.123eng.com
Hatta şu sayfadaki tüm problemlerin çözüm algoritmaları olursa pek bir şahane olur: www.123eng.com
oturup baştan algoritma yazmayacağım ama yol göstereyim.
şarkıların toplam süresini bul
ikiye böl ve bir yüze kaç dakikalık şarkı düştüğünü bul.bu sayıya x diyelim.
daha sonra bütün şarkıların kombinasyonlarını al ve x'e en yakın sonucu veren kombinasyonu bir yüze, kalanları da diğer yüze yazdır.
şarkıların toplam süresini bul
ikiye böl ve bir yüze kaç dakikalık şarkı düştüğünü bul.bu sayıya x diyelim.
daha sonra bütün şarkıların kombinasyonlarını al ve x'e en yakın sonucu veren kombinasyonu bir yüze, kalanları da diğer yüze yazdır.
- kimlanbu
(04.01.08 20:40:57)
Teşekkürler ancak bütün şarkıların kombinasyonlarını almak verimli bir algoritma değil sanırım. n'in sonsuza gitiğini düşünerek bir çözüm lazım...
- crown (04.01.08 20:59:27)
eğer endüstri mühendisi veya adayı iseniz yazacağımı zaten biliyorsunuz;
bahsettiğiniz bir çeşit parallel machine scheduling problem. (makine sayısı 2)
Bu şekilde ele alırsanız internette daha fazla kaynak bulabileceğinizi sanıyorum. Hatırladığım kadarıyla bu problemler heuristic metodlarla çözülüyordu yani kimlanbu'nun önerisi haklı çıkarsa şaşırmayın...
kolay gelsin...
bahsettiğiniz bir çeşit parallel machine scheduling problem. (makine sayısı 2)
Bu şekilde ele alırsanız internette daha fazla kaynak bulabileceğinizi sanıyorum. Hatırladığım kadarıyla bu problemler heuristic metodlarla çözülüyordu yani kimlanbu'nun önerisi haklı çıkarsa şaşırmayın...
kolay gelsin...
- hgn (04.01.08 22:11:31)
Evet derste hoca da bahsetmişti endüstri mühendisliği yaklaşımı ile de çözüme ulaşıldığını ama hocanın, dolayısıyla benim, istediğimiz çözüm bu değil. Bilgisayar mühendisliği okuyorum. Parallel machine scheduling de bu soru gibi br dynamic programming sorusu ama problemlere farkılı branşların farklı yaklaşımları var :) Endüstri mühendisliği sanırım biraz daha pratiğe dayalı varsayımlarla (sayılar makul değerlerde) çözümler üretiyor. Misal sorduğum soruda şarkı sayısının 2^50 olduğunu düşünürseniz artık siz hesaplayın kaç farklı kombinasyon olur, bu kombinasyonları hesaplamak mı uzun sürer yoksa problemi çözmek mi :)
- crown (04.01.08 22:24:01)
Valla o uzun cevabi okumadim ama kesin bir yerlerinde optimizasyon hatasi olan bi yol su olabilir.
sarkilari uzunluga gore sirala
toplam uzunlugu bul
en buyuk sarkiyi al
sonra siradaki en buyuk sarkiyi al ve kontrol et eger toplam uzunlugun yarisini geciyorsa bir sonrakini en buyugu dene bunu bole loopda yap.
Eger bir sonra eklenecek adaylarin hepsi yari uzunlugu geciriyorsa en kucugu al ve ekle. edit: Eklemeden once ama kalanlarin toplam uzunlugunu ekleyince elde edilecek uzunluk ile karsilastir.
Dur ben bi dusinim bu calisir mi.
evet bazi sorunlari var ama hizli gibi duruyor.
Daha delikanli bi cozum geldi aklima ama suan kelimeler kifayetsiz kaliyor.
sarkilari uzunluga gore sirala
toplam uzunlugu bul
en buyuk sarkiyi al
sonra siradaki en buyuk sarkiyi al ve kontrol et eger toplam uzunlugun yarisini geciyorsa bir sonrakini en buyugu dene bunu bole loopda yap.
Eger bir sonra eklenecek adaylarin hepsi yari uzunlugu geciriyorsa en kucugu al ve ekle. edit: Eklemeden once ama kalanlarin toplam uzunlugunu ekleyince elde edilecek uzunluk ile karsilastir.
Dur ben bi dusinim bu calisir mi.
evet bazi sorunlari var ama hizli gibi duruyor.
Daha delikanli bi cozum geldi aklima ama suan kelimeler kifayetsiz kaliyor.
- badseed (05.01.08 02:56:27)
Teşekkürler cevaplar için, yalnız önce de belirttiğim gibi endüstri değil bilgisayar mühendisliği yaklaşımı işime yarıyor. badseed ve comptrol'un algoritmalarını deneyeceğim. comptrol; 100 dolara İstanbul'da singıl bağyan'lar var, yemekten fazlasını da alırsın hem hehe :)
- crown (05.01.08 07:49:52)
1
