Küp Yolculuğu- Depth Search

Question

İki küp birbirine bağlanmış şekilde görüldüğü gibi, A noktasından başlayan hareket B noktası ile son buluyor, yolculuk A noktasında başlayıp ve B noktasında bitiyor, B köşesi dışında diğer tüm köşelerden birden fazla geçilebilir, kenarlardan ise birden fazla geçilemez. Bu yolculuk kaç biçimde yapılabilir? 

Search nasıl yapılır, Bilgisayar Bilimleri ilişkisi, Depth Search nasıl kullanılır, nedir? Bir diğer ilişki graflar nasıl oluşturulur, bunu da gösteren bir soru. Recursive olarak program nasıl yazılır? Data Structures dersi ile verilen konuların en az üçünü kapsamaktadır, soruyu soran kişi büyük olasılıkla bunları düşünerek sormuş...

Bence, eğlenceli bir soru. 

Comments

Bilgisayar açısından durumun nasıl halledileceğini bilmiyorum.

 Ama permütasyon açısından;bu iki küpün birleştiği noktayı $C$ ile gösterelim. Her kenardan yalnız bir defa geçilebilmesi koşulu, dikkate alınırsa ard arda en fazla üç yatay kenardan geçebilir. Dolayısıyla $A$ dan başlayan bir kişi önce mutlaka $C$ 'ye ve sonra $B$ noktasına ulaşacağına göre istenilen yol sayısı $A$ 'dan $C$ 'ye ulaşma sayısının karesi kadar olmalıdır.

---

Kenarlardan bir kereden fazla geçemezsiniz diyor soruda, her kenardan geçme şartı gibi bir bilgi yok.

---

Benim için önemli olan sorular bu tarz sorulardır, soru kendi disiplinimle nasıl bir uyum içindedir, ne uygulanabilir; "Tak çalıştır" değildir, örneğin, bir sayının faktörlerinin bulunması için gereken algoritma bellidir, koyarsın sayıyı programa (programcık) sonucu verir. Faktörleri bulan en hızlı algoritma hep aynıdır, pek değişmez. Bir şey keşfedersin, daha hızlı bir algoritma keşfedersin, o başka...

Bir soruyu, faktörleri bulan algoritmaya dönüştürürsün, o da başka.

Yukarıdaki soruda, neyi nereye koyacağız? 

---

ben mi yaniliyorum yoksa bu yolculuk bu sekliyle sonsuz farkli sekilde yapilabilir mi ? sonucta A nin bulundugu kupte bir yuzde donmemi engelleyen bir kural yok

---

Kenarlardan bir kereden fazla geçemezsiniz kısıtı var. Köşelerden de birden fazla B dışında geçebilirsiniz. Sonlu sayıda bir yanıtı var. Burada yazmış mıydım yanıtını bakmadım, hayli zaman geçmiş Yanıt 1908 olacak.

Buna benzer bir soru da şu şekildedir, yine aynı mantıkla çözülebilir.

https://saracogluahmet.wordpress.com/2020/11/06/puzzleup-2020-1/

Answer 1

Üstteki bu kod ile çabucak çözüme ulaşılır. Kod, recursive(kendi kendi çağıran) tarzda yazılmış bir koddur, "recursive" olarak yazmak istemeyen "stack" mantığını kullanarak da recursive simülasyonu yapabilir. 

Recursive fonksiyonlar yazılırken dikkat edilmesi gereken, durma noktasının tayin edilmesidir. Burada durma noktası, newvertice=14'tür. Yani, bu değer 14 olmadıkça fonksiyon tekrar tekrar çağrılır. Recursive fonksiyonlarda eğer durma noktası gözden kaçarsa, "stack overflow" durumu oluşur. 

Diğer bir husus, "backtracking" durumudur.  Bu da son iki satırdaki pop() fonksiyonlarıyla yapılmış. Backtracking (Geriye yönelim) geri adım atmak demektir. 

Recursive program yazmak isteyenlere en güzel uygulama, "labirent sorusu" olabilir,"mouse trapping" de derler. NXM şeklinde bir labirent vardır, kimi yollar kapalıdır, bir giriş ve bir çıkış vardır, -istenirse bu da değiştirilebilir- yolun bulunması istenir.

Labirent sorusu, "Data Structures" adlı dersin bir vize sınavında sorulmuş bir sorudur bu arada...

Daha basit örnekler, "Fibonacci", "Towes of Hanoi", "Faktöriyel hesaplama" yine recursive program tadında yazılabilir.

Recursive programlar aslında tree(ağaç)'yi "Depth Search" ile yöntemi ile ararlar. Bu yöntem, ağacı derinlemesine tarar. Breadth Search gibi, seviye seviye gitmez, bir başlar kökten, en alt çocuğa kadar arama yapar, sonra yukarı tırmanır, tekrar en alta kadar gider, tekrar tekrar bu işlem devam eder, ta ki istenilen şart sağlanana kadar.

Ağaç nedir? Ağaçta, bir kök vardır, ana-baba diyelim, bir de bunların sol çocuğu ve sağ çocuğu olmak üzere dalları vardır. İkili ağaçlar da (binary)var, çoklu ağaçlar (ternary) da var. 

 

Yukarıdaki ifade de ise düğümler tutulmaktadır, hangi düğüm hangi düğümle ilişkili. Python'da bu işler daha basit. 

Check() fonksiyonu ise, kenarların daha önce eklenip eklenmediğini kontrol eden bir fonksiyon. 

Soru, katılımcıların olduğu dönemde, biraz zor olarak belirlenmiş, sorunun bence tek zorluğu, küplerin düğümleri numaralandırırken yaşandı benim tarafımdan.

count değişkeni de işlemi sayıyor. 

Comments

import time

time1=time.time()

nodes=[(1,2,4),(0,3,5),(0,3,6),(1,2,7),

       (0,5,6),(1,4,7),(2,4,7),

       (3,5,6,8,9,11),(7,10,12),

       (7,10,13),(8,9,14),(7,12,13),

       (8,11,14),(9,11,14)]

 

 

edges,vertices,count=[],[0],0

 

 

def Check(t,eds):

     

    if (t) in edges:

        return False

    Len=len(eds)

    for i in range(Len-1):

        e1=eds[i]

        for j in range(i+1,Len):

            if e1==eds[j]:

                return False

             

         

     

    return True

 

alledges=[[] for i in range(1908)]#This size is because I have already found the answer.

def Solve(vertice):

    global count

    for j in range(len(nodes[vertice])):

        newvertice=nodes[vertice][j]

        t1,t2=(vertice,newvertice),(newvertice,vertice)

        edges.append(t1)

        vertices.append(newvertice)

        #print("edges=",edges,j,newvertice)

        if newvertice!=14 and Check(t2,edges):

            #print("vertice=",vertice)

            Solve(newvertice)

        elif newvertice==14:

             

            #for i in range(len(edges)):

                #alledges[count].append(edges[i])

            #print("edges=",edges)

            #print(vertices)

            count+=1

       # print("Backtrack before=",edges)

        edges.pop()

        vertices.pop()

        #print("Backtrack after=",edges)

 

Solve(0)

print("count=",count)

print((time.time()-time1)*1000)

Koddaki $alledges$ adlı dizi, kenarları tutan bir dizidir, çok da gerekli de değildir sorunun çözümünde, ancak hangi kenarlardan geçtiğini görmek için gereklidir. Comment olarak görünen print satırları açılarak kod denenebilir.