I-Ili drvo

I-ili drvo je grafički prikaz smanjenja problema (ili ciljeva) do konjunkcije i disjunkcije od pod-problem (ili pod-ciljevi).

Primer

I-ili drvo:

predstavlja pretragu prostora za rešavanje problema P, koristeći metode cilj-smanjenja:

P if Q and R

P if S

Q if T

Q if U

Definicije

Imajući u vidu početni problem P0 i set metode rešavanja problema u obliku:

P if P1 and … and Pn

povezani i-ili drvo je skup obeleženih čvorova koji su:

1. Koren stabla je označen po čvoru P0.
2. Za svaki čvor N oznakom od problema ili pod-problema P i za svaku metodu obrasca P if P1 and … and Pn, postoji skup dece čvorovi N1, …, Nn čvora N, tako da je svaki čvor Ni obeležen sa Pi. Čvorovi su spojene po luku, da bi se razlikovali od sinova N koji bi mogli biti povezani sa drugim metodama.

Čvor N, obeležen od problema P,je uspeh čvora ako postoji metod obrasca P ako ništa (tj., P je „činjenica"). Čvor je neuspeh čvora ako ne postoji metod za rešavanje P.

Ako sva deca nekog čvora N, spojene od istog luka, su uspeh čvorovi, onda čvor N je takođe uspeh čvor. Inače čvor je čvor neuspeh.

Pretraživanje strategije

I-ili drvo određuje samo pretragu prostora za rešavanje problema. Različite strategije za pretragu za pretraživanje prostor su moguće. Ovo uključuje pretraživanje stabla dubine prvo, širina-prvi ili najbolji-prvi koristeći neku meru poželjnosti rešenja. Strategija pretraživanje može biti sekvencijalna, traženje ili generisanje jedan čvor u vreme, ili paralelno, ili u potrazi generisanje nekoliko čvorova paralelno.

Odnos sa logičkim programiranjem

Metode koje se koriste za generisanje i-ili drveća iskazna logika programa (bez promenljivih). U slučaju logičkih programa koji sadrže promenljive, rastvori objedinjeni pod-problemi moraju biti kompatibilni. Predmet ove komplikacije, sekvencijalna i paralelna strategija za i-ili drveće pretrage obezbeđuje kompjuterski model za izvršavanje logičkih programa.

Odnos sa dva igrača igara

I-ili drveće se takođe može koristiti da predstavljaju prostore pretrage za dve osobe igara. Koren čvora takvog drveta predstavlja problem jednog od igrača pobedničkih igara, počevši od početnog stanja igre. S obzirom čvor N, obeleženi od problema P od pobede igrača iz određene države, postoji jedan set sintetičke dece čvorova, koji odgovaraju svim protivnikovim anketiranih poteza. Za svaki od ovih čvorova dece, postoji niz od ne-sintetičke dece čvorova, koji odgovara svim branećim potezima igrača.

Za rešavanje igre sa drveća pretraga broja dokaza familija algoritama, igra drveća da se mapira i / ili drveće. MAX-čvorova (tj. maksimalno igrača da se preseli) su predstavljeni kao čvorovi ILI, MIN-čvorovi karta do I čvorova. Mapiranje je moguće, kada pretraživanje vrši samo sa binarnim ciljom, koji obično „igrač za kretanje pobeđuje u igri“.

Literatura

• Luger, George F.; Stubblefield, William A. (1993). Artificial intelligence: structures and strategies for complex problem solving (2 izd.). The Benjamin/Cummings. ISBN 978-0-8053-4785-2. Pristupljeno 28. 2. 2013. 
• Nilsson, Nils J. (1998). Artificial Intelligence: A New Synthesis. Morgan Kaufmann. ISBN 978-1-55860-467-4. Pristupljeno 28. 2. 2013.