Tanrının algoritması

Tanrının algoritması, Rubik Küpü ile benzeri bulmaca ve matematiksel oyunların çözüm yöntemlerini konu alan bir kavram. Sözü edilen bulmacaları olabilecek en az adımda çözmeyi başaran algoritmayı tanımlamak için kullanılan bu terim, herhangi bir anda çözüme giden en kısa yolu bulabilen bir bilgenin var olduğu düşüncesine dayanmaktadır.

Kapsam ve tanım

Kavram, sonlu sayıda "durum" barındıran ve sınırlı sayıda "hamle"den oluşan bulmacalar için kullanılmaktadır. Çözüm, gelişigüzel bir durumdan başlayarak "son duruma" (ya da son durumlardan birine) ulaşmak olarak tanımlanır.

Bu tanıma uyan bazı bulmacalar Rubik Küpü, Hanoi kuleleri ve 15-bulmaca gibi parçalı bulmacalardır. Tek kişiyle oynanan peg solitaire ile misyonerler ve yamyamlar problemi gibi mantık bulmacaları da bu tanıma dahildir. Bu oyunların ortak özelliği, durumların köşeler, hamlelerin yollar olarak tanımlandığı bir yönlü çizge olarak modellenebilmeleridir.

Bu tür bir bulmacayı çözen algoritma, gelişigüzel bir durumdan başlayarak son duruma ulaşıncaya değin yapılacak hamleleri geri dönebilmelidir (bulmacanın o ilk durum için bir çözümü varsa). Bir çözümün en iyi olarak değerlendirilmesi için olabilecek en kısa hamle dizisine sahip olması gerekmektedir. Böylece, Tanrı'nın algoritması bu tür bir bulmacayı olabilecek en iyi çözümle sonuçlandıran algoritma olarak tanımlanabilir.

Bir algoritmanın "Tanrı'nın algoritması" olarak değerlendirilebilmesi için uygulanabilir olması gerekmektedir. Bu, algoritmanın aşırı kaynak (bellek alanı ya da zaman) tüketmemesi anlamını taşımaktadır. Örneğin, çok büyük bir başvuru çizelgesi kullanılarak çözüme çok kısa sürede ulaşılabilir; ancak, bu yöntem olağanüstü miktarda bellek alanına gerek duymaktadır.

Tam çözüme ulaşmaya çalışmaktansa bir durumdan (son durum olmamak koşuluyla) başlayıp yalnızca tek hamle (herhangi bir ideal çözümün ilk hamlesi olmak koşuluyla) yapmak üzerine de odaklanılabilir. Tek bir hamle için doğru sonucu üreten bu algoritma özyineleme yoluyla ilk problemin çözümünü bulan algoritmaya evrilebilmektedir. Buna benzer biçimde, tam çözüm için üretilen algoritma da ürettiği sonucun geri kalanı atılarak yalnızca bir hamle bulacak biçime dönüştürülebilir.

Örnekler

15-bulmacanın genellenmiş sürümü olan n-bulmacanın ideal çözümünü bulmanın NP-zor olduğu bilinmektedir.[1] Bu problem için uygulanabilir bir Tanrı'nın algoritması bulunup bulunmadığı ise belli değildir.

Hanoi kuleleri bulmacası için ise her disk sayısı için bir Tanrı'nın algoritması bulunmaktadır.[2]

Rubik Küpü için ideal çözüm yöntemi ilk kez 1997 yılında Richard Korf tarafından ortaya atılmıştır.[3] En kötü durum için 20 hamlede çözüme ulaşılabileceği 1995'ten bu yana bilinmesine karşın, 2010 yılında gerçekleştirilen deneyler sonucunda 20 hamlenin her durum için üst sınır oluşturduğu kanıtlanmıştır.[4] Bu sayı, Tanrının sayısı olarak adlandırılmaktadır.[5]

Ayrıca bakınız

Notlar

  1. ↑ Daniel Ratner, Manfred K. Warmuth (1986). "Finding a shortest solution for the N × N extension of the 15-puzzle is intractable". Proceedings AAAI-86. Ulusal Yapay Zeka Konferansı, 1986. s. 168–172
  2. ↑ Carlos Rueda, "An optimal solution to the Towers of Hanoi Puzzle".
  3. ↑ Richard E. Korf, "Finding optimal solutions to Rubik's Cube using pattern databases", Proc. Nat. Conf. on Artificial Intelligence (AAAI-97), Providence, Rhode Island, Temmuz 1997, s. 700–705
  4. ↑ "God's Number is 20". Cube20.org
  5. ↑ Jonathan Fildes (11.08.2010). "Rubik's Cube quest for speedy solution comes to an end". BBC News. http://www.bbc.co.uk/news/technology-10929159.

Kaynakça

This article is issued from Vikipedi - version of the 2/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.