Utolsó előadás

Megajánlott jegyhez a NEPTUN-ban fel kell venni a december 16-i vizsgát. (több is van, azt kell felvenni, ahol megjegyzésben oda van írva, hogy a megajánlott jegy beírására, nincs létszámkorlát és terem se) Ha megajánlott ötösöd van és ezt nem teszed meg, nem tudjuk beírni a jegyet és elveszik.

Pót-pót ZH-hoz pedig az infopy portálon kell jelentkezni. A pót-pót ZH különeljárási díjas!

A match szerkezet

Gyakran előfordul, hogy valamilyen változó értékét egymás után sorban kell összehasonlítanunk és ettől függően más és más kódrészletet kell lefuttatnunk. Python 3.10 előtt erre az if - elif - else szerkezetet használtuk. Tipikusan állapotgépekben ez a vezérlési szerkezet nagyon gyakran fordul elő. Pl. az előadáson mutatott kódrészlet, a LY számláló egy részlete az következő:

Az if-elif-else
kígyó...

    if c == "l":
        allapot = LL_VOLT
    elif c == "y":
        szaml += 1
        allapot = ALAP
    else:
        allapot = ALAP
        ...

Használata alapesetben nagyon egyszerű. A match utáni változót hasonlítjuk össze a case-ben leírt esetekkel. Pl. az előző eset példáját így írhatjuk át. A case ágakba tesszük az összehasonlítandó értékeket, majd utána megfelelő kódrészletet. Az utolsó case, az aláhúzás speciális: ezzel jelezzük azt, hogyha a felette lévő esetek közül egyik sem teljesült, akkor minden más értékre ezt kell csinálni.

match mit
case mivel.

    match c:
        case 'l':
            allapot = LL_VOLT
        case 'y': 
            szaml += 1
            allapot= ALAP
        case _:
            allapot= ALAP

Lehetőségünk van többszörös eset létrehozására is, az | operátor használatával. Ez a vagy kapcsolat jelölése. Például egy 1-10 terjedő szám római kiírása így is írható:

def romai(n):
    match n:
        case 1 | 2 | 3: return "I"*n
        case 4: return "IV"
        case 5 | 6 | 7 | 8: return "V" + "I"*(n-5)
        case 9: return "IX"
        case 10: return "X"
        case _: return ""

A case-ben nem csak konstans és egész számra visszavezethető, pl. karakter érték (más nyelvek terminológiájával élve integrális típusú) állhat, hanem bármi. Ezek közül a legizgalmasabb a lista vagy a tuple.

    parancs= input().split()   
    match parancs:
        case "go", "north":
            print("Észak felé")
        case "go", "east":
            print("Kelet felé")
        # ...
        case _:
            print("Ismeretlen parancs")

A matchben is lehet többszörös illeszkedés és az illesztett részt megkaphatjuk paraméterként is az as használatával. Feldolgozhatjuk a lista/tuple maradék részét a *operátorral és végezetül az alapesetet hívhatjuk other-nek is.

parancs= input().split()

match parancs:
    case "go", "north" | "east" | "south" | "west" as irany:
        print(f"Going to {irany}")
    case "print", *what:
        print(*what)
    # ...
    case other:
        print("Ismeretlen parancs")

További részletek a kézikönyvben.

Type hinting

Nem arról volt szó, hogy a Python dinamikus típusos nyelv? Honnan tudja akkor a fejlesztőrendszer?

Python 3.5 felett megmondhatjuk a paraméterek típusát és a függvények visszatérési értékét. Ezt a futtatáskor a Python SEMMIRE nem használja, de a fejlesztőrendszerek ellenőrzésre igen. Egyrészt tudnak adni segítséget, másrészt a háttérben folyamatosan tudják ellenőrizni a begépelt kódot.

Láthatjuk, hogy ez viszonylag egyszerű. Kettőspont után írjuk a típust, a függvény visszatérési értékét pedig a -> operátor után. Ha ezt megtettük és a fejlesztőrendszerünkben bekapcsoltuk a típusok ellenőrzését, akkor a fejlesztőrendszer figyelmeztetni fog a hibára és kijavíthatjuk, vagy ignorálhatjuk. Ezzel megúszunk olyan bosszantó eseteket, amikor egy elmaradt típus konverzió egy hosszabb futás eredményét esetleg tönkreteszi. Vigyázat, ha bekapcsoljuk lehet, hogy mérgesek leszünk a túlzott precizitástól!

