12–Ma’ruza. Timsollarni o’rganuvchi va tanuvchi tizimlar

V₄

X11	1	1	0	0		X11	0	0	0	0
X12	1	1	1	1		X12	0	0	0	0
X*	1	0	0	0			X*	0	0	1	1

Demak, timsol sinfning barcha timsollariga oʻxshash, shuning uchun ga tegishli.

8. «Maksmin» algoritmi

Quyida timsollar orasidagi masofani hisoblash yordamida oʻqituvchi yordamisiz sinflarga ajratadigan va sinflar sonini avtomatik ravishda aniqlaydigan algoritmlarni keltiramiz. Bu algoritmlardan biri "Maksmin" algoritmi [25].

"Maksmin" algoritmi erkin tanlovdan tayanch timsollarni topishga va bu timsollar orqali sinflarni hosil qilishga asoslangan. Ta’kidlaymizki, har bir timsol dan iborat boʻlib, uning tashkil etuvchilari esa dan iborat.
"Maksmin" algoritmi quyidagi qadamlardan iborat.
1. Boshlangʻich yadroni tanlash: Birinchi timsol TTdan ixtiyoriy tanlanadi, ya’ni . Undan keyin yadrolar tanlanadi. Yadrolar soni nechta boʻlishi oldindan ma’lum emas.
2. yadrodan eng uzoq masofada joylashgan timsol topiladi. Buning uchun yadrodan barcha timsollargacha boʻlgan masofa

hisoblanadi.
3. yadrodan eng uzoq masofada joylashgan timsol

topiladi.
4. Ikkinchi yadro sifatida tanlanadi. timsol uchinchi qadamda topiladi.
5. va orasidagi masofa hisoblanadi.
6. yadrodan barcha timsollargacha boʻlgan masofalar 2 - qadamdagidek hisoblanadi.
7. yadrodan barcha timsollargacha boʻlgan masofalar
hisoblanadi.
8. va yadrodan barcha timsollargacha boʻlgan masofalar orasidan eng kichiklari, ya’ni

topiladi.
9. va yadrolarga nisbatan topilgan va masofalardan eng kattasi
tanlanadi.
10. va yadrolar orasidagi masofaning yarmi topiladi .
11. Agar boʻlsa, u holda yangi yadro sifatida ga mos keluvchi timsol tanlanadi.
12. yadro va 9 - qadamda aniqlangan qiymatga mos keluvchi yadrogacha boʻlgan masofa topiladi.
yadrodan barcha timsollargacha boʻlgan masofa 7 - qadamdagidek aniqlanadi.
14. va yadrolardan barcha largacha boʻlgan masofalar orasidan eng kichiklari 8 - qadamdagidek aniqlanadi.
15. va yadrolarga nisbatan topilgan eng kichik masofalar va lar orasidan eng kattasi 9 - qadamdagidek topiladi.
16. va lar orasidagi masofaning yarmi 10 - qadamdagidek topiladi va agar boʻlsa, yangi yadro sifatida timsol tanlanadi. Agar boʻlsa, u holda algoritm oʻz ishini tugatadi. Bu vaqtda sinflar soni va bu sinflarning yadrolari aniqlanadi.
Agar sinflar soni va yadrolar oʻzgarmasdan qolsa, algoritm oʻz ishini toʻxtatadi.Topilgan boʻsagʻa deb nomlanuvchi - ya’ni yadrolar orasidagi masofaning yarmi timsollarni yadrolarga birlashtiradi va sinflar hosil qiladi.