Project Euler-81-İki Yönü kullanarak en az toplamın bulunması

Question

$\left[\begin{array}131&673&234&103&18\\201&96&342&965&150\\630&803&746&422&111\\537&699&497&121&956\\805&732&524&37&331\end{array}\right]$

Yukarıdaki örnekte 5x5 matriste, en üst sol köşeden başlayan en alt sağ köşede biten en kısa  yolu soruyor, bu işlem yapılırken sadece bir birim sağa ve alt alta hareket edilebilir.

Soruda ise, 80X80 boyutunda bir matris verilerek en az toplamın bulunması isteniyor. 

Bu sorunun çözümü, bir graf nasıl oluşturulur ve bu grafta en kısa yol algoritması nasıl uygulanır konularını içerdiğinden, Bilgisayar Bilimleri ile ilgili... En kısa yol algoritması Dijskstra'nın bulduğu bir algoritmadır.

5x5'lik matriste Depth-Search yapmak belki de en basit çözüm, ancak 80x80'lik 6400 düğümün olduğu bir grafta, bu oldukça berbat bir yöntem. Düğümler arasında bir ilişki yoksa, yani aralarındaki mesafe sonsuz ise, boş yere alan tutuluyor. Ağırlık matrisi kullanma durumunda çünkü 6400x6400'lük bir matris gerekiyor. 

O yüzden, linkli listeler veya bağlı listeler daha Türkçe bir ifadeyle en iyi yöntem. 

Python gibi bir dilde bile, orjinal sorunun çözümü Dijkstra algoritması ile 10 sn'nin altında. Bunu takip eden, iki soru için de aynı yöntem uygulanır, sadece graflar farklı bir biçimde oluşturulur.

Bu soru, graf nasıl oluşturulur ve bu grafta en kısa yol nasıl bulunur sorusu için en ideal sorulardan biri. 

Bu linkte, https://projecteuler.net/problem=81 ve takip eden iki soru da bunun devamında.

Graf oluşturulurken, ağırlık matrisi kullanmak yerine, eğer linkli liste kullanılırsa, $O(N2$)'lik karmaşıklık, $O(a*LogN)$ seviyesine indirilir. Dileyen bu iki yöntemi ayrı ayrı uygular ve aradaki farkı görür. 

Bilgisayar Bilimleri ile ilgisi, 1- Graflar 2- En Kısa Yol Algoritması 3-Linkli Listeler

Comments

Dinamik programlama ya da memoization da kullanılarak çözülebilir.

Hatta EXCEL kullanmayı bilenler bu sorunun cevabını  program yazmadan da bulabilir.

Sorunun yanıtı 427337.  

---

http://matkafasi.com/105310/kup-yolculugu-depth-search

O zaman siz bunu da çözersiniz, bu daha kolay bir soru, ancak çözümü veya yanıtı Google'da yok, bir ben paylaşmıştım yarışma bittikten sonra...

Answer 1

Söz konusu algoritmanın uygulanması için, ağırlık matrisi "weight" adında yukarıdaki şekilde oluşturulur. "Infinity" adlı bir değişkene ihtiyaç var, o yüzden çok büyük değer atanmıştır. Graftaki maksimum düğüm sayısı adlı bir değişen daha var...

 

Üstteki kod ise, söz konusu algoritmanın uygulanmasıdır. "used" adlı diziyle o düğüm daha önce kullanılmış mı ona bakılıyor. Graf demek, matris demek. Daha etkin olan (efficient) bir çözüm daha var, "Linkli liste ile çözüm", bu durumda ağırlık matrisi diye bir şey söz konusu değil, böylece boşuna yer tutulmuyor. 

Comments

import time

time1=time.time()

INFINITY=pow(10,10)

DIMENSION=80

DIMENSIONONEMINUS=DIMENSION-1

MAXNODES=DIMENSION**2

weight=[[INFINITY for a in range(MAXNODES)]for b in range(MAXNODES)]

'''

Bu araya matris okuma işlemi yapılmalı, matris dosyasını maalesef burada okutamıyorum,

8000 karakter sorunu var... matrice değişkeni cevap bölümündeki resimde de görülüyor, 

içi öyle olacak, aksi halde çalışmaz bu kod...

'''

def CreateWeightMatrix():

    for i in range(DIMENSIONONEMINUS):

        for j in range(DIMENSIONONEMINUS):

            snode=(i*DIMENSION)+j

            row,col=i+1,j+1

            e1node,e2node=DIMENSION*i+col,DIMENSION*row+j

            weight[snode][e1node]=matrice[i][col]

            weight[snode][e2node]=matrice[row][j]

            #print("i=",i,"j=",j,"start node=",snode,"end node=",e1node,"same row=",i,"next col=",col,matrice[i][col])

            #print("i=",i,"j=",j,"start node=",snode,"end node=",e2node,"next row=",row,"same col=",j,matrice[row][j])

    

    i=DIMENSIONONEMINUS

    for j in range(DIMENSIONONEMINUS):

        snode=(i*DIMENSION)+j

        enode=snode+1

        weight[snode][enode]=matrice[i][j+1]

        

       

    j=DIMENSIONONEMINUS

    for i in range(DIMENSIONONEMINUS):

        snode=(i*DIMENSION)+j

        enode=snode+DIMENSION

        weight[snode][enode]=matrice[i+1][j]

CreateWeightMatrix()

#print(weight)

distance=[INFINITY]*MAXNODES

distance[0]=0

FINALNODE=MAXNODES-1

def Solve():

    used=[0]*MAXNODES

    s=0

    used[s],distance[s],current=1,0,s

    while current!=(FINALNODE):

        #print("current=",current)

        smalldist=INFINITY

        distancecurrent=distance[current]

        for i in range(MAXNODES):

            if used[i]!=1:

                newdistance=distancecurrent+weight[current][i]

                

                if newdistance<distance[i]:

                    distance[i]=newdistance

            

                if distance[i]<smalldist:

                    smalldist=distance[i]

                    #print("smalldist=",smalldist)

                    k=i

        current=k

        used[current]=1

        

        

    #print(distance)

    #print(current)

    

    #print(used)

        

print("Starting Part=")

Solve()

print("Answer is=",distance[FINALNODE]+matrice[0][0])

print(time.time()-time1)