További részletek a kézikönyvben.

Iterátorok/generátorok - rövid gyakorlatias összefoglaló

Hogyan is működik a for ciklus valójában? Ha írunk egy ilyen sort, mi történik?

    for i in range(100):
        print(i)

Nem fog a Python egy 100 elemű egész tömböt generálni, abban biztosak lehetünk.

    it= range(100).__iter__() # vagy iter(range(100))
    while True:
        try:
            print(it.__next__()) # vagy next(it)
        except StopIteration:
            break

Aminek az elemein a for ciklussal végigszaladunk, az egy ún. iterálható (bejárható) objektum. Ennek van két nevezetes függvénye az __iter__(), ami inicializálja a bejárást és a __next__() , ami mindig a következőt elemet adja, ha létezik. Az utolsó elem után pedig StopIteration kivételt dob.

Saját magunk is megírhatjuk ezeket a függvényeket. Pl. nézzük meg egy egyszerű láncolt lista esetén:

    class ListaIt:
        def __init__(self, gyoker):
            self.gyoker= gyoker
            self.mozgo= gyoker
        def __iter__(self):
            self.mozgo= self.gyoker
            return self
        def __next__(self):
            if self.mozgo == None:
                raise StopIteration
            ret= self.mozgo.adat
            self.mozgo= self.mozgo.kov
            return ret

    for e in ListaIt(eleje):
        print(e)

Láthatjuk, hogy pontosan ugyanazt a függvényt használjuk, mint amit már megírtunk a lista bejárására, de a for ciklus használatával sokkal kifejezőbb és egyszerűbb lett a tároló felhasználása, ráadásul itt sorban kapjuk az értékeket, nem kell magába a bejárást végző függvénybe írnunk az adatfeldolgozást.

Nem minden
iterátor generátor,
de minden generátor
iterátor :-)

A generátorok speciális függvények, amelyek képesek visszatérni egy visszatérési értékkel, de eközben megőrzik saját állapotukat, és a következő híváskor a végrehajtás onnan folytatódik. Ehhez egy új kulcsszó, a yield tartozik, ezt használjuk a return helyett.

    def bejar(eleje):
        mozgo= eleje
        while mozgo!= None:
            ret, mozgo = mozgo.adat, mozgo.kov # 
            yield ret

    for e in bejar(eleje):
        print(e)

Belépéskor inicializáljuk a mozgo változót (ez megfelel az __iter__() hívásnak), majd belépünk a ciklusba és a legelső adattal visszatérünk a yield kulcsszó hatására, de a függvény állapota megőrződik. A következő híváskor a yield után folyatjuk, azaz a while ciklus halad tovább. Ez felel meg a __next__() hívásnak. Ez egészen addig folytatódik, amíg a függvény végét nem érjük el. Tehát ez valójában egy jóval egyszerűbb szintaxisa az iterátor megvalósításnak. A legfontosabb előny azonban az, hogy nem kell megvalósítanunk a két különálló függvényt.
További tudnivalókat nézd meg a kézikönyvben.

Generikus algoritmusok

Egy programban numerikus integrálásokat kell végeznünk különféle függvényekre. Például tudni szeretnénk, mennyi a math.sin(x) határozott integrálja [a, b] intervallumon, vagy mennyi a negyzet(x) függvény integrálja [a, b] intervallumon. Ezeket a határozott integrálokat közelíthetjük téglalapok területösszegével: apró lépésekben kiszámítva mindenhol a függvények értékét, a téglalapok területét, és azok összegét. Fontos megjegyzés: ez az algoritmus demonstrációs célokat szolgál. Integrált NEM SZABAD ezzel a módszerrel számolni, erre vannak sokkal jobb algoritmusok, kérdezze meg matematikusát vagy kedvenc keresőjét...

def integral_sin(a, b):
    ossz = 0.0
    x = a
    while x < b:
        ossz += math.sin(x) * 0.001
        x += 0.001
    return ossz


def integral_negyzet(a, b):
    ossz = 0.0
    x = a
    while x < b:
        ossz += negyzet(x) * 0.001
        x += 0.001
    return ossz


def negyzet(x):
    return x ** 2

