A prológ vágási és visszahúzási mechanizmusa
Többféle megoldás kibocsátásának képessége
A ProLog megkülönböztető jellemzője, hogy ha a PROLOG megoldásait keresi, a megfelelő értékek teljes listáját adják meg. Ezért a ProLog-ban egy predikátumot egy egész sor szabály képviselhet, amelyek mindegyike válaszolhat. Egy példa. Lássuk le a "number_more" predikátum következő leírását:
Ezután a ProLog megoldó
Válaszokat ad: Több = 5, 8.
Más szavakkal, a 4. számú számozásnál a "number_more" predikátum szabályai szerint két szám van 5 és 8. Úgy látszik, hogy a szabálykészlet az algoritmikus nyelvek ágakstruktúrájaként működik. Az olyan predikátumok, amelyek több értéket generálnak, undefined (nondeterm) -nek nevezik. Az olyan predikátumokat, amelyek csak egy értéket termelnek, a determin. A ProLog meghatározatlan predikátumai mellett a bizonytalanság mechanizmusa még mindig használatos. Egy példa.
Ezután a ProLog megoldó
A válasz: Mi = apartman, gyerekek
Rollback (visszalépéses)
Most bemutatjuk a visszahúzás fogalmát (Backtracking). A Rollback a ProLog egyik kísérlete, hogy megtalálja a következő megoldást a problémára. A visszalépést a program valamely pontján bekövetkezett hiba okozza, ami a PROLOG-ot arra készteti, hogy megtalálja a következő megoldást. A visszalépés megy arra a pontra, ahol lehetséges egy másik megoldás kiszámítása. Ebben az esetben minden olyan kapcsolódó változó, amely a másik megoldás lehetséges pontja alatt kapcsolódik, felszabadul. Amikor felhívja a ProLog megoldót, a PROLOG automatikusan hozza létre a visszahúzást, hogy visszavegye az összes döntési értéket. Egy példa.
Nyírás (Cut)
Most bemutatjuk a vágás fogalmát. A ProLog egy csonkolása olyan mechanizmus, amely megtiltja a predikátum szabályainak a jelenlegi szabály alatti keresését, és tiltja a visszahúzó mechanizmust. A csonkolás a "!" Jelzéssel látható. Egy példa. Ha átírjuk az előző "number_ball" predikátumot, mint:
Ezután a ProLog megoldó
Visszaadja a választ: Több = 5.
Ez azért van, mert a predikátum minden szabályában több ellenőrzés után a "!" Clipping operátor lép be, ami megakadályozza, hogy a PROLOG később visszahúzódjon és más választási lehetőségeket keres.
Példa a visszahúzó és vágómechanizmus használatára.
A visszahúzó és levágó mechanizmus a következő példában látható. Tegyük fel, hogy van egy listánk az értékekről, amelyekben találunk egy bizonyos értéket, és megadjuk az értéket. Mivel a ProLog logikai nyelv, a feladatot egy sor szabály létrehozásával oldják meg:
Ha listát rendezünk, ha az aktuális elem nem a kívánt érték, akkor még egy brute-force-et is tovább csinálunk.
A lista rendezésénél, ha az aktuális elem a kívánt érték, akkor állítsa le a keresést, és térjen vissza az előző elemre.
Ha az előző szabályok nem működnek, akkor az aktuális elemet visszaadja az előző értéknek.
A PROLOG predikátum nyelvének leírása ezen szabályokat végrehajtva:
Annak tudatában, hogy a ProLog-ban a szabályok sorrendjét használhatja a szabályzatok elkerülésének módjának kiválasztására, és a lehatároló mechanizmus hatásának ismeretében, az 1. és a 2. szabályokat helyeken átrendezheti, és eltávolíthatja az eltérések ellenőrzését. Ezután kapjuk meg a predikátum következő leírását:
A kapott leírás három szabályból áll, és a következő műveleteket hajtja végre. Az első szabály összehasonlítja az aktuális elemet a kívánt értékkel, és ha egyenlők, akkor a) az alább felsorolt predikciós szabályok levágása a keresésben való részvételből, b) hiba keletkezik, ami a rekurzió megállításához vezet. A második szabály felsorolja a lista összes elemét, ha hívja magát, vagyis rekurziót hív. Ebben az esetben a rekurzív hívás előtt nincs lefényképezés, és ha a rekurzív hívás sikertelen, akkor a vezérlés az alább található predikciós szabályhoz vezet. Ha a rekurzív hívás sikeres lesz, akkor a leütést ("!") Hívják, majd a predikátum kimenetét hívják. A harmadik szabály visszaadja az aktuális elemet, mint az előző értéket, amely a keresett érték előtt van, a kivágást és a predikátum kimenetét okozza. A predikátum cselekményét egy példa szemlélteti. Adjuk meg a ProLog megoldóját:
A PROLOG az első előterjesztési hívást jelenti:
- Az 1. szabály nem működik: 3 nem egyenlő 1. Menj a második szabályhoz:
- A 2. szabály miatt rekurzív módon találjuk meg az előre meghatározott értéket (3, [2,4,3,5,2], Előző):
- Az 1. szabály nem működik: a 3. nem egyenlő 2. Menj a második szabályhoz:
- A 2. szabály miatt rekurzív módon találja meg az előre meghatározott értéket (3, [4,3,5,2], Előző):
- Az 1. szabály nem működik: 3 nem egyenlő 4. Ugrás a második szabályhoz:
- A 2. szabály felhívja a rekurziót: find_pr_value (3, [3,5,2], Előző):
- Az első szabály fog működni: 3 = 3. és végrehajtódik: a predikátum szabályok lecsengése alacsonyabb és hiba. Ami azt eredményezi, hogy a rekurzióból kiesés következik be.
- A 2. szabály folytatása A rekurzív hívás sikertelensége a [3,5,2] listával a második szabály ezen a szinten való meghibásodásához vezet. A ProLog átveszi a harmadik szabályt.
- 3. szabály. Itt a lista = [4,3,5,2]. Vannak műveletek: Az előző egyesítve van 4-el, a kimenet más lehetséges megoldások kivágásával.
- A 2. szabály folytatása. A rekurzió sikeres értéket ad vissza. Előző = 4. Van egy kilépés a többi lehetséges megoldás kivágásával.
- A 2. szabály folytatása. A rekurzió sikeres értéket ad vissza. Előző = 4. Van egy kilépés a többi lehetséges megoldás kivágásával.
- A 2. szabály folytatása. A rekurzió sikeres értéket ad vissza. Előző = 4. Van egy kilépés a többi lehetséges megoldás kivágásával.
Válasz ProLog Előző = 4.
Most nézzük meg, mi történik, ha eltávolítjuk a kivágást a második szabályban:
A ProLog már több eredményt produkál:
Ez lehetséges, mivel a ProLog visszaállító mechanizmus be van kapcsolva, és a második szabályban lehetőség nyílik a rekurzió minden egyes lépésére.