İlginç Sorular ve Bulmacalar

Sanat Galerisi Problemi: Bir Galeride Güvenlik İçin En Az Kaç Kişi Gerekir?

Büyük bir sanat galerisinde güvenlik şefi olduğunuzu hayal edin. Galeri duvarlarını kaplayan çok değerli tablolar mevcut ve bu tabloların hırsızlığa ve vandalizme karşı korunmaları gerekiyor. Galeri, farklı şekil ve büyüklükteki odalardan oluşuyor. Üstelik her bir resmin başına bir görevli dikecek kadar da paranız yok. Bu durumda en az sayıda güvenlik görevlisi kullanarak galerideki tüm resimlerin güvenliğini nasıl sağlayabilirsiniz? Basit bir soru gibi gözükse de okuduğunuz bu problem Art gallery problem yani sanat galerisi problemi / müze problemi olarak bilinen hesaplamalı geometrideki önemli sorulardan birisidir.

Problem 1973’te Victor Klee tarafından ortaya atılmış ve 1975’te Vaclav Chvátal tarafından ispatı yapılmıştır. Ancak bu ispat oldukça karışık olduğu için problemin ikinci ve daha kısa bir ispatı 1978’de Steve Fisk tarafından gerçekleştirilmiştir. Geometrik terimlerle, problem şu şekildedir: n-köşeli bir basit çokgen verildiğinde, çokgenin içinin her noktasını görmek için minimum koruma sayısı nedir?

Hesaplamalı geometri, geometrik olarak ifade edilebilen algoritmaların incelenmesine ayrılmış bilgisayar bilimlerinin bir dalıdır. Hesaplamalı geometride problemler matematiksel görselleştirme ve modelleme yoluyla bilgisayar bilimlerine dahil edilmiştir. Bu tarz geometri problemleri gerçekçi bir kullanıcı deneyimi yaratmak için genellikle sanal bir dünyaya dayalı hesaplamalar yapmanın gerekli olduğu video oyunu programlamasında da doğal olarak karşımıza çıkar. Şimdi problemin çözümüne geçebiliriz.

Galerinin Güvenliğini Sağlamak İçin Gerekli En Az Sayıda Kişiyi Nasıl Belirleyebiliriz?

Problemde tüm duvarları izlemek için gereken minimum koruma sayısını bilmemiz gerekiyor. Duvarların düz olduğunu ve iki duvarın birleştiği bir köşede bulunan bir muhafızın her iki duvardaki her şeyi görebileceğini varsayalım. Ayrıca, bir muhafızın görüşünün hiçbir zaman engellenmediğini ve 360 derece etrafında dönebileceğini kabul edeceğiz. Son olarak korumalarımız hareket etmeyecek. Çokgenin köşelerinde bulundukları yerden etrafı gözlemleyecekler.

Üçgen biçiminde bir galeri, içinde herhangi bir yere yerleştirilmiş tek bir güvenlik görevlisi tarafından her zaman rahatça kontrol edilebilir. Aslında, galerimiz sadece üçgen değil herhangi bir dışbükey çokgen ( dikdörtgen, beşgen…) olduğu zaman bir güvenlik görevlisi her zaman yeterli olacaktır. Ancak eğer galerimizin şekli girintilere sahip ise o zaman işler karışmaya başlıyor. Örneğin aşağıdaki biçimde olan 12 duvarlı bir galeriyi ele alalım. Bu galeri için 4 koruma görevlisi yeterli olacaktır.

Sıradan binalar elbette dikdörtgen olma eğilimindedir, ancak sanat galerileri her türlü çılgın şekle sahip olabilir, bu nedenle genel bir cevap bulmak her zaman kolay değildir. Sanat galerisi problemi bu ve bunun gibi durumlarda en az sayıda güvenlik görevlisi kullanımını sorgular.

