Paralel Algoritma - Tasarım Teknikleri
Paralel bir algoritma için uygun bir tasarım tekniği seçmek en zor ve önemli görevdir. Paralel programlama problemlerinin çoğunun birden fazla çözümü olabilir. Bu bölümde, paralel algoritmalar için aşağıdaki tasarım tekniklerini tartışacağız -
- Böl ve fethet
- Açgözlü Yöntem
- Dinamik program
- Backtracking
- Şube ve Bağlı
- Doğrusal programlama
Böl ve Yönet Yöntemi
Böl ve yönet yaklaşımında, problem birkaç küçük alt probleme bölünmüştür. Daha sonra alt problemler özyinelemeli olarak çözülür ve orijinal problemin çözümünü elde etmek için birleştirilir.
Böl ve yönet yaklaşımı, her seviyede aşağıdaki adımları içerir -
Divide - Asıl problem alt problemlere bölünmüştür.
Conquer - Alt problemler özyinelemeli olarak çözülür.
Combine - Alt problemlerin çözümleri bir araya getirilerek asıl problemin çözümü elde edilir.
Böl ve yönet yaklaşımı aşağıdaki algoritmalarda uygulanır -
- Ikili arama
- Hızlı sıralama
- Sıralamayı birleştir
- Tamsayı çarpımı
- Matris ters çevirme
- Matris çarpımı
Açgözlü Yöntem
Açgözlü optimize çözüm algoritmasında, her an en iyi çözüm seçilir. Açgözlü bir algoritmanın karmaşık problemlere uygulanması çok kolaydır. Bir sonraki adımda hangi adımın en doğru çözümü sağlayacağına karar verir.
Bu algoritmaya greedyçünkü daha küçük örnek için en uygun çözüm sağlandığında, algoritma toplam programı bir bütün olarak dikkate almaz. Bir çözüm düşünüldüğünde, açgözlü algoritma bir daha asla aynı çözümü düşünmez.
Açgözlü bir algoritma, mümkün olan en küçük bileşen parçalarından bir grup nesne oluşturarak yinelemeli olarak çalışır. Özyineleme, belirli bir sorunun çözümünün, o sorunun daha küçük örneğinin çözümüne bağlı olduğu bir sorunu çözmek için bir prosedürdür.
Dinamik program
Dinamik programlama, problemi daha küçük alt problemlere bölen ve her bir alt problemi çözdükten sonra, dinamik programlama nihai çözümü elde etmek için tüm çözümleri birleştiren bir optimizasyon tekniğidir. Böl ve yönet yönteminin aksine, dinamik programlama alt problemlerin çözümünü birçok kez yeniden kullanır.
Fibonacci Serisi için yinelemeli algoritma, dinamik programlama örneğidir.
Geri İzleme Algoritması
Geri izleme, kombinasyonel problemleri çözmek için bir optimizasyon tekniğidir. Hem programatik hem de gerçek hayat problemlerine uygulanır. Sekiz vezir problemi, Sudoku bulmacası ve bir labirentten geçmek geri izleme algoritmasının kullanıldığı popüler örneklerdir.
Geriye dönük izlemede, gerekli tüm koşulları karşılayan olası bir çözümle başlıyoruz. Sonra bir sonraki seviyeye geçiyoruz ve bu seviye tatmin edici bir çözüm üretmiyorsa, bir seviye geri dönüyor ve yeni bir seçenekle başlıyoruz.
Şube ve Sınır
Dal ve sınır algoritması, soruna en uygun çözümü elde etmek için kullanılan bir optimizasyon tekniğidir. Çözümün tüm alanında belirli bir problem için en iyi çözümü arar. Optimize edilecek fonksiyondaki sınırlar, en son en iyi çözümün değeri ile birleştirilir. Algoritmanın çözüm uzayının parçalarını tam olarak bulmasını sağlar.
Dal ve bağlı aramanın amacı, hedefe giden en düşük maliyetli yolu korumaktır. Bir çözüm bulunduğunda, çözümü geliştirmeye devam edebilir. Dal ve sınır arama, derinlemesine arama ve derinlik ilk aramada uygulanır.
Doğrusal programlama
Doğrusal programlama, hem optimizasyon kriterinin hem de kısıtlamaların doğrusal fonksiyonlar olduğu geniş bir optimizasyon işi sınıfını tanımlar. Maksimum kar, en kısa yol veya en düşük maliyet gibi en iyi sonucu elde etmek için kullanılan bir tekniktir.
Bu programlamada, bir dizi değişkenimiz var ve bir dizi doğrusal denklemi karşılamak ve belirli bir doğrusal amaç fonksiyonunu maksimize etmek veya en aza indirmek için bunlara mutlak değerler atamamız gerekiyor.