‹ Sorduğum Sorular › ‹ Takip Ettiğim Sorular › ‹ Verdiğim Cevaplar › ‹ Arşivimdeki Sorular › ‹ İlgilendiğim Alanlardaki Sorular ›
Kodları lütfen aşağıdaki butonları kullanarak renklendirin. Örnek: <php> echo "Selam Dünya"; </php>
Soruyu takip et
karakter kaldı
merter
0 cevap – 1 soru
Profili | Mesaj At | Takip Et
Tweet
Kategoriler
PHP Python Java .NET SQL Delphi
İstatistikler
10 yıl önce yazılmış
10 yıl önce güncellenmiş
122 üye izlemiş
1 cevap verilmiş
Kare Bulmaca Algoritması
Merhabalar.
2 boyutlu harf matrisinde boş olarak verilmiş bir kare bulmacayı, sözlükteki kelimeler ile doldurmak istiyorum. Backtrack ve bruteforce yöntemlerini denedim fakat farklı bir yaklaşım gerekiyor. Bu problemin çözümü için optimum yaklaşım nasıl olmalı?
Örnek matris ektedir.
Not: Önce matris ve siyah noktalar belirleniyor, daha sonra yaklaşık 400.000 kelime barındıran sözlükten uygun kelimeler alınarak bulmaca doldurulmalı.
Ekli Dosyalar
Kelimeleri yatay ve dikey okutup, uygun kelimeleri ( MySQL ile "... like 'k_l_me' " veya "regexp '^k.l.me$' " tarzı sorgular ile ) arama yaptırıp kelimeleri çekiyorum.
— merter 10 yıl önce yazdı
o 400.000 kelimelik sözlüğü nerden bulabilirim? bana lazım öyle bişey.
— guest 9 yıl önce yazdı
+2
-0
Cevaplar
10 yıl önce yazılmış
cgelis
10 cevap - 0 soru
cevapları kelime uzunluğuna göre mi yerleştiriyorsunuz ?
merter
Sorunuzu tam anlamadım ama biraz daha açıklayayım. Yukarıdaki bulmaca örneğini 2 boyutlu char matrisi olarak modelledim. Siyah noktalar da belirtilmiş şekilde. Bu hazır kalıba kelimeleri yerleştirmek istiyorum.
Önce kelimeleri yazıp sonra noktaları koyarak yapMıyorum. Önce siyah noktalar, sonra kelimeler yerleştirilecek.
Amacım sadece yukarıdaki matrise sözlükteki kelimeleri yerleştirmek, bunun için yaklaşım & mantık arıyorum.
Sözlük yaklaşık 400.000 kelime barındırıyor.
10 yıl önce yazılmış
cgelis
yapmak istediğiniz tam olarak 400.000 kelime içerisinden bulmacayı dolduracak en uygun kelimeleri bulmak mıdır? Doğru mu anlamışım?
10 yıl önce yazılmış
merter
Evet aynen öyle. 400.000 kelime içinden kelimeleri seçip bu matrisi doldurmak istiyorum. Bu sözlükteki kelimeler 15 harfli kelimelere kadar kayıt barındırıyor.
10 yıl önce yazılmış
cgelis
anlatacağım yöntemle biraz memory'e yüklenmen gerekecek. ancak seni çokta sıkıntıya sokmaz diye düşünüyorum. öncelikle 400.000 kelimen var bunların hepsini memory'e attığımızı düşünelim. hepsi 15 harf olsa (en kötü ihtimal) ve her karakter 1 byte olduğu için 400.000 * 15 = 6.000.000 byte'a ihtiyacın olacak yani yaklaşık 5 mb. (pekte kötü değil). kelimelerin maximum 15 harf olduğu için 15 boyutlu bir Binary Search Tree türünde bir array açman gerekecek. Binary Search Tree'imiz alfabetik sıraya göre olacak.
BST kelimeler[15];
daha sonra kelimeleri bu arrayın içerisine atacağız.
mesela 4 harfli kelimeler kelimeler[4] kısmına 15 harfliler kelimeler[15] kısmına. daha sonra bulmacada gezerken mesela 10 harfli bir alana geldiğinde kelimeler[10] kısmındaki BST'de aramaya başlayacak. tabi 10 harfli dışındaki kelimeleri elediğin için birde içeride arama yaparken BST kullandığın için inanılmaz bir performans artışın olacak. Bu verdiğim yöntem dışında şu an için daha iyi bir seçenek aklıma gelmedi. birde Treelerini oluştururken AVL Tree kullanırsan performansını daha üst seviyelere çıkartmış olursun.
Kolay gelsin.
10 yıl önce yazılmış
siyahbeyaz
cgelis. cok mantıklı. gercekten. binary sistemi ve array olayı cok iyi. yükünü hafifletir. ama sole birsey var
S a
a h m e t
l m
i e
h t
yukardan asagı salih yaptık soldan saga ahmet yaptık yukardan asagı ahmet yaptık tekrar. soldan saga 3.satır ve dıger satırlar alakasız oldu. buraları seni epey yoracaktır.
10 yıl önce yazılmış
merter
Kelime ararken pek sıkıntım olmuyor, MySql ile sorguları uyarlayarak kelimeleri bulabiliyorum. (like veya regexp kullanıyorum). Ancak örneğin 20 kelime yerleştirdikten sonra 21. kelime bulunmuyor bu sözlükte, backtrack ile geri gidip önceki kelimeleri değiştirsem de bir noktada takılıyor, belli bir noktada kombinasyonu sağlayan kelime bulunmayabiliyor. Sanki ileriyi görebilen veya sezgisel birşeylere ihtiyacım var gibi.. Cevabınız için teşekkür ederim, ağaç aramayı araştıracağım.
10 yıl önce yazılmış
siyahbeyaz
kelimenın yerlestirecegi kutucuk sayısı elınde olsa kontrolerin dahada saglamlasa bilir int olayı. ama su array olayı senı kurtarır gıbıme geldi.
10 yıl önce yazılmış
merter
Kelime arayıp bulmak konusunda sıkıntım yok, onu hızlandırabilirim de cgelis'in dediği gibi. Sıkıntı işlemlerin ilerlediği durumlarda ,işlem yaptığı yere kelime bulamamasında. Kelimeleri tek tek diziye çıkartıp Backtrack ile uygun kelimeleri bulup yerleştirmeye çalıştım ancak çok uzun sürüyor öyle.
10 yıl önce yazılmış
cgelis
Problem sudoku problemini andırdı bana. Görünüşe göre backtrackingten başka çare yok ama bu konuda uzun süre düşünmek gerekiyor, biraz araştırma yapmakta fayda var. Sudoku problemleri ile ilgili araştırma yapmanızı öneririm. Sanırım onlarında birçoğu backtracking ve bruteforce ile çalışıyor. Birşeyler bulduğumda tekrar cevap yazarım.
10 yıl önce yazılmış
merter
Sudoku problemini Backtrack ile çok önceden çözdüm zaten. (http://merterhami.com/sudoku.php) Kare bulmaca ile 1-2 yıldır uğraşıyorum. Harf harf veya kelime kelime backtrack denedim ancak sonuç alamadım işlem süresi çok uzuyor. Bu aralar brutefoce gibi kelimeleri yazıp değiştirmeye uğraşıyorum ama içime sinmiyor öyle de. Çok dallanıyor.
10 yıl önce yazılmış
cgelis
Birde backtracking yaparken direk veritabanı üzerinden yaparsanız çok zaman kaybınız olur. Verdiğim algoritma üzerinden backtracking yapmanızı öneririm. Kaldığınız yerlerin pointerlarını elinizde tutarsanız bir geriye gitmek için zaman kaybetmemiş olursunuz. Şu an için en etkili yöntem bu gözüküyor. Tek yapmanız gereken tüm veritabanını anlattığım veri yapılarına inşa etmek. Kaldığınız yerleride ayrı bir yerde tutarsanız probleminizin çok hızlı çözüleceğini düşünüyorum.