İhtiyaç duyulan koruma görevlisinin sayısının çokgenin köşelerinin sayısına bağlı olacağı sezgisel olarak anlaşılabilir. Bu yüzden girintili çıkıntılı şekle sahip olan bir galeriyi güvende tutabilmemiz için onu çokgenlere ayırmamız gerekir. Böylece her çokgenin içine bir güvenlik görevlisi yerleştirmemiz mümkün olacaktır. Fisk’in zekice argümanı, n köşeli basit bir çokgen şeklindeki bir galeriyi korumak için asla n/3’ün tam kısmından fazla korumaya ihtiyacınız olmadığını bize gösterir. On iki kenarlı yukarıdaki galerimiz için bu değer maksimum 12/3 = 4 iken sekiz kenarlı galeri için ikidir.

Sanat Galerisi Probleminin Olası Çözümleri

Genel olarak sorunu çözmek için galeriyi üst üste binmeyen üçgenlere nasıl bölebileceğimize bakacağız. Eğer bir çokgenin S kadar kenarı var ise bu çokgen S-2 kadar üçgene ayrılabilir. Üçgen, yalnızca tek bir korumaya ihtiyaç duyan dışbükey çokgenlerden biri olduğu için, o zaman çokgeni ayırdığımız üçgen sayısı kadar güvenlik görevlisi sayısına ihtiyacımız olacağını söylemek yanlış olmaz.

Her bir koruma, karşılık gelen üçgeni denetleyecektir ve üçgenler birlikte tüm poligonu kapladığından, tüm poligonun korunmasını sağlanacaktır. Ancak daha az sayıda gerekli koruma sayısının bulunması da mümkündür. Çünkü karşı köşegenleri birleştirerek bir kareyi her zaman iki üçgene bölebiliriz, ancak tüm duvarları izlemek için iki korumaya ihtiyacımız yoktur, bir kişi aslında yeterlidir.

Üçgenlere ayrılmış bir 9-gen

Bugün ziyaret ettiğiniz galerilerin çoğunda bu örnekler gibi garip duvar planları olmayacaktır. Galeriler aslında aşağıdaki gibi dik açılardan oluşmuş duvarlara sahip olacaklardır. Böyle bir galeride gerekli güvenliği sağlamak için daha az görevli gerektiren dikdörtgenlere ayırma daha kullanışlı olacaktır. Bu durumda da galeriyi korumak için gerekli koruma sayısı ¼ × Köşe Sayısının tam sayı kısmı biçiminde olacaktır. Aşağıdaki on dört köşeli galeri için bu sayı üçtür.

Bir başka geleneksel dik açılı galeri türü, odalara bölünen biçimlidir. Aşağıda on odalı örnek bir galeri örebilirsiniz.

Bu durumda da galeriyi dikdörtgenlere bölmek daha mantıklıdır. İki farklı odayı birbirine bağlayan açıklığa bir koruma yerleştirirseniz, iki oda da aynı anda güvende olacaktır. Öyleyse bu durumda galeride gerekli olan güvenlik görevlisi sayısı, ½ × Oda Sayısı’na eşit veya ondan büyük bir sonraki tam sayı biçiminde olacaktır. Yukarıdaki görseldeki on odalı galeri için bu beştir.

Sanat galerisi problemi ile ilgili harika olan şey matematikçilere keşfedilecek bir dizi yeni yol sunmasıdır. Bazılarında muhafızların hareket ettiği, bazılarında sınırlı görüş alanlarına sahip oldukları veya köşeleri görmelerine yardımcı olacak aynaların olduğu her türlü senaryo matematikçiler tarafından incelenmiştir. ( Kaynaklarda bu gibi detaylara erişebilirsiniz.).

Gerçek dünyada bir sanat galerisine güvenlik görevlisi alınırken bu hesaplamalara göre hareket edilmese de aynı yaklaşım güvenlik kameralarının konumlandırılmasında kullanılmaktadır.

Kaynaklar ve İleri Okumalar:

Ana sayfa » MATEMATİK » İlginç Sorular ve Bulmacalar » Sanat Galerisi Problemi: Bir Galeride Güvenlik İçin En Az Kaç Kişi Gerekir?

Matematiksel