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

Bu məqalədə daxili keçidlərin artırılmasına ehtiyac var. Lütfən, məqalələrin əlaqələndirilməsinə kömək etmək üçün mövzuya uyğun başqa səhifələrə daxili keçidlər əlavə etməklə bu məqaləni təkmilləşdirməyə kömək edin. (dekabr 2023)

Bu, tənha məqalədir, çünki hansısa məqalədən bu məqaləyə verilmiş keçid yoxdur. Lütfən, əlaqəli məqalələrdən bu səhifəyə keçid verməyə çalışın. (dekabr 2023)

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.

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.^[1]

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. 

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. 

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. 

Ə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.