Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
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 ""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 gibi . Tek kişiyle oynanan ile gibi 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 ideal çözümünü bulmanın NP-zor olduğu bilinmektedir. 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.
Rubik Küpü için ideal çözüm yöntemi ilk kez 1997 yılında tarafından ortaya atılmıştır. 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. Bu sayı, Tanrının sayısı olarak adlandırılmaktadır.
Ayrıca bakınız
Notlar
- ^ Daniel Ratner, Manfred K. Warmuth (1986). "Finding a shortest solution for the N × N extension of the 15-puzzle is intractable" 9 Mart 2012 tarihinde Wayback Machine sitesinde .. Proceedings AAAI-86. Ulusal Yapay Zeka Konferansı, 1986. s. 168–172
- ^ Carlos Rueda, .
- ^ 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
- ^ "God's Number is 20" 21 Temmuz 2013 tarihinde Wayback Machine sitesinde .. Cube20.org
- ^ Jonathan Fildes (11 Ağustos 2010). "Rubik's Cube quest for speedy solution comes to an end". BBC News. 25 Ağustos 2010 tarihinde kaynağından . Erişim tarihi: 25 Ağustos 2010.
Kaynakça
- David Joyner (2002). Adventures in Group Theory. Johns Hopkins University Press. .
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Tanrinin algoritmasi Rubik Kupu ile benzeri bulmaca ve matematiksel oyunlarin cozum yontemlerini konu alan bir kavram Sozu edilen bulmacalari olabilecek en az adimda cozmeyi basaran algoritmayi tanimlamak icin kullanilan bu terim herhangi bir anda cozume giden en kisa yolu bulabilen bir bilgenin var oldugu dusuncesine dayanmaktadir Kapsam ve tanimKavram sonlu sayida durum barindiran ve sinirli sayida den olusan bulmacalar icin kullanilmaktadir Cozum gelisiguzel bir durumdan baslayarak son duruma ya da son durumlardan birine ulasmak olarak tanimlanir Bu tanima uyan bazi bulmacalar Rubik Kupu Hanoi kuleleri ve gibi Tek kisiyle oynanan ile gibi da bu tanima dahildir Bu oyunlarin ortak ozelligi durumlarin koseler hamlelerin yollar olarak tanimlandigi bir yonlu cizge olarak modellenebilmeleridir Bu tur bir bulmacayi cozen algoritma gelisiguzel bir durumdan baslayarak son duruma ulasincaya degin yapilacak hamleleri geri donebilmelidir bulmacanin o ilk durum icin bir cozumu varsa Bir cozumun en iyi olarak degerlendirilmesi icin olabilecek en kisa hamle dizisine sahip olmasi gerekmektedir Boylece Tanri nin algoritmasi bu tur bir bulmacayi olabilecek en iyi cozumle sonuclandiran algoritma olarak tanimlanabilir Bir algoritmanin Tanri nin algoritmasi olarak degerlendirilebilmesi icin uygulanabilir olmasi gerekmektedir Bu algoritmanin asiri kaynak bellek alani ya da zaman tuketmemesi anlamini tasimaktadir Ornegin cok buyuk bir basvuru cizelgesi kullanilarak cozume cok kisa surede ulasilabilir ancak bu yontem olaganustu miktarda bellek alanina gerek duymaktadir Tam cozume ulasmaya calismaktansa bir durumdan son durum olmamak kosuluyla baslayip yalnizca tek hamle herhangi bir ideal cozumun ilk hamlesi olmak kosuluyla yapmak uzerine de odaklanilabilir Tek bir hamle icin dogru sonucu ureten bu algoritma ozyineleme yoluyla ilk problemin cozumunu bulan algoritmaya evrilebilmektedir Buna benzer bicimde tam cozum icin uretilen algoritma da urettigi sonucun geri kalani atilarak yalnizca bir hamle bulacak bicime donusturulebilir Ornekler15 bulmacanin genellenmis surumu olan ideal cozumunu bulmanin NP zor oldugu bilinmektedir Bu problem icin uygulanabilir bir Tanri nin algoritmasi bulunup bulunmadigi ise belli degildir Hanoi kuleleri bulmacasi icin ise her disk sayisi icin bir Tanri nin algoritmasi bulunmaktadir Rubik Kupu icin ideal cozum yontemi ilk kez 1997 yilinda tarafindan ortaya atilmistir En kotu durum icin 20 hamlede cozume ulasilabilecegi 1995 ten bu yana bilinmesine karsin 2010 yilinda gerceklestirilen deneyler sonucunda 20 hamlenin her durum icin ust sinir olusturdugu kanitlanmistir Bu sayi Tanrinin sayisi olarak adlandirilmaktadir Ayrica bakinizKahinli Turing makinesiNotlar Daniel Ratner Manfred K Warmuth 1986 Finding a shortest solution for the N N extension of the 15 puzzle is intractable 9 Mart 2012 tarihinde Wayback Machine sitesinde Proceedings AAAI 86 Ulusal Yapay Zeka Konferansi 1986 s 168 172 Carlos Rueda 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 God s Number is 20 21 Temmuz 2013 tarihinde Wayback Machine sitesinde Cube20 org Jonathan Fildes 11 Agustos 2010 Rubik s Cube quest for speedy solution comes to an end BBC News 25 Agustos 2010 tarihinde kaynagindan Erisim tarihi 25 Agustos 2010 KaynakcaDavid Joyner 2002 Adventures in Group Theory Johns Hopkins University Press ISBN 0 8018 6947 1