Üçlü arama
Segment
[l, r] üzerindeki tek modlu bir fonksiyonun maksimumunu veya minimumunu bulmak için üçlü aramaya ihtiyacımız var. Bir fonksiyon, bir segmentte bir ekstremuma sahip olduğunda tek modludur.
Bir fonksiyonun maksimum değerlerinin aranması genellikle optimizasyon problemlerinde kullanılır. Örneğin, bir dik üçgende, alanın en büyük olacağı maksimum olası açıyı bulmamız gerekiyor. Bunun için
0 ile
90 arasındaki açılardan geçeceğiz ve bu segmentte önce artacak sonra azalacak bir alan arıyoruz yani. işlev tek modlu olacaktır.
Nasıl çalışır
Çalışma prensibi ikili aramaya benzer, ancak segmenti ikiye böldüğümüzde, segmentin ortası tam olarak uç noktaya düştüğünde ve & nbsp; net bir sonuç alamayacağız.
Bu nedenle böyle bir durumu önlemek için segmenti ikiye değil üçe bölmek gerekir ve uç vb. Olmayan kısmı sınırlar sonuçta birleşene kadar atıyoruz.
çift f( çift hipo, çift alfa) {
alfa = (alfa *M_PI)/180;
dönüş 0,5 * hipo * hipo * cos(alfa) * sin(alfa);
}
int ana() {
çift l = 0;
çift r = 90;
çift EPS = 1e-6;
çift hipo = 100;
while (r - l >=EPS) {
çift m1 = l + (r - l) / 3;
çift m2 = r - (r - l) / 3;
if (f(hipo, m1) < f(hipo, m2)) {
l=m1;
}
başka {
r=m2;
}
}
çıkış<< ((l + r) / 2);
0 döndür;
}
Üçlü arama altın bölüm yöntemi, bu da yakınsama oranını yaklaşık 2 kat artırır.
Kaynaklar
1) üçlü arama ve altın oran
2) üçlü arama