Səyahət edən tacir (alqoritm)

Səyahət edən tacir  (ing. ing. travelling salesman problem (TSP)) - informatikada həlli çətin olan məsələlərdən biridir. Səyahət edən tacir belə bir sual soruşur: "Mənə şəhərlərin siyahısı və şəhərlər arasında məsafə verilibdir. Görəsən, bütün şəhərlərə səyahət edib və evə qayıtmaq üçün ən qısa yol hansıdır? Amma bir şərtlə ki, bir şəhəri iki dəfə ziyarət etməyim." Ilk baxışdan çox sadə görünən bu sual, əslində informatikada NP çətin məsələdir.

"Səyahət edən tacir" məsələsinin həlli : Qara xətt bütün qırmızı nöqtələri birləşdirən ən qısa yoldur

Bu məsələ ilk dəfə 1930 ildə formalaşdırılıb və ən çox öyrənilmiş optimallaşdırma məsələlərindən biridir. Bir çox optimallaşdırma metodu üçün benchmark (etalon) kimi istifadə olunur. Baxmayaraq ki, səyahət edən tacir hesablama baxımdan çətin məsələdir, on minlərlə şəhər üçün bu məsələni dəqiq və heuristik həlləri var. Hətta milyonlarla şəhər üçün bu məsələni 1% səhvlə həll etmək mümkündür.

Səyahət edən tacirin bir neçə tətbiq sahəsi var, nümunə olaraq, planlaşdırma, logistika və microçip sahələrini göstərmək olar. Bir azca dəyişdirilmiş forması isə daha geniş istifadə olunur, məsələn, DNA ardıcıllığının tapılmasında. Bunun üçün "şəhər" olaraq DNA fraqmentlərini, "şəhərlər arasında məsafə" olaraq isə DNA fraqmentləri arasında oxşar ölçü vahidini götürmək lazımdır. Səyahət edən tacir eyni zamanda astronomiyada da istifadə oluna bilər. Belə ki, astronomlar teleskopu müşahidə etdikləri cisimlər arasında hərəkət etdirərkən, teleskopun hərəkət vaxtını minimallaşdırmaq istəyirlər. 

Qraf məsələsi

Simmetrik - 4 şəhərlə

Səyahət edən tacir məsələsi qraf kimi göstərmək olar. Belə ki, qrafın təpə nöqtələri - şəhərləri, qrafın tilləri isə, şəhərlər arasındakı yolu təsvir edir. Beləliklə, minimallaşdırma məsələsi qrafın hər hansı təpəsindən çıxmaqla bütün təpələri bir dəfə gəzib, həmin təpəyə qayıtmaq məsələsinə çevrilir. 

Heuristik və aproksimasiya alqoritmləri

Bir çox heuristik və aproksimasiya alqoritmləri sürətli şəkildə yaxşı həll tapmağa kömək edir. Müasir metodlar böyük problemlər (milyonlarla şəhər) üçün az bir zamanda optimala yaxın (optimaldan 2-3% fərqli) həll tapır. 

Heuristik yanaşmanın bir neçə kateqoriyası var. 

Konstruktiv heuristika

"Ən yaxın qonşu" alqoritmi - 7 şəhər üçün. Başlanğıc nöqtə dəyişdiriləndə, həll də dəyişilir. 

Ən yaxın qonşu alqoritmi (Acgöz alqoritm kateqoriyasına aiddir) növbəti addım kimi tacirin ən yaxın gəzilməmiş şəhərə getməyinə imkan verir. Bu alqoritm çox qısa zamanda qısa yolu tapır.