13-amaliy mashg’ulot. Timsollarni avtomatik sinflash algoritmlari asosida amaliy masalalarni yechish

13-amaliy mashg’ulot. Timsollarni avtomatik sinflash algoritmlari asosida amaliy masalalarni yechish

Quyida timsollar orasidagi masofani hisoblash yordamida oʻqituvchi yordamisiz sinflarga ajratadigan va sinflar sonini avtomatik ravishda aniqlaydigan "Maksmin" algoritmini keltiramiz [43, 49]. Bu algoritmi erkin tanlovdan TOlarni 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 [43, 49].
1. Boshlangʻich yadroni tanlash: Birinchi timsol OTdan 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 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.
13. 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.
Misol sifatida 14.1-rasmda keltirilgan yadrolarni va sinflarni keltirish mumkin.

14.1-rasm. Yadrolar va sinflarni hosil qilish.


Misol. Masalaning qoʻyilishi. Bizga (14.1-jadval) tanlov berilgan [4].
14.1-jadval

Timsollar	Belgilar
	a1	a2	a3	a4	a5	a6	a7	a8
S1	0	58	37	2	1	63	38	4
S2	0	62	39	4	0	70	37	5
S3	1	73	40	5	1	74	39	4
S4	0	55	38	3	1	81	40	1
S5	1	75	40	0	1	90	40	0
S6	1	84	39	1	0	95	37	3
S7	0	95	37	1	0	84	39	2
S8	1	98	37	3	1	59	38	0