శాస్త్ర విజ్ఞానము

పార్వతమ్మగారి అమ్మాయి పెళ్లి పిలుపుల సమస్య

పార్వతమ్మకి ఓ పెద్ద ఇక్కట్టు నెత్తిన పడింది. టీ.సీ.యస్. లో పని చేస్తున్న వాళ్ళ అమ్మాయి రేఖకి పెళ్లి కుదిరింది. రెండు రోజుల్లో పెళ్ళి, మూడో రోజు రిసెప్షన్. కనుక ఈ రోజు పెళ్లి పిలుపులు, రేపు షాపింగ్! భర్త పరంధామయ్య యూనివర్సిటీలో ఫిలాసఫీ  ప్రొఫెసరు. ఇంట్లో ఏం జరుగుతోందో ఏమీ పట్టించుకోడు. అన్నీ ఈవిడే నెత్తిన వేసుకుని చెయ్యాలి. ఒక్క రోజులో ఇంచుమించు యాభై మంది ఇళ్ళకి వెళ్లి శుభలేఖలు పంచాలి. అంతా ఒక్క చోట ఉంటే బావుణ్ణు.  షంసా బాద్ నుండి  ఆల్వాల్ దాకా,  కుక్కట్ పల్లి నుండి  ఉప్పల్ దాకా కుప్పలుతెప్పలుగా ఉన్నారు బంధువులు. ముందు మెహదీపట్నం తో మొదలు పెట్టి, జూబిలీ హిల్స్  మీదుగా సనత్ నగర్ కి వెళ్లి, అక్కణ్ణుంచి  బాలానగర్ కి వెళ్లడమా? లేక ముందు బహదూర్ గుడా కి వెళ్లి, దార్లో లక్ష్మీ గూడాకి కూడా  వెళ్లి, షంసాబాద్ కి వెళ్లడమా? ఏది మేలైన పద్ధతి? ఈ ఇళ్ళన్నీ చుట్టి సాయంకాలానికి ఇంటికి చేరాలంటే అతి దగ్గరి దారి ఏంటి? ఆలోచిస్తుంటే తల వేడెక్కిపోతోంది. “నా వల్ల కాదు రేఖా! మీ నాన్నగారేమో ఏవీ పట్టించుకోరు. నీ పెళ్లిపిలుపులేవో నువ్వే చూసుకో” అంటూ కూతురికి ఫోన్ చేసి చెప్పేసింది. కాని రేఖకి ఆ రోజు లీవ్ దొరకలేదు. ఎలాగోలా ఓపిక చేసుకుని ఆ పని అమ్మే చెయ్యాలి. తల్లితో ప్రాధేయపడుతున్నట్టుగా అంది. “అయ్యో అమ్మా! ఈ సమస్య నాకు వదిలేయ్. నువ్వు చెప్తున్నది సామాన్యమైన సమస్య కాదు. అదో ముఖ్యమైన గణిత సమస్య. కంప్యూటర్ సైన్స్ సమస్య. ఒక్క అరగంట టైమివ్వు. ఏం చెయ్యాలో చెప్తాను,” అంటూ గూగుల్ మ్యాప్ ల నుండి ఏవేవో కొలతలు తీసుకుని, ఆ సమాచారం అంతా ఏదో సాఫ్ట్ వేర్ లోకి ఫీడ్ చేసి అరగంటలో పరిష్కారం కనుక్కుని తల్లికి  ఫోన్ చేసి చెప్పింది. ఆమె చెప్పిన క్రమంలోనే బంధుమిత్రుల ఇళ్ళన్నీ సందర్శించి సాయంత్రంలోపు పని పూర్తి చేసింది పార్వతమ్మ.

పార్వతమ్మ ఎదుర్కున్న సమస్య సైద్ధాంతిక కంప్యూటర్ సైన్స్ లో ముఖ్యమైన సమస్య. దీన్నే ట్రావెలింగ్ సేల్స్ మాన్ ప్రాబ్లమ్ (ప్రయాణించే సేల్స్ మాన్ సమస్య) అంటారు. ఇందులో ఓ సేల్స్ మన్ కొన్ని ఊళ్లు చుట్టి రావాలి. ఒకే ఊరికి రెండు సార్లు వెళ్ళకూడదు. అన్ని ఊళ్లూ తిరగాలి. మొత్తం చుట్టి రావడానికి పట్టే ఖర్చు కనీసమాత్రంగా ఉండాలి. ఈ సమస్య కనిపించినంత సులభం కాదు. ముఖ్యంగా ఊళ్ల సంఖ్య పెరుగుతుంటే సమస్య మరింత జటిలం అవుతుంది. ఎందుకంటే ఈ సమస్యని పరిష్కరించాలంటే ఎన్నో మార్గాలని పరిశీలించాలి. ప్రతీ మార్గానికి పట్టే ఖర్చు అంచనా వెయ్యాలి. ఊళ్ళ సంఖ్య పెరుగుతుంటే మార్గాల సంఖ్య విపరీతంగా పెరిగిపోతుంది.

 

