Prune and search
ಪ್ರೂನ್ ಮತ್ತು ಸರ್ಚ್ ಎಂಬುದು 1983 ರಲ್ಲಿ ನಿಮ್ರೋಡ್ ಮೆಗಿಡ್ಡೊ ಸೂಚಿಸಿದ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವ ಒಂದು ವಿಧಾನವಾಗಿದೆ. ವಿಧಾನದ ಮೂಲ ಕಲ್ಪನೆಯು ಪುನರಾವರ್ತಿತ ವಿಧಾನವಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಇನ್ಪುಟ್ ಗಾತ್ರವನ್ನು ಸ್ಥಿರ ಅಂಶದಿಂದ ಕಡಿಮೆ ಮಾಡಲಾಗುತ್ತದೆ ("ಕತ್ತರಿಸಲಾಗುತ್ತದೆ"). ಅಂತೆಯೇ, ಇದು ಇಳಿಕೆ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ ಅಲ್ಗಾರಿದಮ್ನ ಒಂದು ರೂಪವಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಇಳಿಕೆಯು ಸ್ಥಿರ ಅಂಶವಾಗಿರುತ್ತದೆ. ಇನ್ಪುಟ್ ಗಾತ್ರವಾಗಿರಲಿ, ಇಡೀ ಸಮರುವಿಕೆಯನ್ನು ಮತ್ತು ಹುಡುಕಾಟ ಕ್ರಮಾವಳಿಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆ ಆಗಿರಲಿ, ಮತ್ತು ಸಮರುವಿಕೆಯ ಹಂತದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿರಲಿ. ನಂತರ ಈ ಕೆಳಗಿನ ಪುನರಾವರ್ತಿತ ಸಂಬಂಧವನ್ನು ಅನುಸರಿಸುತ್ತದೆಃ ಇದು ಬೈನರಿ ಹುಡುಕಾಟದ ಪುನರಾವರ್ತನೆಯನ್ನು ಹೋಲುತ್ತದೆ ಆದರೆ ಬೈನರಿ ಹುಡುಕಾಟದ ಸ್ಥಿರ ಪದಕ್ಕಿಂತ ದೊಡ್ಡ ಪದವನ್ನು ಹೊಂದಿದೆ. ಪ್ರೂನ್ ಮತ್ತು ಸರ್ಚ್ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಎಸ್ (ಎನ್) ಸಾಮಾನ್ಯವಾಗಿ ಕನಿಷ್ಠ ರೇಖೀಯವಾಗಿರುತ್ತದೆ (ಏಕೆಂದರೆ ಸಂಪೂರ್ಣ ಇನ್ಪುಟ್ ಅನ್ನು ಸಂಸ್ಕರಿಸಬೇಕು). ಈ ಊಹೆಯೊಂದಿಗೆ, ಪುನರಾವರ್ತನೆಯು ಪರಿಹಾರವನ್ನು ಹೊಂದಿದೆ. ವಿಭಜನೆ-ಮತ್ತು-ವಶಪಡಿಸಿಕೊಳ್ಳುವ ಪುನರಾವರ್ತನೆಗಳಿಗೆ ಮುಖ್ಯ ಪ್ರಮೇಯವನ್ನು ಅನ್ವಯಿಸುವ ಮೂಲಕ ಅಥವಾ ಜ್ಯಾಮಿತೀಯ ಸರಣಿಯಲ್ಲಿ ಪುನರಾವರ್ತಿತ ಉಪ-ಸಮಸ್ಯೆಗಳ ಸಮಯವು ಕಡಿಮೆಯಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸುವುದರ ಮೂಲಕ ಇದನ್ನು ಕಾಣಬಹುದು. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಮೆಗಿಡ್ಡೊ ಸ್ವತಃ ಈ ವಿಧಾನವನ್ನು ತನ್ನ ರೇಖೀಯ ಸಮಯ ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಾಗಿ ಆಯಾಮವನ್ನು ನಿಗದಿಪಡಿಸಿದಾಗ ಮತ್ತು ಬಾಹ್ಯಾಕಾಶದಲ್ಲಿನ ಬಿಂದುಗಳ ಗುಂಪಿಗೆ ಕನಿಷ್ಠ ಸುತ್ತುವರಿದ ಗೋಳದ ಸಮಸ್ಯೆಗಾಗಿ ಬಳಸಿದರು. ಉಲ್ಲೇಖಗಳು ಜ್ಯಾಮಿತೀಯ ಕ್ರಮಾವಳಿಗಳು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್