Интерактив ба ухаалаг систем | лекц № 3, 4

         Их мэдэгч google дүүгээс үл мэдэгч Харх ах нь "AI" гэж бичээд зураг асуутал урдаас Ai Takahashi гэдэг энэ хүүхний зургийг санал болгож байх юм. Гүй ээ яахав дажгүй хүүхний зураг тавьж байгаад AI-ийнхаа лекц гурав дөрвийг шивээд тавьчихъя гэж бодлоо. Дараа нь сорил энэ тэр дээр энэ шивсэн лекцүүд маань хэрэг болох байх гэж найднам... За юу ч гэсэн Мөөж хамын бичсэн лекцнээс эхлэе. Манай хүн галограммын нууцлалтай бичдэг учраас зарим үгнийх нь бичгийн хэвийг нь тайлж унших гээд чадахгүй байна.

Хайлтын алгоритм

"Лекц №3: Хайлтын үндсэн алгоритм"

           Мод өргөтгөх - Бид асуудал болон зорилгоо тодорхойлсон. Асуудлын томъёоллыг хүлээн авч зорилгыг биелүүлэх үйлдлийн дарааллыг (solution) буцаах функцыг хайлтын функц гэнэ.

           Санаа: Тухайн төлвөөс операторуудаа ашиглан шинээр төлвүүд гарган өртгөтгөх процесс юм. Эндээс хайлтын мод (search three) гэсэн ойлголт гарч ирдэг. Энэ процессыг мод өргөтгөх буюу expanding гэж хэлдэг.

Function General - Search (problem, strategy) return a solution or future

A - Гүний нэвтрэлт
B - Түвшний нэвтрэлт

---

Мод өгөгдлийн бүтэц:

• Мод нь зангилаануудаас тогтоно
• Төлөв нь физик ертөнцийн ш/ч цуглуулга
• Зангилаа нь эцэг, хүү, гүн, замын зардал g(x) зэргийг агуулсан ө/б юм.

Puzzle

• Expand функц нь Successor Fn-ийг ашиглан төрөл бүрийн төлвүүд харгалзах шинэ зангилааныг үүсгэдэг.

 Үнэлгээ: 2+3+3+2+2+2+0+3=17
            Өргөтгөгдөхөөр хүлээгдэж байгаа зангилаануудын олонлогийг fringe эсхүл frontier гэж нэрлэдэг.
            Хайлтын стратеги нь эдргээрээс дараачийн өргөтгөгдөх зангилааг сонгодог.

            Энэхүү fringe зангилаануудын олонлогийг дараалал байдлаар (queue) дүрсэлдэг.
Fuction Tree - Search (problem, queue

Хайлтын стратегуудыг дараах үндсэн зүйлүүдээр үнэлнэ.

• Completeness / Бүрэн хэсэг: Энэ стратеги нь шийдлийг баталгаатай олох уу?
• Time complexity / Хугацааны асуудал: Шийд олохдоо хэр удаж байна?
• Space complexity / Орон зайн асуудал: Хэр зэрэг санах ой ашиглах?
• Optimality / Оновчтой эсэх: Чанар + зөв нь

Дараах хүчин зүйлээр хэмжигдэнэ.

• b (branching factor): Хайлтын модны мах factor. Нэг зангилаанаас гарах мах зангилааны тоос уг модны factor.
• d (depth): Шийдийн орших гүн

Хайлтын хоёр категор байна.

• Uninformed: Үнэлгээ хийгддэггүй, хайлтын стратегиас үл хамаарна. (6 алгоритм)
• Informed: 5

Unformed:

• Blind search - сохор хайлт
• Breadth - first search
• Uniform - cost search
• Depth - first search
• Depth - limited search
• Iterative deepening searc
• Bidirectional

Complete: Тийм (b төгсгөлөг бол)
Time: 1+b+b^2+b^3+...+b(b^d-1)
Өөрөөр хэлвэл экспонекциал өсөлт.

• Uniform Cost Search: Хамгийн бага зангилааг өргөтгөдөг. BFS нь UCS-ийн тухайн тохиолдол.

• Depth - First Search: Санах ойг маш бага шаарддаг.

Эндээс эхлээд "Лекц №4"

• Depth - Limited Search (DLS): BFS хайлтын максимум M гүнийг оптемал L гүнээр хязгаарлан хайх юм. Үүний тулд тухайн асуудлын оптемал гүнг (шийд баталгаатай оршин байх хамгийн бага гүн) хүн тооцоолон олсон байх хэрэгтэй.
• Iterative deepening Search (IDS): Хайлтын гүнийг 0-ээс эхлэн аажмаар нэмэгдүүлэн хайх хайлт. Ямар ч асуудлын оптемал гүн өөрөө олох давуу талтай. Хамгийн хүчирхэг хайлт юм. Цагт хавчигдсан системд хэрэглэж болно. Жишээ нь: Цагтай шатар, өгөгдсөн цагт тохируулан шийдийг олох чадвартай. DFS хайлтыг бодвол 11% илүү тооны зангилаа өргөтгөх тул арай илүү удаан байж болох
• Bidirectional Search (BS): Анхы төлөв болон зорилгын төлөв хоёроос нь өөд өөдөөс нь хайна. Хоёр хайлт огтлолцох үед шийд олдоно. Хариунаас нь бодох аргатай төстэй...

 Давхардсан төлвүүдээс зайлсхийх:

• Хайлтын алгоритм нь өмнө нь авч үзсэн төлөвөө дахин авч үзэхээс аль болох зайлсхийвэл зохино.
• Төлвүүдийг давхардуулан ахин дахин үзсэнээр хайлт маш удаан болдог
• Давхардлыг шалгахгүй бол шугаман асуудал ч экспонциал болж болно.

Давхардлыг шалгах гурван арга:

• Ирсэн төлөврүүгээ буцаж орохгүй байх. Өөрөөр хэлвэл эцэгтэйгээ адил хүү заниглаа үүсгэхгүй байх.
• Циклдсэн зам үүсэхгүй байх.
• Үүсгэсэн төлвүүдийн мэдээллийг шалгаж хадгалж шинээр үүсгэж байгаа төлвүүдийг тэдэнтэй харьцуулан шалгах

Alpha - Betta Prunning Search
Шатар:

• Муу байрлалуудыг өргөтгөлгүй алгасдаг байх
• Хурдтай хайдаг
• Шатар хийхдээ энэ алгоритмыг ашиглаж болно.

Ингээд байхгүй цаашаагаа унтаад лекцээ бичээгүй би лав хаха

Шошго: Судлагдахуунууд