ఉదాహరణకి 5 ఊళ్లు ఉన్నాయనుకుందాం. ఐదింట్లో ఏదో ఒక దాని నుండి బయలుదేరొచ్చు. అక్కణ్నుంచి మిగతా 4 ఊళ్లలో ఏదో ఒక దాన్ని సందర్శించొచ్చు. ఆ 4 ఊళ్లలో ఒక్కొక్క దాని నుండి మూడేసి ఊళ్లు సందర్శించొచ్చు. అలా లెక్క  వేస్తూ పోతే మొత్తం 5 X 4 X 3 X 2 X 1 = 120  మార్గాలని, అంటే మార్గాంతరాలని పరిగణించాల్సి ఉంటుంది. ఇంకా సామాన్యంగా n ఊళ్లు ఉన్న సమస్యలో మొత్తం n! మార్గాంతరాలు ఉంటాయి. n విలువ పెరుగుతుంటే ఈ n! విలువ చాలా వేగంగా పెరిగిపోతుంది. ఇక పార్వతమ్మ గారి సమస్యలో యాభై ఇళ్ళు ఉన్నాయి కనుక 50! విలువ రమారమి 3X 10⁶⁴ అవుతుంది. ఒక్కొక్క మార్గాంతరాన్ని పరిశీలించడానికి సెకనులో వెయ్యోవంతు కాలం పట్టినా మొత్తం అన్ని మార్గాంతరాలని పరిశీలించడానికి, మన ఆయుర్దాయం మాట అటుంచితే, ఈ విశ్వం ఆయుర్దాయమే సరిపోకపోవచ్చు.

ఈ ట్రావెలింగ్ సేల్స్ మన్ సమస్యని మొట్టమొదట నిర్వచించినవాడు ఐర్లాండ్ కి చెందిన హామిల్టన్ అనే గొప్ప గణితవేత్త. ఇరవయ్యవ శాతాబ్దపు మొదటి దశల్లో కార్ల్ మెంగర్ అనే గణితవేత్త దీన్ని పరిశీలించాడు. ఉన్న ఊరి నుండి కేవలం అతి దగ్గరి ఊరికి ప్రయాణిస్తూ పోయినంత మాత్రాన కనిష్ఠ మార్గం దొరుకుతుందని భరోసా లేదని ఇతడు నిరూపించాడు. 1950, 1960 లలో డాంట్ జిగ్, ఫుల్కర్సన్, జాన్సన్ వంటి వారు దీన్ని పరిశీలించి, ‘లీనియర్ ప్రోగ్రామింగ్’ అనే రంగంలో దీనినొక ప్రత్యేక సమస్యగా గుర్తించి, 49 ఊళ్ళున్న ఓ ప్రత్యేక సమస్యని కచ్చితంగా పరిష్కరించారు. తదనంతరం 1972 లో రిచర్డ్ కార్ప్ అనే గణితవేత్త ఈ సమస్యని ‘ఎన్.పి-కంప్లీట్’ అనే కోవకి చెందిన అతి కఠినమైన సమస్యల్లో ఒకటిగా గుర్తించాడు. దాంతో ఈ సమస్య ఎందుకంత కఠినమైనదో అర్థమయ్యింది.

ఈ ప్రయాణించే సేల్స్ మన్ సమస్య అతి కఠినమైనదే అయినా, కొన్ని ప్రత్యేక సందర్భాలలో దీన్ని కచ్చితంగా పరిష్కరించడానికి వీలయ్యింది. పైగా సూపర్  కంప్యూటర్ల వినియోగం పెరిగాక పెద్ద సంఖ్యలో ఊళ్లున్న సమస్యల్ని కూడా ఛేదించడానికి వీలయ్యింది.  1970, 1980 లలో గ్రోట్షెల్, పాడ్బర్గ్ తదితరులు 2,392 ఊళ్ళున్న సమస్యని పరిష్కరించారు. 2005 లో కుక్ అనే గణితవేత్త 33,810 ఊళ్లున్న సమస్యని పరిష్కరించాడు. ఆ పరిష్కారాన్ని గణించడానికి 15.7 సంవత్సరాల సీ.పీ.యు. సమయం అవసరమయ్యింది! 

ప్రయాణించే సేల్స్ మన్ సమస్య కేవలం ఒక ప్రత్యేక సమస్య కాదు. ఒక ప్రత్యేక కోవకి చెందిన సమస్యలకి అదొక చిహ్నం మాత్రమే. కనుక ఈ ప్రత్యేక సమస్యని పరిష్కరిస్తే, ఆ కోవకి చెందిన సమస్యలన్నీ పరిష్కరించినట్టే. కాల్ టాక్సీల  కార్యక్రమాలకి ఈ ప్రయాణించే సేల్స్ మన్ సమస్యతో సంబంధం ఉంది. వి.ఎల్. ఎస్. ఐ. చిప్ ల డిజైన్ లో కూడా ఈ పరిష్కారం ఎన్నో సందర్భాల్లో ఉపయోగపడుతుంది. కమ్యూనికేషన్ నెట్వర్క్ లలోను, కంప్యూటర్ నెట్వర్క్ లలో కూడా దీని వల్ల ఎన్నో ఉపయోగాలు ఉన్నాయి. ఒక్క గణిత సమస్య యొక్క పరిష్కారానికి దైనిక జీవితంలో ఎన్నో ఉపయోగాలు ఉండొచ్చునని చెప్పడానికి ఈ ప్రయాణించే సేల్స్ మన్ సమస్య ఓ చక్కని తార్కాణం.