Tamahkar axtarışın alqoritmasinin "Yol Məsələsinə" tətbiqi

tamahkar_alqo

"""
    Tamahkar Alqoritma ilə yol məsələsini həll edək. 
    
    - Qarşıda 2 üsul var:
        1. Node-lar open node listine gore secilir, yuksek heuristici olan secilir.
        2. Node-lar ancaq qarsidaki yola gore secilir, meselen bu misalda, elaqesi olmayan node-a kecmek mumken deyil 
            - Məs., E-dən D-yə keçmək olmaz, çünki yol yoxdur-qonşuluq yoxdur).
"""

import concurrent.futures
import time
import sys




class TamahkarAxtaris:
    """
        Seçilmiş 2.ci həll üsulu ilə Tamahkar Alqoritmanın yol məsələsinə tətbiq olunması.
        
        Bəzi atributların mənası:        
            duyum: düyüm, yəni node deməkdir
            serfiyyat: tapılan tam yolun başlanğıcdan hədəfə qədərki həqiqi məsafəsi (metrlər)
    """

    def __init__(self):
        self.baslangic_duyum='A'
        self.hedef_duyum='H'

        self.butun_duyumler=['B', 'C', 'E', 'D', 'I', 'K', 'M', 'S', 'Z', 'N', 'L', 'G', 'P', 'Y']
        self.aciq_duyumler=[] # bu məsələdə işlədilməyəcək
        self.bagli_duyumler=[]

        self.secilmis_yol=[]
        self.serfiyyat=None
        
        self.heuristic_mesafeler = {
            "A":542,
            "B": 510,
            # "B": 470,
            "C":490,
            "E": 304,
            "D": 323,
            "I":269,
            "K": 270,
            "M": 276,
            "S":163,
            "Z":134,
            "N":136,
            "L": 95,
            "G":94,
            "P": 72,
            "Y":75,
            "H":0
        }

        self.qonşu_duyumler = {
            "A": ["B", "C"],
            "B": ["A", "E"],
            "C": ["A", "D"],
            "E": ["B", "K", "M"],
            "D": ["C", "K", "I"],
            "I": ["D"],
            "K": ["D", "E", "Z"],
            "M": ["E", "S"],
            "N": ["S", "L"],
            "S": ["M", "N"],
            "Z": ["K", "G", "L"],
            "G": ["Z", "P"],
            "L": ["N", "Z", "P", "Y"],
            "Y": ["L", "H"],
            "P": ["L", "G", "H"]
        }

        self.qonsu_duyumArasi_mesafeler = {
            ('A','B'): 50,
            ('B','E'): 215,
            ('E','K'): 40,
            ('E','M'): 33,
            ('M','S'): 148,
            ('S','N'): 40,
            ('N','L'): 48,
            ('L','P'): 25,
            ('L','Y'): 40,
            ('Y','H'): 77,
            ('A','C'): 47,
            ('C','D'): 183,
            ('D','K'): 59,
            ('D', 'I'):30,
            ('K','Z'): 166,
            ('Z','L'): 41,
            ('Z','G'): 55,
            ('G','P'): 20,
            ('P','H'): 75,
            }



    def axtaris_muherriki(self, emeliyyat_novu=""):
        """ Özəlləşdirilmiş "Tamahkar Axtarış" alqoritması """
        cari_duyum=None
        ust_duyum_tarixi={} #dict of tuples #current parent node is chosen before going to the child node
        ust_duyum=None
        heuristic_uygun_duyum=None # qisa mesafe uygundur
        heuristic_uygun_duyum_mesafesi=None
        qonsular_arasi_mesafe=None
        uste_qalx=False

        while True:
            if not self.bagli_duyumler: #hele baslamayib
                print(f'Başlanğıc düyüm: {self.baslangic_duyum}')
                cari_duyum = self.baslangic_duyum

            if cari_duyum == self.hedef_duyum:
                self.sonlandir("Uğurlu axtarış")
                return True

            ### QONSU DUYUMLERI TAP
            qonsu_duyumler = self.qonşu_duyumler[cari_duyum]
            while True:
                if uste_qalx:
                    ust_duyum = ust_duyum_tarixi[cari_duyum][-1]
                    self.secilmis_yol.remove(cari_duyum) # izlenen yoldan cari duyumu cix
                    self.serfiyyat -= qonsular_arasi_mesafe
                    cari_duyum = ust_duyum # bir addim geri get
                    qonsu_duyumler = self.qonşu_duyumler[cari_duyum]

                qonsu_duyumlerin_hamisi_baglidir = all(duyum in self.bagli_duyumler for duyum in qonsu_duyumler)
                print("Bütün qonşu düyümlər", qonsu_duyumler)

                if ust_duyum == self.baslangic_duyum and qonsu_duyumlerin_hamisi_baglidir:
                    self.sonlandir("Bütün yollar qapalıdır. Hədəfə çatmaq mümkün olmadı.")
                    return False
                elif len(qonsu_duyumler) == 1 and qonsu_duyumler[0]==ust_duyum_tarixi[cari_duyum][-1]:
                    print("Yolun çıxışı yoxdur! Üstə qalxırıq")
                    if cari_duyum not in self.bagli_duyumler:
                        self.bagli_duyumler += cari_duyum
                    uste_qalx = True
                    continue #sifirla - eger yolun cixisi yoxdursa, geri don (qapali yol)
                elif qonsu_duyumlerin_hamisi_baglidir:
                    print("Qonşu düyümlərin hamısı bağlıdır! Üstə qalx...")
                    uste_qalx = True
                    continue #sifirla - aciq qonsu duyum yoxdur, bir uste qalx - enter while loop again
                elif qonsu_duyumler:
                    # print(f'Qonşu düyümlərdən açıq olanı var.')
                    uste_qalx = False
                    break
            ### ACIQ QONSU DUYUM VAR

            ### HEURISTIC UYGUN QONSU DUYUMU TAP  
            heuristic_uygun_duyum = None
            for duyum in qonsu_duyumler:
                if duyum in self.bagli_duyumler:
                    print(f'Bağlı düyüm: {duyum}')
                    continue
                heuristic_duyum_mesafesi = self.heuristic_mesafeler[duyum]
                if not heuristic_uygun_duyum or heuristic_uygun_duyum_mesafesi > heuristic_duyum_mesafesi:
                    heuristic_uygun_duyum = duyum
                    heuristic_uygun_duyum_mesafesi = heuristic_duyum_mesafesi
            
            print(f'Heuristic uyğun düyüm: {heuristic_uygun_duyum} | Heuristic məsafə: {heuristic_duyum_mesafesi} metr\n')
            if cari_duyum not in self.bagli_duyumler:
                self.bagli_duyumler += cari_duyum # cari duyumu bagli duyumlere at
            self.secilmis_yol += heuristic_uygun_duyum
            qonsular_arasi_mesafe = self.qonsu_duyumArasi_mesafeler[(cari_duyum, heuristic_uygun_duyum)]
            
            if not self.serfiyyat:
                self.serfiyyat = qonsular_arasi_mesafe 
            else:
                self.serfiyyat += qonsular_arasi_mesafe 

            if heuristic_uygun_duyum not in ust_duyum_tarixi.keys():
                ust_duyum_tarixi[heuristic_uygun_duyum] = [cari_duyum]
            else:
                ust_duyum_tarixi[heuristic_uygun_duyum] += cari_duyum
            
            cari_duyum = heuristic_uygun_duyum #cari duyumu novbeti heuristic uygun qonsuya teyin et
            print(f'Cari düyüm: {cari_duyum} | Sərfiyyat: {self.serfiyyat} metr')
            ### HEURISTIC UYGUN QONSU DUYUM TAPILDI

        return False



    def sonlandir(self, mezmun=None):
        """ Xüsusiləşdirilmiş sonlandırma; Sıradan və ya məcburi """
        if mezmun=="Uğurlu axtarış":
            print(f'Hədəf tapıldı!\n====\n\nSeçilmiş yol: {self.baslangic_duyum} -> {self.secilmis_yol}\nSərfiyyat/həqiqi məsafə: {self.serfiyyat} m.\n')
        else:
            print(f'\n {mezmun} \n')
            # sys.exit()



    def axtar(self):
        """ Çoxnüvəli (multicore) axtarış. """
        with concurrent.futures.ProcessPoolExecutor() as executor:
            f1=executor.submit(self.axtaris_muherriki, "capEt")
            print(f'Nəticə: {"tapıldı" if f1.result() else "tapılmadı"}')



""" Çoxnüvəli prosesi çalışdır """
if __name__ == '__main__':
    Axtaris_alqoritmi = TamahkarAxtaris()

    baslangic_zamani = time.perf_counter()
    Axtaris_alqoritmi.axtar()
    bitis_zamani = time.perf_counter()

    print(f'Keçən zaman: {bitis_zamani-baslangic_zamani} saniyə\n')