कुतूहल : फिरत्या विक्रेत्याची भ्रमंती

ही प्रश्नांचे उत्तर शोधण्यासाठी मर्यादित वेळ लागतो. असे प्रश्न ‘पी’ (ढ) गटात मोडतात.

एका कंपनीच्या उत्पादनाचे अनेक शहरांमध्ये वितरक आहेत. कंपनीच्या विक्रेत्याला मुख्यालयातून सुरुवात करून प्रत्येक शहराला एकदा आणि एकदाच भेट देऊन परत यायचे आहे. विक्रेत्याने प्रवासाची आखणी कशी करावी म्हणजे कमीत कमी खर्चात काम होईल? हा प्रश्न ‘फिरत्या विक्रेत्याचा प्रश्न’ (ट्रॅव्हलिंग सेल्समन प्रॉब्लेम) म्हणून ओळखला जातो आणि त्याचे योग्य उत्तर अजूनही सापडलेले नाही. योग्य उत्तर म्हणजे जे मर्यादित वेळेत काढता येईल. सर्व शक्यता तपासून पाहायच्या तर त्यांची संख्या खूप जास्त होते आणि, प्रगत संगणकावरसुद्धा, त्याला लाखो वर्षे लागू शकतील. उदा. १० शहरे असतील तर सैद्धान्तिकरीत्या १०! = १०७९ ७८ ७ . ७३ ७२ ७१, इतके पर्याय तपासावे लागतील. 

काही प्रश्नांचे उत्तर शोधण्यासाठी मर्यादित वेळ लागतो. असे प्रश्न ‘पी’ (ढ) गटात मोडतात. जसे की दिलेल्या संख्यांचा चढता क्रम लावणे. उलट काही प्रश्नांचे उत्तर दिले असेल तर, ते बरोबर आहे की नाही हे मर्यादित वेळेत तपासता येते. असे प्रश्न ‘एनपी’ (ठढ) गटात मोडतात. जसे सुडोकुचे उत्तर भरून कोष्टक पूर्ण केले तर उत्तर तपासायला फार वेळ लागत नाही. पी गट आणि एनपी गट सारखेच आहेत का हा संगणकशास्त्रातील महत्त्वाचा अनुत्तरित प्रश्न आहे; त्याच्या उत्तरासाठी एक दशलक्ष डॉलरचे बक्षीस ठेवलेले आहे. फिरत्या विक्रेत्याचा प्रश्न एनपी गटात मोडतो, पण त्यासाठी इष्टतम पद्धत मिळाली तर पी = एनपी आहे का, हे सांगता येईल.

संख्याशास्त्रज्ञ पी. सी. महालनोबीस यांनी १९३० च्या दशकात केलेले काम फिरत्या विक्रेत्याच्या प्रश्नाशी संबंधित आहे हे लोकांना फारसे माहीत नाही. बंगालमधील तागाचे उत्पादन अनेक छोट्या जमिनीच्या तुकड्यांमध्ये होत असे आणि ते मोजण्याचे काम करावे लागे. प्रथम काही तुकडे यादृच्छिक पद्धतीने निवडले जात. मग त्या सर्व तुकड्यांना भेट द्यावी लागे आणि हा प्रश्न फिरत्या विक्रेत्याच्या प्रश्नासारखाच होता. समजा १०० चौरस किमी क्षेत्रामधून ‘न’ बिंदू यादृच्छिक पद्धतीने निवडले, तर त्या सर्वांना भेट देण्यासाठी लागणारा कमीत कमी लांबीचा मार्ग केवढा असेल? सर्वात कमी लांबीचा मार्ग शोधून काढणे दुरापास्त आहे हे महालनोबीसांनी अचूक ओळखले आणि असे अनुमान केले की न ही संख्या जशी वाढत जाते तशी त्या मार्गाची लांबी साधारण न च्या वर्गमुळाच्या प्रमाणात असते. पुढे गणिती पद्धतीने हा तर्क बरोबर असल्याचे सिद्ध झाले. असे प्रश्न व्यवस्थापनशास्त्र, खगोलशास्त्र, जनुकीय ‘डीएनए’ क्रम लावणे अशा विविध क्षेत्रांत हाताळावे लागतात. – डॉ. रवींद्र बापट मराठी विज्ञान परिषद

संकेतस्थळ : www.mavipa.org      

ईमेल : office@mavipamumbai.org

Loksatta Telegram लोकसत्ता आता टेलीग्रामवर आहे. आमचं चॅनेल (@Loksatta) जॉइन करण्यासाठी येथे क्लिक करा आणि ताज्या व महत्त्वाच्या बातम्या मिळवा.

मराठीतील सर्व नवनीत बातम्या वाचा. मराठी ताज्या बातम्या (Latest Marathi News) वाचण्यासाठी डाउनलोड करा लोकसत्ताचं Marathi News App. ताज्या बातम्या (latest News) फेसबुक , ट्विटरवरही वाचता येतील.

Web Title: Wandering of the traveling seller of the company product distributors in cities akp