Észrevehetjük, hogy lényegében megírtuk kétszer ugyanazt a függvényt. Mindkettőben ugyanaz az a-tól b-ig menő ciklus van, mindkettő ugyanúgy lép, ugyanúgy kiértékeli a függvényt, ugyanúgy összegzi a területeket. Az egyetlen különbség a két integráló között az, hogy mely függvénynek az integrálját számítják ki, vagyis hogy mely függvényt kell meghívni a téglalapok magasságának meghatározásához.

Felmerül a kérdés, hogy nem lehetne valahogy ezt a kódduplikációt megszüntetni? Nem lehetne az integráló függvénynek paraméterként adni azt, hogy mely matematikai függvénynek határoznánk meg az integrálját?

Ha két függvénynek egyforma a fejléce, vagyis egyformán kezelik a paramétereket, akkor kompatibilisek egymással. Az integrálós példánkban minden integrálandó függvény megkap egy számot és elvégez rajta egy műveletet, aminek az eredményét a visszatérési értékben közli.

def negyzet(x):
    return x ** 2

# math.py
def sin(x):
    return ...

def harmadikfuggveny(x):
    return x - 7 + math.sqrt(x)

f = negyzet
print(f(3))   # negyzet(3)

f = math.sin
print(f(3))   # math.sin(3)

f = harmadikfuggveny
print(f(3))   # harmadikfuggveny(3)

Ezek alapján már az integráló függvényünk könnyen parametrizálhatóvá tehető:

import math

def integral(f, a, b):
    ossz = 0.0
    x = a
    while x < b:
        ossz += f(x) * 0.001
        x += 0.001
    return ossz

def negyzet(x):
    return x ** 2

def main():
    print(integral(negyzet, 5, 10)) # !
    print(integral(math.sin, 5, 10))

main()

Az integrálónak így három paramétere van: az integrálandó függvény: f, és a határok: [a, b]. A területek számításánál pedig mindig a paraméterként kapott függvényt hívja, f-et. Ez az f paraméter a két példában más-más függvénynek referenciája; először a saját negyzet()-ünknek, másodjára pedig a beépített math.sin()-nek. Mivel ez paraméterré vált, az integráló innentől bármilyen más függvényt is tud integrálni, lényeg, hogy egyváltozós, valós→valós függvényről legyen szó.

Képzeljük most el, hogy egy határidőnaplós programot írunk. Ebben egy menüből választhatjuk ki a teendőt.

Határidőnapló

1. Adatbevitel
2. Módosítás
3. Keresés
0. Kilépés

Melyik? _

print("1. Adatbevitel") # 1. sorminta
print("2. Módosítás")
print("3. Keresés")
print("0. Kilépés")

valasztas = int(input())
if valasztas < 4:
    if valasztas == 1: adatbevitel(esemenyek) # 2. sorminta
    elif valasztas == 2: modositas(esemenyek)
    elif valasztas == 3: kereses(esemenyek)

Vizsgáljuk meg a menüpontok függvényeit!

def adatbevitel(esemenyek):
    # ...
    esemenyek.append(...)
    

def modositas(esemenyek):
    # ...
    esemenyek[i] = ...


def kereses(esemenyek):
    for e in esemenyek:
        ...

if valasztas == 1: adatbevitel(esemenyek)
elif valasztas == 2: modositas(esemenyek)
elif valasztas == 3: kereses(esemenyek)

Észrevehetjük, hogy itt hasonló a helyzet, mint az előző esetben. Van egy csomó függvényünk, amelyek a menüpontokból kiválasztható tevékenységeket végzik. Ezek mind paraméterként kapják a listát, amelyet aztán módosítanak vagy nem. (Ez a menü szempontjából mindegy, mert a paraméterként átadott lista módosítható a függvényből.) A függvények mindig pontosan egy paramétert kapnak, és nincs visszatérési értékük. Vagyis ezek is kompatibilisek egymással. Ha referenciákat tárolnánk rájuk, akkor létrejöhetne egy függvényeket tartalmazó táblázat, amellyel dolgozhatna a menü!

A függvényobjektumok, és azok referenciái ismeretében a menüpont feliratát és a meghívandó függvényt betehetjük egy objektumba. Ehhez elég egy sima tuple, bár akár definiálhatnánk külön osztályt is.

A menüpontok kiírása és a kiválasztott menüpont végrehajtása:

menupontok = [
    ("Adatbevitel", adatbevitel),
    ("Módosítás", modositas),
    ("Keresés", kereses),
]


