Tietojenkäsittelytieteen ja tekoälyn olennainen osa ovat hakualgoritmit. Niitä käytetään useiden ongelmien ratkaisemiseen shakin ja tammen kaltaisten pelien pelaamisesta lyhimmän reitin löytämiseen kartalta. Depth First Search (DFS) -menetelmä, yksi suosituimmista hakualgoritmeista, etsii verkkoa tai puuta kulkemalla mahdollisimman pitkälle kutakin haaraa pitkin ennen kääntymistä. DFS:llä on kuitenkin kriittinen haittapuoli: jos graafi sisältää jaksoja, se voi jäädä loputtomaan silmukkaan. Iterative Deepening Search (IDS) tai Iterative Deepening Depth First Search on yksi tapa ratkaista tämä ongelma (IDDFS).

Mikä on IDS?

IDS-niminen hakualgoritmi yhdistää DFS:n edut Breadth First Searchiin (BFS). Kaaviota tutkitaan DFS:n avulla, mutta syvyysraja nousi tasaisesti, kunnes kohde löydetään. Toisin sanoen IDS käyttää jatkuvasti DFS:ää nostaen syvyysrajaa joka kerta, kunnes haluttu tulos saavutetaan. Iteratiivinen syventäminen on menetelmä, joka varmistaa, että haku on perusteellinen (eli se löytää ratkaisun, jos sellainen on olemassa) ja tehokas (eli se löytää lyhimmän polun tavoitteeseen).

IDS:n pseudokoodi on yksinkertainen:

Koodi

 function iterativeDeepeningSearch(root, goal): depth = 0 while True: result = depthLimitedSearch(root, goal, depth) if result == FOUND: return goal if result == NOT_FOUND: return None depth = depth + 1 function depthLimitedSearch(node, goal, depth): if node == goal: return FOUND if depth == 0: return NOT_FOUND for child in node.children: result = depthLimitedSearch(child, goal, depth - 1) if result == FOUND: return FOUND return NOT_FOUND 

Miten IDS toimii?

IterativeDeepeningSearch-toiminto suorittaa iteratiivisen syventävän haun kaaviossa käyttämällä juurisolmua ja tavoitesolmua syötteinä, kunnes tavoite saavutetaan tai hakutila on käytetty. Tämä saavutetaan käyttämällä säännöllisesti deeplylimitedSearch-toimintoa, joka asettaa DFS:lle syvyysrajoituksen. Haku päättyy ja palauttaa tavoitesolmun, jos tavoite sijaitsee missä tahansa syvyydessä. Haku tuottaa Ei mitään, jos hakutila on käytetty loppuun (kaikki solmut syvyysrajaan asti on tutkittu).

deepLimitedSearch-toiminto suorittaa DFS:n kuvaajalle määritetyllä syvyysrajalla ottamalla syötteiksi solmun, kohdesolmun ja syvyysrajan. Haku palauttaa LÖYTYNYT, jos haluttu solmu sijaitsee nykyisellä syvyydellä. Haku palauttaa NOT FOUND, jos syvyysraja saavutetaan, mutta tavoitesolmua ei löydy. Jos kumpikaan kriteeri ei ole tosi, haku siirtyy iteratiivisesti solmun jälkeläisiin.

Ohjelmoida:

Koodi

 from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def add_edge(self, u, v): self.graph[u].append(v) def iddfs(self, start, goal, max_depth): for depth in range(max_depth+1): visited = set() if self.dls(start, goal, depth, visited): return True return False def dls(self, node, goal, depth, visited): if node == goal: return True if depth == 0: return False visited.add(node) for neighbor in self.graph[node]: if neighbor not in visited: if self.dls(neighbor, goal, depth-1, visited): return True return False # Example usage g = Graph() g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.add_edge(3, 3) start = 0 goal = 3 max_depth = 3 if g.iddfs(start, goal, max_depth): print('Path found') else: print('Path not found') 

Lähtö

 Path found 

Edut

• IDS on monin tavoin parempi kuin muut hakualgoritmit. Ensimmäinen etu on, että se on kattava, mikä varmistaa, että ratkaisu löytyy, jos sellainen on hakutilassa. Tämä on niin, että kaikki tietyn syvyysrajan alaiset solmut tutkitaan ennen kuin syvyysrajaa nostetaan IDS:llä, joka tekee syvyysrajoitetun DFS:n.
• IDS on muistitehokas, mikä on sen toinen etu. Tämä johtuu siitä, että IDS vähentää algoritmin muistin tarvetta, koska se ei tallenna kaikkia hakualueen solmuja muistiin. IDS minimoi algoritmin muistin jalanjäljen tallentamalla solmut vain nykyiseen syvyysrajaan asti.
• IDS:n kyky hyödyntää sekä puu- että graafihaussa on sen kolmas etu. Tämä johtuu siitä, että IDS on yleinen hakualgoritmi, joka toimii missä tahansa hakutilassa, mukaan lukien puu tai kaavio.

Haitat

• IDS:n haittana on, että se voi vierailla tietyissä solmuissa useammin kuin kerran, mikä saattaa hidastaa hakua. Täydellisyyden ja optimaalisuuden edut usein ylittävät tämän haitan. Lisäksi käyttämällä strategioita, kuten muistia tai välimuistia, toistuvat matkat voidaan minimoida.