Tam işlək Tamahkar Axtarış alqoritmi (yol məsələləri üçün)

TamahkarAxtarış_alqoritmi (tam)

"""
    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).
        3. Normal Greedy axtarış aparılsın, open node-lar işlədilsin; Hər open node-un heuristic məsafəsi yadda saxlanılsın.
            - Buna görə də node-swithcing algorithm işlədiyi müddətcə path-per-path aparılacaq. Cavab isə insan yeriyəbiləcəyi tam path olacaq. 
            - Seçilən node-un (switched) tam path-i qeyddə qalır.
"""

import concurrent.futures
import time
import sys



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

    def __init__(self):
        self.başlanğıc_düyüm='A'
        self.hədəf_düyümlər=['H']

        self.bütün_düyümlər=['A', 'B', 'C', 'E', 'D', 'I', 'K', 'M', 'S', 'Z', 'N', 'L', 'G', 'P', 'Y', 'H']
        self.açıq_düyümlər=[]
        self.bağlı_düyümlər=[]

        self.gəlinən_yol=[]
        self.bütün_yollar={} # dict of ID int with lists
        self.bütün_yollar_məsafəli={}
        self.hazırki_yol_ID=None
        self.sərfiyyat=None
        
        self.heuristic_məsafələr = {
            "A": 542,
            "B": 510,
            "C": 490,
            "E": 304,
            "D": 323,
            "I": 269,
            "K": 270,
            "M": 276,
            "S": 163,
            "Z": 234,
            "N": 136,
            "L": 95,
            "G": 94,
            "P": 72,
            "Y": 75,
            "H": 0
        }

        self.qonşu_düyümlər = {
            "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.qonşu_düyümArası_məsafələr = {
            ('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 axtarış_mühərriki(self, əməliyyat_növü=""):
        """ Özəlləşdirilmiş "Tamahkar Axtarış" alqoritması """
        cari_düyüm=None
        heuristic_uyğun_düyüm=None # qisa məsafə uygundur
        if not self.bağlı_düyümlər: #hele baslamayib
            print(f'\n-> Başlanğıc düyüm: {self.başlanğıc_düyüm}')
            cari_düyüm = self.başlanğıc_düyüm
            self.bağlı_düyümlər.append(self.başlanğıc_düyüm)
        
        while True:
            print("-- -- -- -- -- -- --\n")
            print(f'>> Cari düyüm: {cari_düyüm} | Sərfiyyat: {0 if self.sərfiyyat is None else self.sərfiyyat} metr')

            ### QONSU düyümLERI tap
            qonşu_düyümlər = self.qonşu_düyümlər[cari_düyüm]

            ### GENISLET VE ACIQ düyümLERI TAP
            genişlənmiş_düyümlər=[]
            for genişlənmiş_düyüm in qonşu_düyümlər:
                if genişlənmiş_düyüm not in self.bağlı_düyümlər and genişlənmiş_düyüm not in self.açıq_düyümlər:
                    self.açıq_düyümlər.append(genişlənmiş_düyüm) 
                    genişlənmiş_düyümlər.append(genişlənmiş_düyüm)
            
            self.açıq_düyümlər = self.açıq_düyümləri_sırala()

            if not self.açıq_düyümlər:
                self.sonlandır("Açıq Düyüm qalmadı! Bütün düyümlərə baxılıb. Hədəfə çatmaq mümkün olmadı.")
                return False

            print(f'--> [Sıralanmış] Açıq Düyümlər (heuristic məsafələrilə): {[{düyüm:self.heuristic_məsafələr[düyüm]} for düyüm in self.açıq_düyümlər]}')
            print(f'--> Bağlı Düyümlər: {self.bağlı_düyümlər}')

            ### Genislemeden sonra butun node-lari yol tarixine sal
            print(f'--> Bütün yollar və sərfiyyatı (metrlə): {self.bütün_yollar}')
            
            ## kohne izi axtar
            iz_tapıldı=False
            try:
                for value_list in self.bütün_yollar.values():
                    if value_list[0][-1]==cari_düyüm:
                        for key in self.bütün_yollar.keys():
                            if self.bütün_yollar[key][0][-1]==cari_düyüm:
                                self.hazırki_yol_ID=key
                                break
                        iz_tapıldı=True
                        break
            except IndexError:
                iz_tapıldı=False

            ## iz tapildi - elave ele
            if iz_tapıldı:
                məsafə=None
                for i, genişlənmiş_düyüm in reversed(list(enumerate(genişlənmiş_düyümlər))):
                    for qonşular in self.qonşu_düyümArası_məsafələr.keys():
                        if genişlənmiş_düyüm in qonşular and cari_düyüm in qonşular:
                            məsafə=self.qonşu_düyümArası_məsafələr[qonşular]
                            break
                    if i==0:
                        self.bütün_yollar[self.hazırki_yol_ID][0].append(genişlənmiş_düyüm)
                        köhnə_məsafə=self.bütün_yollar[self.hazırki_yol_ID][1]
                        self.bütün_yollar[self.hazırki_yol_ID][1]=köhnə_məsafə+məsafə
                    else:
                        əsas_yol=self.bütün_yollar[self.hazırki_yol_ID][0]
                        yeni_yol_ID=max(list(self.bütün_yollar.keys()))+1
                        köhnə_məsafə=self.bütün_yollar[self.hazırki_yol_ID][1]
                        self.bütün_yollar[yeni_yol_ID]=[əsas_yol+[genişlənmiş_düyüm], köhnə_məsafə+məsafə]

            ## yeni iz ac
            if not iz_tapıldı:
                for genişlənmiş_düyüm in genişlənmiş_düyümlər:
                    for qonşular in self.qonşu_düyümArası_məsafələr.keys():
                        if genişlənmiş_düyüm in qonşular and cari_düyüm in qonşular:
                            məsafə=self.qonşu_düyümArası_məsafələr[qonşular]
                    try:
                        yeni_yol_ID=max(list(self.bütün_yollar.keys()))+1
                    except ValueError:
                        yeni_yol_ID = 1
                    self.bütün_yollar[yeni_yol_ID]=[[genişlənmiş_düyüm], məsafə] 

            ### HEURISTICLI UYGUN düyümU SEC
            # cari düyümü il açıq düyüm olaraq seç
            heuristic_uyğun_düyüm=self.açıq_düyümlər[0]
            print(f'==> Heuristic uyğun düyüm: {heuristic_uyğun_düyüm} | Heuristic məsafəsi: {self.heuristic_məsafələr[heuristic_uyğun_düyüm]} metr\n')
            
            ### CARI düyümU TEZELE
            cari_düyüm = heuristic_uyğun_düyüm 
            self.açıq_düyümlər.remove(cari_düyüm) # seçilib gediləcək düyümü açıq düyümlərdən çıxart
            self.bağlı_düyümlər.append(cari_düyüm)

            if cari_düyüm in self.hədəf_düyümlər:  ## təkli və çoxlu hədəfi dəstəklə
                self.sonlandır("Uğurlu axtarış")
                break

            bütün_yollar_hazırkiYol = [v for v in self.bütün_yollar.values() if v[0][-1]==cari_düyüm][0]
            self.sərfiyyat =  bütün_yollar_hazırkiYol[1]

        return True


    def açıq_düyümləri_sırala(self):
        discSiralanmis_açıq_düyümlər = sorted(self.açıq_düyümlər, key=lambda x: self.heuristic_məsafələr[x], reverse=False)
        return discSiralanmis_açıq_düyümlər


    def sonlandır(self, məzmun=None):
        """ Xüsusiləşdirilmiş sonlandırma; Sıradan və ya məcburi """
        if məzmun=="Uğurlu axtarış":
            bütün_yollar_ugurluYol = [v for v in self.bütün_yollar.values() if v[0][-1] in self.hədəf_düyümlər][0]
            self.gəlinən_yol=[self.başlanğıc_düyüm] + bütün_yollar_ugurluYol[0]
            self.sərfiyyat = bütün_yollar_ugurluYol[1]
            müxtəlif_yol_sayı=len(list(self.bütün_yollar.values()))
            
            hədəf_düyüm = self.gəlinən_yol[-1]
            if hədəf_düyüm not in self.hədəf_düyümlər:
                hədəf_düyüm = self.hədəf_düyümlər

            print(f'\nHədəf tapıldı!\n=== \
                    \n>\'{hədəf_düyüm}\' düyümünə çatmaq üçün {müxtəlif_yol_sayı} müxtəlif yola girildi. \
                    \n> Gəlinən yol: {self.gəlinən_yol} \
                    \n> Sərfiyyat (həqiqi məsafə): {self.sərfiyyat} metr \
                    \n\n')
        else:
            print(f'\n {məzmun} \n')
            # sys.exit()
        

    def axtar(self):
        """ Normal axtarış """
        nəticə = self.axtarış_mühərriki("capEt")
        print(f'Nəticə: {"tapıldı" if nəticə else "tapılmadı"}')


    def çoxNüvəli_axtar(self):
        """ Çox-nüvəli (multi-core) axtarış """
        with concurrent.futures.ProcessPoolExecutor() as executor:
            f1=executor.submit(self.axtarış_mühərriki, "capEt")
            print(f'Nəticə: {"tapıldı" if f1.result() else "tapılmadı"}')



def axtarış_nümunə2(TamahkarObyekt=None):
    """ Nümunə 2 
    """
    if TamahkarObyekt:

        TamahkarObyekt.başlanğıc_düyüm='A'
        TamahkarObyekt.hədəf_düyümlər=['Z1', 'Z2']

        TamahkarObyekt.heuristic_məsafələr = {
            "A": 400,
            "B": 250,
            "C": 150,
            "E": 250,
            "D": 300,
            "F": 200,
            "G": 300,
            "P": 300,
            "Q": 100,
            "V": 200,
            "W": 150,
            "H": 200,
            "I": 100,
            "J": 150,
            "K": 50,
            "R": 50,
            "S": 50,
            "T": 350,
            "X": 100,
            "Y": 50,
            "L": 100,
            "M": 100,
            "O": 90,
            "N": 10,
            "Z1": 0,
            "Z2": 0
        }

        # TamahkarObyekt.bütün_düyümlər=['A', 'B', 'N', 'L', 'G', 'P', 'Y', 'H']
        TamahkarObyekt.bütün_düyümlər = list(TamahkarObyekt.heuristic_məsafələr.keys())

        TamahkarObyekt.qonşu_düyümlər = {
            "A": ["B", "C", "D"],
            "B": ["A", "E", "F", "G"],
            "C": ["A", "P", "Q"],
            "D": ["A", "V", "W"],
            "E": ["B", "H", "I"],
            "F": ["B", "J"],
            "G": ["B", "K"],
            "P": ["C", "R"],
            "Q": ["C", "S", "T"],
            "V": ["D", "X"],
            "W": ["D", "Y"],
            "H": ["E", "L"],
            "I": ["E"],
            "J": ["F", "M", "Z1"],
            "K": ["G", "O"],
            "R": ["P"],
            "S": ["Q", "N"],
            "T": ["Q"],
            "X": ["V", "Z2"],
            "Y": ["W"],
            "L": ["H"],
            "M": ["J"],
            "Z1": ["J"],
            "O": ["K"],
            "N": ["S"],
            "Z2": ["X"],
        }

        TamahkarObyekt.qonşu_düyümArası_məsafələr = {
            ('A', 'B'): 150,
            ('A', 'C'): 100,
            ('A', 'D'): 50,
            ('B', 'E'): 15,
            ('B', 'F'): 35,
            ('B', 'G'): 25,
            ('C', 'P'): 5,
            ('C', 'Q'): 15,
            ('D', 'V'): 50,
            ('D', 'W'): 10,
            ('E', 'H'): 10,
            ('E', 'I'): 30,
            ('F', 'J'): 20,
            ('G', 'K'): 15,
            ('P', 'R'): 300,
            ('Q', 'S'): 35,
            ('Q', 'T'): 5,
            ('V', 'X'): 10,
            ('W', 'Y'): 300,
            ('H', 'L'): 5,
            ('J', 'M'): 10,
            ('J', 'Z1'): 5,
            ('K', 'O'): 5,
            ('S', 'N'): 5,
            ('X', 'Z2'): 15,
            }



def axtarış_nümunə3(TamahkarObyekt=None):
    """ Nümunə 3 
    """
    if TamahkarObyekt:

        TamahkarObyekt.başlanğıc_düyüm='S'
        TamahkarObyekt.hədəf_düyümlər=['E']

        TamahkarObyekt.heuristic_məsafələr = {
            "S": 10,
            "A": 9,
            "B": 7,
            "C": 8,
            "D": 8,
            "H": 6,
            "L": 6,
            "G": 3,
            "F": 6,
            "I": 4,
            "J": 4,
            "K": 3,
            "E": 0,
        }

        # TamahkarObyekt.bütün_düyümlər=['A', 'B', 'C', 'E', 'D', 'Y', 'H']
        TamahkarObyekt.bütün_düyümlər = list(TamahkarObyekt.heuristic_məsafələr.keys())

        TamahkarObyekt.qonşu_düyümlər = {
            "S": ["A", "B", "C"],
            "A": ["S", "D", "B"],
            "B": ["S", "A", "D", "H"],
            "C": ["S", "L"],
            "D": ["A", "B", "F"],
            "F": ["D", "H"],
            "H": ["F", "B", "G"],
            "G": ["H", "E"],
            "E": ["G", "K"],
            "L": ["C", "I", "J"],
            "I": ["L", "K"],
            "J": ["L", "K"],
            "K": ["I", "J", "E"],
        }

        TamahkarObyekt.qonşu_düyümArası_məsafələr = {
            ('S', 'A'): 7,
            ('S', 'B'): 2,
            ('S', 'C'): 3,
            ('C', 'L'): 2,
            ('A', 'B'): 3,
            ('A', 'D'): 4,
            ('B', 'D'): 4,
            ('B', 'H'): 1,
            ('D', 'F'): 5,
            ('H', 'F'): 3,
            ('H', 'G'): 2,
            ('L', 'I'): 4,
            ('L', 'J'): 4,
            ('I', 'K'): 4,
            ('J', 'K'): 4,
            ('G', 'E'): 2,
            ('K', 'E'): 5,
            }













""" Sadə və ya Çoxnüvəli prosesi çalışdır """
if __name__ == '__main__':
    # axtarış başlamadan zaman
    başlanğıc_zamanı = time.perf_counter()


    # Class-in instansini (obyektini) al
    Axtarış_alqoritmi = TamahkarAxtarış()
    
    # axtarış 2
    # axtarış_nümunə2(TamahkarObyekt=Axtarış_alqoritmi)
    axtarış_nümunə3(TamahkarObyekt=Axtarış_alqoritmi)

    # Axtarış_alqoritmi.axtar()
    Axtarış_alqoritmi.çoxNüvəli_axtar()


    # axtarış bitende zaman
    bitiş_zamanı = time.perf_counter()

    keçən_zaman=bitiş_zamanı-başlanğıc_zamanı
    print(f'Keçən zaman: {keçən_zaman} saniyə\n')