Саяхатшы мәселесі келесі сұрақты қояды: "Қалалар тізімін және әрбір жұп қалалар арасындағы қашықтықты ескере отырып, әр қалаға дәл бір рет барып, шыққан қаласына қайтатын ең қысқа жол қандай болуы мүмкін?"
Саяхатшыны қалай атайды?
Саяхатшы – тауарларды үйме-үй аралап сатушы, сонымен қатар саудагер деп те белгілі.
Саяхатшы шешілді ме?
Жапония ғалымдары бұрыннан да күрделі саяхатшы сатушы мәселесін шешті. Лезде шешудің алдыңғы стандарты 16 «қала» болды және бұл ғалымдар 22 қаланы шешу үшін процессордың жаңа түрін пайдаланды. Олардың айтуынша, дәл осындай тапсырманы орындау үшін дәстүрлі фон Нейман CPU 1 200 жыл қажет еді.
Сіз саяхатшыны қалай шешесіз?
TSP мәселесін Brute-Force әдісі арқылы шешу үшін маршруттардың жалпы санын есептеп, содан кейін сызып, барлық ықтимал бағыттарды тізімдеу керек. Әр бағыттың қашықтығын есептеп, содан кейін ең қысқасын таңдаңыз - бұл оңтайлы шешім. Бұл әдіс шешілетін мәселені бірнеше ішкі мәселелерге бөледі.
Саяхатшы NP қиын ба?
Саяхатшыны оңтайландыру (TSP-OPT) - NP-қиын мәселе және саяхатшы сатушыны іздеу (TSP) - NP аяқталды. Дегенмен, TSP-OPT-ны TSP-ге азайтуға болады, өйткені егер TSP полиномды уақытта шешілсе, TSP-OPT(1).
