Begreper & referanser

1from collections import deque2 3tidlig_maltest = 1  # @param 0..14 5# Urettet graf; naboene står i alfabetisk rekkefølge6naboer = {"S": "ABC", "A": "DS", "B": "ES", "C": "FS",7          "D": "AG", "E": "B", "F": "C", "G": "D"}8frontier = deque(["S"])9forelder = {"S": None}  # nådd-mengden10utvidet, funnet = [], None11while frontier and funnet is None:12    node = frontier.popleft()13    if not tidlig_maltest and node == "G":14        funnet = node15        break16    utvidet.append(node)17    for barn in naboer[node]:18        if barn not in forelder:19            forelder[barn] = node20            if tidlig_maltest and barn == "G":21                funnet = barn22                break23            frontier.append(barn)24sti, node = [], funnet25while node is not None:26    sti.insert(0, node)27    node = forelder[node]28print(f"Ekspansjonsrekkefølge: {', '.join(utvidet)}")29print(f"Funnet sti: {' → '.join(sti)}")30print(f"Antall ekspansjoner: {len(utvidet)}")

Prøv: sett tidlig_maltest til 0 og se at Antall ekspansjoner: øker fra 5 til 7, mens Funnet sti: er den samme.

1import heapq2 3kost_SB = 4  # @param 1..94 5kanter = {("S", "A"): 2, ("S", "B"): kost_SB, ("A", "C"): 3,6          ("B", "C"): 1, ("C", "G"): 2, ("B", "G"): 6}7naboer = {}8for (u, v), c in kanter.items():9    naboer.setdefault(u, []).append((v, c))10    naboer.setdefault(v, []).append((u, c))11frontier = [(0, "S")]  # (g, node): lavest g først, likt g alfabetisk12beste = {"S": 0}13forelder = {"S": None}14utvidet = []15while frontier:16    g, node = heapq.heappop(frontier)17    if g > beste[node]:18        continue  # utdatert post, erstattet av en billigere sti19    if node == "G":20        break  # måltest ved uttak21    utvidet.append(node)22    for barn, c in sorted(naboer[node]):23        if barn not in beste or g + c < beste[barn]:24            beste[barn], forelder[barn] = g + c, node25            heapq.heappush(frontier, (g + c, barn))26sti, node = [], "G"27while node is not None:28    sti.insert(0, node)29    node = forelder[node]30print(f"Ekspansjonsrekkefølge: {', '.join(utvidet)}")31print(f"Funnet sti: {' → '.join(sti)}")32print(f"Kostnad: {beste['G']}")

Prøv: sett kost_SB til 1 og se at Funnet sti: går via B og Kostnad: faller til 4, og sett den så til 9 og se at B ekspanderes sist på linja Ekspansjonsrekkefølge:.

1b = 3  # @param 2..122d = 6  # @param 1..83 4# Regnet med formlene, uten å kjøre søket (roten telles ikke som generert)5bfs = sum(b ** i for i in range(1, d + 1))6ids = sum((d + 1 - i) * b ** i for i in range(1, d + 1))7ekstra = 100 * (ids - bfs) / bfs8 9 10def tall(n):11    return f"{n:,}".replace(",", " ")12 13 14print(f"Noder generert av BFS: {tall(bfs)}")15print(f"Noder generert av IDS: {tall(ids)}")16print(f"Ekstra arbeid for IDS: {ekstra:.1f} %")

Prøv: øk b fra 3 til 10 og se at Ekstra arbeid for IDS: faller fra rundt 49 % til rundt 11 %, mens Noder generert av BFS: vokser kraftig.

1best_forst(start, er_maal, naboer, prioritet):2    beste_g = {start: 0}             # nådd-mengden: billigste kjente sti hit3    forelder = {start: ingen}4    kø = prioritetskø med posten (prioritet(start, 0), 0, start)5    så lenge kø ikke er tom:6        (_, g, x) = ta ut posten med lavest prioritet7        hvis g > beste_g[x]:8            hopp over posten         # utdatert: x er nådd billigere siden9        hvis er_maal(x):             # måltest ved uttak10            returner stien til x langs forelder, og g11        for (y, kost) i naboer(x):12            g_y = g + kost13            hvis y ikke er i beste_g eller g_y < beste_g[y]:   # ny eller strengt billigere14                beste_g[y] = g_y15                forelder[y] = x16                legg (prioritet(y, g_y), g_y, y) i kø17    returner «ingen løsning»

Samme løkke for alle søkene, bare prioriteten skiller dem. En billigere sti legger en ny post i køen i stedet for å lete opp den gamle, og den gamle hoppes over når den kommer ut.