# Menü kiírása
for idx, menupont in enumerate(menupontok):
    (felirat, _) = menupont
    print(f"{idx+1}. {felirat}")

# Választás, és a függvény meghívása
v = int(input())
if 1 <= v <= len(menupontok):
    (_, fuggveny) = menupontok[v - 1]
    fuggveny(esemenyek)
else:
    print("Nincs ilyen menüpont")

def szamlal(lista, pred):
    db = 0
    for x in lista:
        if pred(x):     # adott tulajdonságú?
            db += 1
    return db

A program forráskódja is így nagyon szemléletes. Akárhány függvényt írhatunk, amelyek tulajdonságokat vizsgálnak. Ezek a predikátumok:

def negativ(x):
    return x < 0

def paros(x):
    return x % 2 == 0

A függvényeket pedig egyszerűen paraméterként átadjuk:

lista = [5, 7, 12, -6, ………]

print(szamlal(lista, negativ), "db negatív szám.")
print(szamlal(lista, paros), "db páros szám.")

A függvény tehát paraméterként kapja a vizsgálandó számsort, továbbá egy másik függvényt, a predikátumot. Ezt a függvényt meghívja minden elemre – ez a függvény mondja meg, hogy az adott elemeket bele kell-e épp számolni, vagy nem. Hogy épp a negatív számok esetén növeljük a számlálót, vagy a páros számok esetén.

Mi a helyzet akkor, ha paraméterezni szeretnénk a predikátumot? Például meg szeretnénk számolni az összes 5-nél nagyobb számot. Vagy 8-nál nagyobbat. 19-nél nagyobbat... Mindegyikhez külön predikátumot kell írni, mert a számlálásban a predikátum egy paraméterű kell legyen?

Szerencsére nem, mert lehetséges függvény belsejében függvényt definiálni:

def szamlal(lista, pred):
    db = 0
    for x in lista:
        if pred(x):    # unáris predikátum!
            db += 1
    return db

def main():
    szamok = [ 87, 56, 34, 98, 11, 25 ]
    print("Számok:", szamok)
    
    hatar = int(input("Minél nagyobbak? "))
    def nagyobb_hatarnal(x):
        return x > hatar    # !
        
    print(szamlal(szamok, nagyobb_hatarnal), "db")

main()

def nagyobb_hatarnal(x):
    return x > hatar    # hatar = ?

A rendezőalgoritmusokat is meg tudjuk fogalmazni generikusan. Ott ugyanez a helyzet, mint a számlálásnál vagy a keresésnél. Az algoritmus maga ugyanaz, csak az változik, hogy melyik elem kisebb, melyik nagyobb – egész pontosan, hogy melyik való a lista elejére, és melyik a végére, mert kisebbről és nagyobbról itt már nem beszélhetünk.

def rendez(lista, pred):
    for i in range(0, len(lista) - 1):
        leg = i
        for j in range(i + 1, len(lista)):
            if pred(lista[j], lista[leg]):
                leg = j
        temp = lista[i]
        lista[i] = lista[leg]
        lista[leg] = temp

A függvénynek adott predikátum most nem egy-, hanem kétparaméterű. Ugyanis nem egy elemről kell megmondania, hogy rendelkezik-e valamilyen tulajdonsággal, hanem két elemet kell összehasonlítania; előrébb való-e az egyik a rendezett listában, mint a másik. Ha a kisebb elemekre mondjuk azt, hogy előrébb való, akkor növekvő sorrendet kapunk. Ha a nagyobb elemek kerülnek előre, akkor csökkenő lesz a sorrend.

def kisebb(a, b):
    return a < b

def nagyobb(a, b):
    return a > b

lista = [5, 7, 12, -6]
rendez(lista, kisebb)   # -6, 5, 7, 12
rendez(lista, nagyobb)  # 12, 7, 5, -6

Az előző pont egyparaméterű predikátumait unáris predikátumnak nevezzük (unary predicate). Az összehasonlító, kétparaméterű predikátumokat pedig binárisnak (binary predicate).

A list.sort() függvény, illetve a globális sorted() függvény is generikus. Mindkettő kaphat rendezési relációt, méghozzá a key=... nevű paraméterükben veszik azt át. Ez a két rendezőalgoritmus azonban a rendezési szempontot másképp kezeli. Nem bináris predikátumot várnak, azaz „kisebb-e az egyik, mint a másik?” kérdésre válaszoló függvényt. Hanem egy olyat, amelyik egy leképezést ad meg: minden rendezendő elemhez hozzárendel egy értéket, és a rendezés utána azon értékek szerint történik.

