मार्ग समस्या र मार्किङ एल्गोरिदम प्रयोग गरेर यसलाई कसरी समाधान गर्न सकिन्छ भनेर व्याख्या गर्नुहोस्।
पथ समस्या कम्प्युटेसनल जटिलता सिद्धान्तमा एक आधारभूत समस्या हो जसमा ग्राफमा दुई शीर्षहरू बीचको बाटो खोज्नु समावेश छ। ग्राफ G = (V, E) र दुईवटा ठाउहरू s र t दिएर, लक्ष्य G मा s बाट t सम्मको बाटो अवस्थित छ कि छैन भनेर निर्धारण गर्नु हो।
मार्ग समस्या समाधान गर्न, एउटा दृष्टिकोण मार्किंग एल्गोरिथ्म प्रयोग गर्नु हो। मार्किङ एल्गोरिथ्म एउटा सरल र प्रभावकारी प्रविधि हो जुन ग्राफमा दुईवटा ठाडोहरू बीच बाटो अवस्थित छ कि छैन भनेर निर्धारण गर्न प्रयोग गर्न सकिन्छ।
निम्नानुसार एल्गोरिथ्म काम गर्दछ:
1. शुरुवात vertex s लाई भ्रमण गरिएको रूपमा चिन्ह लगाउनुहोस्।
2. s को छेउमा रहेको प्रत्येक vertex v को लागि, v लाई भ्रमण गरिएको भनी चिन्ह लगाउनुहोस् र यसलाई लाममा थप्नुहोस्।
3. जब लाम खाली छैन, निम्न चरणहरू दोहोर्याउनुहोस्:
a लामबाट vertex u हटाउनुहोस्।
b यदि u लक्ष्य vertex t हो, तब s बाट t सम्मको बाटो फेला परेको छ।
ग अन्यथा, भ्रमण नगरिएको u को छेउमा रहेको v को लागि, v लाई भ्रमण गरिएको भनी चिन्ह लगाउनुहोस् र यसलाई लाममा थप्नुहोस्।
मार्किङ एल्गोरिथ्मले ग्राफको अन्वेषण गर्न र भ्रमण गरिएको ठाँउहरूलाई चिन्ह लगाउन चौडाइ-पहिलो खोज (BFS) ट्र्याभर्सल रणनीति प्रयोग गर्दछ। त्यसो गरेर, यसले एल्गोरिथ्मलाई सुरुवात र लक्षित vertices बीचको बाटो अवस्थित छ कि छैन भनी निर्धारण गर्न अनुमति दिँदै, प्रारम्भिक भेर्टेक्सबाट पुग्न सकिने प्रत्येक भेर्टेक्स भ्रमण गरिएको सुनिश्चित गर्दछ।
मार्किङ एल्गोरिदमको समय जटिलता O(|V| + |E|), जहाँ |V| ग्राफ र |E| मा ठाडो संख्या हो किनाराहरूको संख्या हो। यो किनभने एल्गोरिथ्मले प्रत्येक शीर्ष र प्रत्येक किनारामा एक पटक भ्रमण गर्दछ। कम्प्युटेशनल जटिलता सिद्धान्तको सन्दर्भमा, मार्किंग एल्गोरिदम वर्ग P मा पर्दछ, जसले बहुपद समयमा समाधान गर्न सकिने समस्याहरूलाई प्रतिनिधित्व गर्दछ।
मार्किङ एल्गोरिथ्मको प्रयोगलाई चित्रण गर्न यहाँ एउटा उदाहरण छ:
निम्न ग्राफलाई विचार गर्नुहोस्:
A --- B --- C | | D --- E --- F
मानौं कि हामी vertex A देखि vertex F सम्मको बाटो छ कि छैन भनेर निर्धारण गर्न चाहन्छौं। हामी निम्नानुसार मार्किङ एल्गोरिदम प्रयोग गर्न सक्छौं:
1. vertex A लाई भ्रमण गरिएको भनी चिन्ह लगाएर सुरु गर्नुहोस्।
2. लाममा vertex A थप्नुहोस्।
3. लामबाट vertex A हटाउनुहोस्।
4. भर्टेक्स B लाई भ्रमण गरिएको भनी चिन्ह लगाउनुहोस् र यसलाई लाममा थप्नुहोस्।
5. लामबाट vertex B हटाउनुहोस्।
6. vertex C लाई भ्रमण गरिएको भनी चिन्ह लगाउनुहोस् र यसलाई लाममा थप्नुहोस्।
7. लामबाट vertex C हटाउनुहोस्।
8. भर्टेक्स D लाई भ्रमण गरिएको भनी चिन्ह लगाउनुहोस् र यसलाई लाममा थप्नुहोस्।
9. लामबाट vertex D हटाउनुहोस्।
10. vertex E लाई भ्रमण गरिएको भनी चिन्ह लगाउनुहोस् र यसलाई लाममा थप्नुहोस्।
11. लामबाट vertex E हटाउनुहोस्।
12. भर्टेक्स F लाई भ्रमण गरिएको रूपमा चिन्ह लगाउनुहोस्।
13. भेर्टेक्स F लक्ष्य भेर्टेक्स भएकोले, A देखि F सम्मको बाटो फेला परेको छ।
यस उदाहरणमा, मार्किङ एल्गोरिदमले vertex A देखि vertex F सम्मको बाटो छ भनी सफलतापूर्वक निर्धारण गर्छ।
कम्प्युटेसनल जटिलता सिद्धान्तमा पथ समस्याले ग्राफमा दुईवटा ठाडोहरू बीचको बाटो खोज्नु समावेश गर्दछ। मार्किङ एल्गोरिदम एक सरल र प्रभावकारी प्रविधि हो जुन यो समस्या समाधान गर्न प्रयोग गर्न सकिन्छ चौडाइ-पहिलो खोज ट्र्याभर्सल प्रदर्शन गरेर र भ्रमण गरिएको रूपमा ठाडो चिन्हहरू। एल्गोरिथ्ममा O(|V| + |E|) को समय जटिलता छ र P वर्गसँग सम्बन्धित छ।
अन्य भर्खरका प्रश्न र उत्तरहरू सम्बन्धमा जटिलता:
- के PSPACE वर्ग EXPSPACE वर्गको बराबर छैन?
- के P जटिलता वर्ग PSPACE वर्गको उपसमूह हो?
- के हामी एक निश्चित TM मा कुनै पनि NP पूर्ण समस्याको लागि एक कुशल बहुपद समाधान खोजेर Np र P वर्ग समान छन् भनेर प्रमाणित गर्न सक्छौं?
- के NP वर्ग EXPTIME कक्षा बराबर हुन सक्छ?
- के PSPACE मा समस्याहरू छन् जसको लागि कुनै ज्ञात NP एल्गोरिथ्म छैन?
- के एक SAT समस्या NP पूर्ण समस्या हुन सक्छ?
- के NP जटिलता वर्गमा समस्या हुन सक्छ यदि त्यहाँ एक गैर-निर्धारित ट्युरिङ मेसिन छ जसले यसलाई बहुपद समयमा समाधान गर्नेछ।
- NP बहुपदीय समय प्रमाणिकरण भएका भाषाहरूको वर्ग हो
- के P र NP वास्तवमा एउटै जटिलता वर्ग हो?
- के प्रत्येक सन्दर्भ मुक्त भाषा P जटिलता वर्गमा छ?
जटिलतामा थप प्रश्न र उत्तरहरू हेर्नुहोस्