Amaliy matematika va informatika” yo’nalishi 18. 08-guruh talabasi Topvoldiyev Muslimjon Muxtorjom o’g’lining

2.2 Krestofides algoritmi strukturasi

Krestofides algoritmida 5 ta shaharga, bir shahardan turib qolganlariga bir marttadan borib qaytish uchun eng qisqa masofa topishni ko’rib chiqamiz. Bunda shaharlar aro masofalar ko’rsatilgan bo’lishi lozim. Quyida A shahardan turib qolganlariga borib qaytish uchum yo’nalishlar ko’rsatilgan:

A shahardan turib qolgan 4 ta shaharni masofalarini solishtirib eng kichik uzublikdagi masofani aniqlaymiz, bu yerda AB = 100, AC = 200, AE = 175, AD=150. Bizga kerakli bo’lgan masofa bu AB ni belgilab olamiz.

Birinchi harakatni ekranga chiqariladi: A -> B =100

Ikkinchi harakarimiz ham huddi birinchi kabi amalga oshiriladi, haqat birinchi shahar hisobga olinmasdan qolganlarini solishtiriladi: BC = 125, BD = 250, BE = 225. Ko’rib turganingizdek 3 ta yo’nalish bo’ylab masofalarni solishtiramiz bunda eng kichik son BC = 125.

A -> B -> C = 225

Huddi shu harakatlarni qolgan shaharlar uchun ham qo’llaymiz: CE = 275, CD=300 A -> B -> C -> E= 500

Natija: A -> B -> C -> E -> D -> A= 725