szavak = ["körte", "alma", "dió", "cseresznye"]

szavak.sort()
print(szavak)   # alma, cseresznye, dió, körte

szavak.sort(key=len)
print(szavak)   # dió, alma, körte, cseresznye

Az első esetben a szavakat rendezzük. Alapértelmezés szerint a .sort() függvény magukat az elemeket hasonlítja össze. Sztringeknél a növekvő sorrend, a < b ábécé szerinti összehasonlítást jelent, így kapjuk meg sorban az A, C, D és K betűvel kezdődő szavakat.

A második esetben a rendezéshez kulcsot adunk, és ez a len függvény. Ezért minden egyes rendezendő elemre a rendezőalgoritmus meghívja a len()-t, pl. len("dió"), len("alma") és így tovább. Ezzel egész számokat kap, a rendezendő sztringek hosszát, és végülis ezek alapján teszi őket sorba. A sor elejére a legrövidebb szó kerül (mert ahhoz tartozott a legkisebb szám), a végére pedig a leghosszabb.

A sorted() függvény ugyanígy működik, azzal a különbséggel, hogy az nem módosítja a listát, hanem új listát ad.

Lássunk példákat rendezések kulcsaira!

class Tort:
    ...

def tort_valos(t):
    return t.szaml / t.nev

tortek = [ ... ]
tortek.sort(key=tort_valos)

class Tort:
    ...

    def __float__(self):
        return self.szaml / self.nev

tortek = [ ... ]
tortek.sort(key=Tort.__float__)

Lássunk egy másik példát, egy névsort!

class Ember:
    def __init__(self, nev, szuletesnap):
        ...

def ember_szuletesnap(e):
    return e.szuletesnap

nevsor = [ ... ]
nevsor.sort(key=ember_szuletesnap)

class Ember:
    def __init__(self, nev, szuletesnap):
        ...

nevsor = [ ... ]
nevsor.sort(key=lambda e: e.szuletesnap)

def main():
    szaml = 0
    def nop():
        pass
    def egy():
        nonlocal szaml
        szaml = szaml + 1
    def ketto():
        nonlocal szaml
        szaml = szaml + 2

    allapotgep = [
        [(L_VOLT, nop),  (ALAP, nop),   (ALAP, nop)], 
        [(LL_VOLT, nop), (ALAP, egy),   (ALAP, nop)], 
        [(LL_VOLT, nop), (ALAP, ketto), (ALAP, nop)], 
    ]

    while True:
        # ...
        (ujallapot, tevekenyseg) = allapotgep[allapot][kar]
        tevekenyseg()
        allapot = ujallapot

Visszalépő keresés (backtrack)

Feladat: tegyük egy sakktáblára nyolc királynőt úgy, hogy ne üssék egymást!

Húzd az egeret a királynők fölé!

Próbáljuk végig a lehetséges megoldásokat!

Ehhez el kell tárolnunk, hogy melyik királynő hol van. Definiáljunk egy pozíció nevű típust, és hozzuk létre belőle a 8 elemű listát!

class Pozicio:
   def __init__(self, x, y):
      self.x = x
      self.y = y

kiralynok = [
    Pozicio(1, 5),
    Pozicio(7, 6), ...
]

Hány megoldást kell végigpróbálnunk?

Hány megoldást kell végigpróbálnunk? Összesen 8×8 = 64 mezőre kell 8 királynőt raknunk. Vagyis 64 mezőből 8-at kell választanunk, ahol lesz királynő, a többi mezőkön nem. Ez ugyanaz a probléma matematikailag, mint a lottósorsolás, ahol 90 számból kell 5 különbözőt választani. A kombinatorikában ezt ismétlés nélküli kombinációnak nevezik. Ezek számát, „64 alatt a 8-at” jópár faktoriális kiszámításával lehet meghatározni:

         64!
C = ──────────── = 4 426 165 368
     8!·(64-8)!

100 000 próbálkozás / másodperc → 44 261 másodperc → fél nap.

Ha a gépünk százezer állást tud végigpróbálni másodpercenként, akkor is fél napig fog futni a programunk. Ezért másképp kell okoskodni, még akkor is, ha valójában a mai asztali számítógépek sokkal gyorsabbak ennél (kb. 1–10 millió próbálkozás / másodperc is belefér).

