Forum
Aktif konular
Üyeler
Kurallar
Arama
Oyalanacak İş Arayanlara - Algoritma Sorusu Oyalanacak İş Arayanlara - Algoritma Sorusu
-
Şu aşağıdaki iki örnek gibi, herhangi bi şekilde başlangıç konumu verilen tabloyu
8 7 1 3 4 6 5 2 8 2 6 3 4 7 5 1 şu hale getirebilecek algoritma, C, C++, C#, Java, Php, Pascal, Python vs herhangi bir dildeki kodu ya da çözüm üretecek herhangi bir şeyler.
1 2 3 8 4 7 6 5 Ben biraz uğraştım yemedi, belki ilginizi çeker. Amaç soru sormak falan da değil, öyle esti paylaşayım dedim. İlgilenip çözen olursa biz de birkaç şey öğrenmiş oluruz belki.
Buna benzer oyunları görmüşsünüzdür zaten. Kurallar basit, bi tane boşluk var, rakamlar sağa, sola, yukarı ya da aşağı kayarak son hale dönüşmek isteyecekler. Ya da herkes istediği şartları yazsın, kendi kuralını oluştursun.
-
yeni halinin tek özelliği sarmal olarak 1den 8e gitmesimi?
-
Bu örnek için öyle, ama sen istediğin başka türlü şartlar da ekleyebilirsin.
-
başla
matrisin boyutunu oku (M (X , Y) )
matris kümesini oku
matris kümesini büyükten küçüğe sırala A s dizisine yükle
S=1
U=1 V=1
10 i=1 j=1
15 S x*y den büyük mü E -> "matris tamam" bitir
20 M(ij) ye As yi ata
40 i+1 X den büyük mü
H-> j= j+v ( yan sütuma geç ) 15e git
E -> i=i+u ( alt satıra geç) j=Y s= s+1 15e git
( mesai ibitti evde devam ederim )
-
Bu konuda http://www.tahribat.com/forumdisplayfolder.asp?folderid=80854 yazmış olduğum cevap.
Tek fark manhattan mesafe'lerin farklı şekilde hesaplanması.
-------------Selam,
Bu puzzle'ın optimal çözümüne o kadar da ağır olmayan bir heuristic ile ulaşılabilir. A* (astar) search algoritmasını (http://www.autonlab.org/tutorials/astar08.pdf) duymuşsunuzdur.Çözümümüzde tam anlamıyla bu search algoritmasını kullanacağız.
Bu algoritmayı kullanlanırken h değerini (yani puzzle'ın bir pozisyondaki önem değerini), her tuşun bu pozisyondaki yeri ile olması gereken yerinin arasındaki Manhattan mesafesinin (http://www.improvedoutcomes.com/docs/WebSiteDocs/Clustering/Clustering_Parameters/Manhattan_Distance_Metric.htm) mutlak degerlerinin toplayarak bulacağız.
Verilen bir puzzle'da öncelikle ilk pozisyon için h değerini buluyoruz ve priority queue denilen yapıya bu pozisyonu değeriyle beraber koyuyoruz. Sonra bu pozisyondan üretilebilecek pozisyonlar için aynı şekilde h hesaplamalarını yapıyoruz ve priority queue'ya koyuyoruz. Bundan sonraki adımlar bir loop'un içinde geçecek, puzzle'ın olması gerektiği pozisyona ulaşınca bu loop'tan çıkacağız.
Loop'umuz başladı.
Priority queue'dan en küçük h değerli pozisyonu çekiyoruz.
Eğer pozisyon orjinal puzzle posizyonuysa tamamdır sonuca ulaştık.
Değilse, pozisyondan üretilebilecek pozisyonları buluyoruz, h hesaplamalarını yapıyoruz ve priority queue'ya koyuyoruz.
Loop'un başına dönüyoruz.
NOT: Priority queue'ya koyarken aynı pozisyonları koymamaya dikkat edilmeli. Üsünde geçilmiş pozisyonların bir listesini array yapısında tutabilirsiniz.
NOT: Pozisyonları oluştururken, parent pozisyonlarını unutmamak gerekiyor. Bunu da bir pointerla halledebilirsiniz.
Bu greedy heuristic olup da optimal sonuca götüren bir çözümdür.
------------- -
Algoritmanın püf noktası başlangıç adresinden sonra başlngıc yönünde bir sonraki hücreye eleman yerleştirilip yerleştirilemeyeceği (matris sınırları aşılıyor mu yoksa yan hücreye daha örce veri ğirilmiş mi?) ve buna bağlı yön değişim kararı prosedürü. ve yerleştirecek eleman kalıp kalmadığı
Öncelikle matrise yerleştirilecek dizi küçükten büyüğe sıralanır, boş hücreler için 0 lar dizi sonuna atılır.
ilk olarak elemanı yerleştirdikten sonra, dizide eleman kaldığı sorgulunır
Diğer bir husus da yazmaçın yatay ve düşey doğrultuda yön vektörlerinin tesbiti
yatay hareket vektörü U düşey hreket vekkörü V +/-1 değerlidir ki yazmaça hreket vektörü doğrultusunda bir birim ilerle dediğimizde indisler üzerinde ileri geri aşağı yukarı hareket edebilelim.( her kdoğrultu değiştiğinde mevcut doğrultuda hareket yönü terslenir yatayda sağa gderken köşe dönünce ikinci köşede sola gitmek zorunda)
aşağıdaki program önerisinde başlangıç nokası 1,1 pozitif hareket yönler sağ ve aşağı olarak var sayılmaka birlikte dış girdi olarak da alınabilir sistemi değiştirmez 450-470
Hücrelelere daha önce elelman atamasının kontrolü için D(,) gölge/duvar mattrisi oluşturdum eleman yerleşen hücreye 1 atadım ki kaynak dizinin sıfırları kafa karıştırmasın
temelde BASIC olmasına rağmen hemen her dilde olan basit komutlardır
50 input "matris sat˝r X " ; x
60 input " matris s¸tun say˝s˝ Y ": y
70 "eleman say˝s˝" ES=x*y
100 for b=1 to ES
200 input " matris elemanlar˝n˝ giriniz" e(b)
210 next
220 gosub ELEMAN SIRALA
230 "elemanlar başarıyla ˝ EL(en) dizisine atandı "
235 " duvar matris matris sıfırlanıyor
240 for i=1 to x
245 for j=1 to y
250 D(i,j)=0
255 next j
256 next j
450 u=1, v=1 ,i=1,j=1,**en=1 // s=1
ilk ELEMAN YERLEşTir460 T(1,1)=EL(1) D(1,1)=1
470 en=en+1
480 if en > ES then 899
490 yatay hareket deerlendirmesi
500 yhd = j+u*1>x or j+u*1<1 or D(i,j+u*1)
510 if yhd=1 u=-1*u : goto 650 (DHD )
520 j=j+u*1
530** T(i,j)=EL(en): en=en+1 // 530 T(i,j)=EL(en)
540** if en > ES then 899 //if en+1 > ES then 899
550 goto 490
650 Dikey hareket deerlendirmesi
660 dhd= i+v*1>y or i+v*1<1 or D(1+v*1,j)=1
670 if dhd=1 v=-1*v : goto 490 (YHD )
680 i=i+v*1
690** T(i,j)=EL(en) :en=en+1 //T(i,j)=EL(en)
695**if en > ES then 899 //
700 goto 650
899** matris yerleşti
900 end
düzeltme ve özür: mürit kardeşlerim kusurua bakmayın 15 yıldır ne algoritma ne program yazdım ** lı düzeltmeler yapılmalı ki sıradaki elemanın indisiyle çağrılabilsin // eski yanlış koddur
Kısayol
Şikayet
Özel Mesaj
Alıntı yap
Cevapla