ട്രാവലിങ് സേൽസ്‌മാൻ അൽഗോരിതം

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
Jump to navigation Jump to search
Solution of a travelling salesman problem

തിയററ്റിക്കൽ കമ്പ്യൂട്ടർ സയൻസിലേയും ഗ്രാഫ് തിയറിയിലേയും ഒരു പ്രധാനപ്പെട്ട ചോദ്യമാണ് ട്രാവലിങ് സേൽസ്‌മാൻ പ്രശ്നം. കോമ്പ്ലക്സിറ്റി തിയറി പ്രകാരം NP-Hard ആയ ഈ പ്രശ്നത്തിന്റെ നിർദ്ധാരണവഴികൾ നെറ്റ്‌വർക്കിങ്, ഡി.എൻ.എ. സീക്വൻസിങ്, ഇന്റഗ്രേറ്റഡ് സർക്യൂട്ട് നിർമ്മാണം മുതലായവയിൽ ഉപയോഗിച്ചു വരുന്നു. ചോദ്യം ഇപ്രകാരമാണ് :

ഒരു കൂട്ടം നഗരങ്ങളും അവയിലോരോന്നു തമ്മിലുള്ള ദൂരവും തന്നാൽ, ഓരോ നഗരവും ഒരു തവണ മാത്രം സന്ദർശിച്ച് തിരികെ തുടങ്ങിയ നഗരത്തിലെത്താനുള്ള ഏറ്റവും ദൂരം കുറഞ്ഞ വഴിയേത്.