Mivel nem lehet egy sorban két királynő (ütnék egymást vízszintesen), ezért biztosak lehetünk abban, hogy minden sorban pontosan egy királynő lesz (8 sor, 8 királynő). Tehát lényegében elég csak azt megmondanunk a programunkban, hogy melyik sorban hol van a királynő. És ezt eltárolni is bőven elegendő; egy 8 elemű, int-eket tartalmazó listára van csak szükségünk. Ha például poz[3] == 7, az azt jelenti, hogy a harmadik sor királynője a hetedik oszlopban van.

Észrevehetjük, hogy minden sorban pontosan egy királynő lesz:

poz = [5, 2, 4, ...]

Hogyan számítjuk ki így a végigpróbálandó esetek számát? A tömbelemek a 0...7 (1...8) értékeket vehetik fel. Ez 8ⁿ lehetőséget jelent, ahol n a tömbelemek száma; az pedig most szintén 8. A kombinatorikában ez az ún. ismétléses variáció.

V = 88 = 16 777 216

Vagyis 16,7 millió esetről van szó – az előzőek 260-adrészéről. Ez már sokkal inkább vállalhatónak tűnik, de még valamit észre kell vennünk.

Kétszer nem szerepelhet ugyanaz a szám:

poz = [1, 2, 3, 4, 5, 6, 7, 8]

Ha a listában kétszer szerepelne ugyanaz a szám, az azt jelentené, hogy két különböző királynő ugyanabban az oszlopban van. Akkor viszont ütnék egymást függőlegesen, ezért ezeket az eseteket is kizárhatjuk. Vagyis valójában nem egy ismétléses variációt keresünk, hanem a fenti, 1-8 számokat tartalmazó lista permutációit. Az tehát a kérdésünk, hogy ennek a listának mely keverései, sorbaállításai adják a megoldást.

P = 8! = 40 320 !

A permutációk száma faktoriálissal határozható meg. A 8-elemű tömbünk lehetséges permutációinak száma 40320, vagyis az eredetileg kigondolt 4,4 milliárd megvizsgálandó esetet százezred részére tudtuk csökkenteni! Ha ez még nem lenne elég, az így kialakított listában az ütési helyzetek vizsgálata is egyszerűbb. Mivel eleve minden sorba csak egy királynőt rakunk (a sor száma az index), és minden oszlopba is egyet (a listaelemek egymástól különböző értékei), így már csak az átlós ütéseket kell vizsgálnunk majd, a függőlegeseket és a vízszinteseket nem.

Ütésben vannak, ha

Tehát csak az átlós ütésekkel kell foglalkozni. Átlós ütés akkor van, ha ugyanannyi sort kell lépni az egyik királynőtől a másikig, mint ahány oszlopot.

• 45 fokos átlón: dx = dy
• –45 fokos átlón: dx = –dy
• A kettő együtt: |dx| = |dy|

Figyelembe kell vennünk, hogy ez mindkét irányú átlón megtörténhet. De ha vesszük az ugrások abszolút értékét (hogy mindegy legyen, fel vagy le, illetve jobbra vagy balra kell menni), akkor egyetlen egy egyenlettel leírhatjuk, mikor van ütközés: ha |x1–x2| = |y1–y2|.

A vizsgálatot ez a függvény fogja végezni:

def kiralyno_oke(poz):
    for i in range(len(poz) - 1):
        for j in range(i + 1, len(poz)):
            if abs(poz[i] - poz[j]) == abs(i - j):
                return False
    return True

Az adatszerkezetünkben a tömbindexek a sorok, a tömbértékek pedig az oszlopok. Vagyis ha bármely két tömbelemre igaz az, hogy az indexek különbsége megegyezik az értékek különbségével, akkor ütést találtunk, és az nem megoldás. Ha sehol nincs ilyen, akkor a tömb egy helyes megoldást tartalmaz.

Valójában az abs(i - j) helyett írhattunk volna j - i-t. A j index mindig nagyobb, mint az i (ez látszik a ciklushatárokon), tehát így biztosan pozitív számot kapnánk, abszolút érték nélkül is. A fenti példakódban maradt az abs(i - j), mert jobban illeszkedik a gondolatmenethez.

Permutáció

