Kommivayjer masalasi

Gts algoritmi

Qadam 0

[Insiallashtirish] TOUR:=0; COST:=0; V:=U;

Qadam 1

[Hama shaharlarni o’tish] For k:=1 to N-1 do qadam 2;

Qadam 2

[Keyingi vektorga o’tish]

Faraz qilaylik, (V,W) – V shahardan W ga olib borayotgan eng kichik narxli vektor. Unda:

TOUR:=TOUR+(V,W); COST:=COST+C(V,W);

V:=W;

N ta shaharlar va C narxlar matrisasi berilgan kommivoyajer masalasi uchun U shahardan boshlab COST narxli TOUR yaqinlashgan yechimni topish kerak.

-	1	2	7	5
1	-	4	4	3
2	4	-	1	2
7	4	1	-	3
5	3	2	3	-

Marshrutni tasvirlash uchun biz matematikada graf yoki tur deb nomlanayotgan chizmadan foydalanamiz. Umuman tur – bu nuqtalar va bir nechta yoki barcha ikki nuqtalarni bog’layotgan chiziqlar to’plami, undan tashqari chiziqlar ustida qiymatlar ham berilishi mumkin.
Masalani soddalashtirish uchun beshta shahar uchun yechim topamiz. Rasm. 1a – narxlar matrisasi. Rasm. 1b – turli model ko’rsatilgan.