• Menjünk végig a sorozaton. Tegyük mindegyik elemét az elejére.
• Az így kapott sorozat fennmaradó részét permutáljuk.
• Tegyük vissza az elemet a helyére.

Másképp fogalmazva: előreveszünk egy elemet, kavargatjuk a többit. Aztán előreveszünk egy másik elemet, és megint kavargatjuk a többit. Ezt kell megcsinálni mindegyik elemmel.

def permutal(lista, honnan=0):
    if honnan == len(lista): # !
        print(lista)
        return

    for i in range(honnan, len(lista)):
        csere(lista, honnan, i)
        permutal(lista, honnan + 1) # !
        csere(lista, honnan, i)

permutal(lista, honnan + 1)
for i in range(honnan + 1, len(lista)):
    csere(lista, honnan, i)
    permutal(lista, honnan + 1)
    csere(lista, honnan, i)

Ha ez megvan, nincs más teendőnk: az előálló permutációkat megvizsgálni, és csak az elfogadhatóakat kirajzolni.

def kiralyno_keres(poz, honnan=0):
    if honnan == len(poz):
        if kiralyno_oke(poz): # !
            kiralyno_kiir(poz)
        return

    for i in range(honnan, len(poz)):
        csere(poz, honnan, i)
        kiralyno_keres(poz, honnan + 1)
        csere(poz, honnan, i)


def main():
    kiralyno_keres([1, 2, 3, 4, 5, 6, 7, 8])

Valójában most is rengeteg feleslegesen kipróbált megoldás van:

poz = [1, 2, ???]
poz = [3, 2, ???]
poz = [1, ?, 3, ???]
poz = [6, ?, 4, ???]

A permutációs módszerrel rengeteg állást megvizsgáltunk hiábavalóan. Például az első királynőt leraktuk az első oszlopba, a másodikat a második oszlopba (mint a rajzon). Ezek biztosan ütik egymást, tehát a maradék hatot hiába próbáljuk meg elhelyezni bárhogyan, helytelen lesz a megoldásunk. A maradék 6 királynő elhelyezésére 6! = 720 lehetőség van, tehát ennyi állás vizsgálatát kihagyhattuk volna. És nem ez az egyetlen ilyen eset; a fenti listakezdemények mind olyan elhelyezéseket mutatnak, ahol a kérdőjelek helyére bármi is kerül, biztosan rossz a megoldás.

Vannak olyan feladványok, ahol egy lehetséges megoldást egyben kell látnunk, és csak akkor tudjuk eldönteni, hogy helyes-e. A nyolckirálynő-probléma azonban nem ilyen. Itt egy részmegoldást is tudunk vizsgálni. Vagyis egy még nem teljesen kitöltött táblára kétféle állítást tehetünk, a) ez még lehet jó, próbáljuk meg kitölteni az alját, b) ez már biztosan nem lesz jó. Vagyis hasznos megvizsgálnunk a részmegoldást is, mert az ki fog zárni egy csomó esetet.

start következő folyamatos

Az új algoritmushoz egy egyszerűbb tesztelőfüggvény tartozik, mint az előzőhöz. Mivel most egyesével rakjuk majd a királynőket, mindig csak a legutóbbit kell megnézni, hogy jó-e, nem üti-e a többit. Az összes előzőre nem figyelünk: úgy jutunk mindig ide, hogy azok már ellenőrizve vannak.

Ütésben vannak, ha

• Azonos oszlopban vannak: x1 = x2
• Azonos átlón vannak: |dx| = |dy|

Ebben az algoritmusban feltételezzük, hogy a lista nem annyi elemet tartalmaz, amilyen magas a tábla, hanem csak az első valahány darab királynőt, amit már feltettünk a táblára. Vagyis a legutolsó elem az, amit vizsgálunk.

def kiralyno_utolso_oke(poz):
    utso = len(poz) - 1
    for i in range(utso):
        if (poz[i] == poz[utso] 
            or abs(poz[i] - poz[utso]) == abs(i - utso)):
            return False
    return True

Ügyelni kell arra, hogy most nem csak az átlót kell vizsgálni, hanem azt is, hogy az új királynő nem került-e valamelyikkel azonos oszlopba: poz[i] == poz[utolso]. A listába ugyanis most nem permutációk kerülnek, hanem minden sorban végigpróbáljuk az összes oszlopot, és oszlopok szerinti ütés is előfordulhat. De ez csak egy újabb feltétel; az algoritmus még így is egyszerűbb, egyetlen egy ciklus vizsgálja az új királynő sora előtti sorokat.

Az alábbi függvény valósítja meg a visszalépő keresést a probléma megoldására. Ez nem a klasszikus megvalósítás, még később finomítjuk majd, de előbb lássuk a működését!

A függvénynek paramétere most a mekkora nevű változó, amelyik azt mutatja, hogy mekkora játéktáblán kell megtalálni a megoldásokat. Ugyanis most egy teljesen üres listából indulunk ki, ahogy a hívásnál is látszik.

def kiralyno_keres(poz, mekkora):
    if len(poz) == mekkora:
        kiralyno_kiir(poz)
        return

    for uj in range(1, mekkora + 1):
        poz.append(uj)
        if not kiralyno_utolso_oke(poz):
            poz.pop()  # visszalépés
            continue
        kiralyno_keres(poz, mekkora)
        poz.pop()

def main():
    kiralyno_keres([], 8)

def permutal(lista, honnan):
    if honnan == len(lista):
        return
    
    for i in range(honnan, len(lista)):
        csere(lista, honnan, i)
        permutal(lista, honnan + 1)
        csere(lista, honnan, i)

def kiralyno_keres(poz, n=0):
    if not kiralyno_nedik_oke(poz, n - 1): # !
        return
    if n == len(poz):
        kiralyno_kiir(poz)
        return
    
    for i in range(n, len(poz)):
        csere(poz, n, i)
        kiralyno_keres(poz, n + 1)
        csere(poz, n, i)

def main():
    kiralyno_keres([1, 2, 3, 4, 5, 6, 7, 8])

A végleges megoldásunk tehát ez. Valójában ez alig különbözik az első, permutáló megoldástól. Az egyetlen különbség abban rejlik, hogy ez részmegoldásokat is megvizsgál, és azokat nagyon hamar visszautasítja, ha nem jók. Ezt mutatja a felkiáltójellel jelölt rész: ez a visszalépés.

A teljes program letölthető innen: 8kiralyno_bt_perm.py.

Az alábbi táblázat azt mutatja, hogy táblaméret függvényében hány pályaállást kell megvizsgálni akkor, ha a teljes permutációkat előállító módszert, illetve a visszalépő keresést alkalmazzuk a probléma megoldására.

Lent látható a visszalépő keresés általános megfogalmazása pszeudokód formájában. Ez annyiban különbözik az előbb látott nyolckirálynő-megoldótól, hogy itt a hipotézis helyességének a vizsgálata is báziskritériumként szerepel. Vagyis a ciklus feltétel nélkül elindítja a rekurziót a kiegészített megoldás vizsgálatára; aztán a rekurzív hívás dönti el, hogy elfogadja vagy visszautasítja azt a megoldást, amit éppen lát.

függvény: visszalépő_keresés(megoldás)

    ha a (rész)megoldás hibás   báziskritériumok
        vissza
    ha megoldás elfogadható
        kiírás
        vissza

    ciklus a következő részmegoldásokkal   egyszerűsítés
        megoldás kiegészítése
        visszalépő_keresés(megoldás)

A fenti algoritmus az összes megoldást kilistázza. De a visszalépő keresés könnyedén módosítható olyan feladatok megoldására, ahol csak egy megoldást keresünk, vagy esetleg meg akarunk állni az első egynéhány megoldás megtalálása után.

Ha egy megoldás keresése a feladat, akkor ahhoz bevezetünk a függvénynek egy visszatérési értéket. Ez fogja azt mutatni, sikerült-e megoldást találni vagy nem.

def kiralyno_keres(poz, n=0):
    if not kiralyno_nedik_oke(poz, n - 1):
        return False # !
    if n == len(poz):
        return True  # !
    
    for i in range(n, len(poz)):
        csere(poz, n, i)
        if kiralyno_keres(poz, n + 1):
            return True # !
        csere(poz, n, i)

    return False # !

def main():
    poz = [1, 2, 3, 4, 5, 6, 7, 8]
    talalt = kiralyno_keres(poz)
    if talalt:
        kiralyno_kiir(poz)

A visszalépő keresés alkalmazásai:

• Rejtvények: nyolc királynő, sudoku, keresztrejtvény, labirintus
• Nyelvi elemzés (fordítóban)
• Optimalizálási feladatok, pl. hátizsák-probléma, pénzosztás