Reverse-search algorithm
ರಿವರ್ಸ್-ಸರ್ಚ್ ಕ್ರಮಾವಳಿಗಳು ನಿರ್ದಿಷ್ಟ ಗಾತ್ರದ ಎಲ್ಲಾ ವಸ್ತುಗಳನ್ನು, ಕೆಲವು ವರ್ಗದ ಸಂಯೋಜಿತ ವಸ್ತುಗಳಿಂದ ಉತ್ಪಾದಿಸುವ ಕ್ರಮಾವಳಿಗಳ ಒಂದು ವರ್ಗವಾಗಿದೆ. ಅನೇಕ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಈ ವಿಧಾನಗಳು ಪ್ರತಿ ವಸ್ತುವಿಗೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ವಸ್ತುಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತವೆ, ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ವಸ್ತುಗಳನ್ನು (ಬಹುಪದ ಸ್ಥಳ) ಸಂಗ್ರಹಿಸಲು ಸಾಕಷ್ಟು ಸ್ಮರಣೆಯನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತವೆ. (ಆದಾಗ್ಯೂ, ಸಾಮಾನ್ಯವಾಗಿ, ಅವುಗಳನ್ನು ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಗಳೆಂದು ವರ್ಗೀಕರಿಸಲಾಗುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ಅವು ಉತ್ಪಾದಿಸುವ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಘಾತೀಯವಾಗಿರುತ್ತದೆ.) ಅವರು ತಮ್ಮ ರಾಜ್ಯದ ಪ್ರದೇಶದ ವಿಸ್ತಾರವಾದ ಮರದಲ್ಲಿ ಉತ್ಪಾದಿಸಬೇಕಾದ ವಸ್ತುಗಳನ್ನು ಸಂಘಟಿಸುವ ಮೂಲಕ ಕೆಲಸ ಮಾಡುತ್ತಾರೆ ಮತ್ತು ನಂತರ ಈ ಮರದ ಆಳವಾದ-ಮೊದಲ ಹುಡುಕಾಟವನ್ನು ಮಾಡುತ್ತಾರೆ. ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ಗಳ ಶೃಂಗಗಳನ್ನು ಮತ್ತು ಹೈಪರ್ ಪ್ಲೇನ್ಗಳ ಜೋಡಣೆಯ ಕೋಶಗಳನ್ನು ಉತ್ಪಾದಿಸುವ ಸಮಸ್ಯೆಗಳಿಗಾಗಿ ಡೇವಿಡ್ ಅವಿಸ್ ಮತ್ತು ಕೊಮೈ ಫುಕುಡಾ ಅವರು 1991ರಲ್ಲಿ ರಿವರ್ಸ್-ಸರ್ಚ್ ಕ್ರಮಾವಳಿಗಳನ್ನು ಪರಿಚಯಿಸಿದರು. ಅವುಗಳನ್ನು 1996 ರಲ್ಲಿ ಅವಿಸ್ ಮತ್ತು ಫುಕುಡಾ ಅವರು ಹೆಚ್ಚು ವಿಶಾಲವಾಗಿ ಔಪಚಾರಿಕಗೊಳಿಸಿದರು. ತತ್ವಗಳು ರಿವರ್ಸ್-ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಸ್ಥಿತಿಯ ಜಾಗದಲ್ಲಿ ಸಂಯೋಜಿತ ವಸ್ತುಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ, ಒಂದು ಸೂಚ್ಯ ಗ್ರಾಫ್, ಅದರ ಶೃಂಗಗಳು ಪಟ್ಟಿ ಮಾಡಬೇಕಾದ ವಸ್ತುಗಳು ಮತ್ತು ಅದರ ಅಂಚುಗಳು ಕೆಲವು "ಸ್ಥಳೀಯ ಚಲನೆಗಳನ್ನು" ಪ್ರತಿನಿಧಿಸುತ್ತವೆ, ಸಾಮಾನ್ಯವಾಗಿ ಅವುಗಳ ರಚನೆಯಲ್ಲಿ ಸಣ್ಣ ಬದಲಾವಣೆಗಳನ್ನು ಮಾಡುತ್ತವೆ. ಈ ಕೆಳಗಿನ ಮಾಹಿತಿಯಿಂದ ವಿವರಿಸಲಾದ ಈ ಸ್ಥಿತಿಯ ವಿಸ್ತಾರವಾದ ಮರದಲ್ಲಿ ಆಳವಾದ-ಮೊದಲ ಹುಡುಕಾಟವನ್ನು ಬಳಸಿಕೊಂಡು ಇದು ಪ್ರತಿಯೊಂದು ವಸ್ತುವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆಃ ವಿಸ್ತಾರವಾದ ಮರದ ಮೂಲ, ವಸ್ತುಗಳಲ್ಲಿ ಒಂದು ಮರದಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ವಸ್ತುವಿನ ಮೂಲವನ್ನು ಉತ್ಪಾದಿಸಲು ಎ ಸಬ್ರುಟೈನ್, ಸಾಕಷ್ಟು ಬಾರಿ ಪುನರಾವರ್ತಿಸಿದರೆ ಅದು ಅಂತಿಮವಾಗಿ ಮೂಲವನ್ನು ತಲುಪುತ್ತದೆ ಎಂಬ ಆಸ್ತಿಯೊಂದಿಗೆ ರಾಜ್ಯದ ಎಲ್ಲಾ ನೆರೆಹೊರೆಯವರನ್ನು ಪಟ್ಟಿ ಮಾಡಲು ಎ ಸಬ್ರುಟೈನ್ (ಎಲ್ಲರೂ ಮರದಲ್ಲಿ ನೆರೆಹೊರೆಯವರಾಗಿರಬಾರದು) ಈ ಮಾಹಿತಿಯಿಂದ ಮರದಲ್ಲಿ ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ನೋಡ್ನ ಮಕ್ಕಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಿದೆ, ಮೂಲ ಸಬ್ರುಟೈನ್ ನೀಡಿದ ಕೊಂಡಿಗಳನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುತ್ತದೆಃ ಅವರು ಕೇವಲ ನೆರೆಹೊರೆಯವರ ಪೋಷಕರು ನೀಡಿದ ನೋಡ್. ಚೈಲ್ಡ್ ನೋಡ್ಗಳಿಗೆ ಈ ಹಿಮ್ಮುಖ ಕೊಂಡಿಗಳನ್ನು ಅಲ್ಗಾರಿದಮ್ ಹುಡುಕುತ್ತದೆ. ಈ ವಿಸ್ತಾರವಾದ ಮರದ ಶಾಸ್ತ್ರೀಯ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟವು ಮರವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಹಾದುಹೋಗುತ್ತದೆ, ಮೂಲದಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಪ್ರತಿ ನೋಡ್ನಲ್ಲಿ ಎಲ್ಲಾ ಮಕ್ಕಳನ್ನು ಪಟ್ಟಿ ಮಾಡುತ್ತದೆ ಮತ್ತು ಪ್ರತಿಯೊಂದಕ್ಕೂ ಪುನರಾವರ್ತಿತ ಕರೆ ಮಾಡುತ್ತದೆ. ಚಕ್ರಗಳೊಂದಿಗಿನ ರೇಖಾಚಿತ್ರದ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟಕ್ಕಿಂತ ಭಿನ್ನವಾಗಿ, ಪುನರಾವರ್ತಿತ ಭೇಟಿಗಳನ್ನು ತಪ್ಪಿಸಲು ಈಗಾಗಲೇ ಭೇಟಿ ನೀಡಿದ ನೋಡ್ಗಳ ಗುಂಪನ್ನು ನಿರ್ವಹಿಸುವ ಅಗತ್ಯವಿಲ್ಲ; ಅಂತಹ ಪುನರಾವರ್ತನೆ ಮರದಲ್ಲಿ ಸಾಧ್ಯವಿಲ್ಲ. ಆದಾಗ್ಯೂ, ಮರವು ತುಂಬಾ ಆಳವಾದ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಈ ಪುನರಾವರ್ತಿತ ಅಲ್ಗಾರಿದಮ್ಗೆ ಅದರ ಕರೆ ಸ್ಟ್ಯಾಕ್ಗೆ ಇನ್ನೂ ಹೆಚ್ಚಿನ ಪ್ರಮಾಣದ ಮೆಮೊರಿಯ ಅಗತ್ಯವಿರುತ್ತದೆ. ಬದಲಾಗಿ, ರಿವರ್ಸ್ ಸರ್ಚ್ ಎರಡು ವಸ್ತುಗಳನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸುವಾಗ ಒಂದೇ ಕ್ರಮದಲ್ಲಿ ವ್ಯಾಪಿಸಿರುವ ಮರವನ್ನು ಹಾದುಹೋಗುತ್ತದೆಃ ಚಲಿಸುವ ವಸ್ತುವಿನ ಪ್ರಸ್ತುತ ವಸ್ತು ಮತ್ತು ಹಿಂದೆ ಚಲಿಸಿದ ವಸ್ತು. ಆರಂಭದಲ್ಲಿ, ಪ್ರಸ್ತುತ ವಸ್ತುವನ್ನು ಮರದ ಮೂಲಕ್ಕೆ ಹೊಂದಿಸಲಾಗಿದೆ, ಮತ್ತು ಯಾವುದೇ ಹಿಂದಿನ ವಸ್ತು ಇಲ್ಲ. ಈ ಮಾಹಿತಿಯಿಂದ, ಈ ಕೆಳಗಿನ ಪ್ರಕರಣ ವಿಶ್ಲೇಷಣೆಯ ಮೂಲಕ ಚಲಿಸುವಿಕೆಯ ಮುಂದಿನ ಹಂತವನ್ನು ನಿರ್ಧರಿಸಲು ಸಾಧ್ಯವಿದೆಃ ಯಾವುದೇ ಹಿಂದಿನ ವಸ್ತು ಇಲ್ಲದಿದ್ದರೆ, ಅಥವಾ ಹಿಂದಿನ ವಸ್ತುವು ಪ್ರಸ್ತುತ ವಸ್ತುವಿನ ಪೋಷಕನಾಗಿದ್ದರೆ, ಚಲಿಸುವಿಕೆಯು ಪ್ರಸ್ತುತ ವಸ್ತುವನ್ನು ತಲುಪಿರುವುದು ಇದೇ ಮೊದಲು, ಆದ್ದರಿಂದ ಇದು ಹುಡುಕಾಟದ ಔಟ್ಪುಟ್ ಆಗಿದೆ. ಮುಂದಿನ ವಸ್ತುವು ಅದರ ಮೊದಲ ಮಗು ಅಥವಾ, ಅದು ಮಕ್ಕಳಿಲ್ಲದಿದ್ದರೆ, ಅದರ ಪೋಷಕರು. ಇತರ ಎಲ್ಲಾ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಹಿಂದಿನ ವಸ್ತುವು ಪ್ರಸ್ತುತ ವಸ್ತುವಿನ ಚೈಲ್ಡ್ ಆಗಿರಬೇಕು. ಅಲ್ಗಾರಿದಮ್ ಈ ಹಿಂದಿನ ಮಗುವನ್ನು ತಲುಪುವವರೆಗೆ ಮಕ್ಕಳನ್ನು (ಅಂದರೆ, ಪ್ರಸ್ತುತ ವಸ್ತುವನ್ನು ಅವರ ಪೋಷಕರಾಗಿ ಹೊಂದಿರುವ ಪ್ರಸ್ತುತ ವಸ್ತುವಿನ ರಾಜ್ಯ-ಬಾಹ್ಯಾಕಾಶ ನೆರೆಹೊರೆಯವರು) ಒಂದು ಸಮಯದಲ್ಲಿ ಪಟ್ಟಿ ಮಾಡುತ್ತದೆ, ಮತ್ತು ನಂತರ ಮಕ್ಕಳ ಈ ಪಟ್ಟಿಯಲ್ಲಿ ಇನ್ನೂ ಒಂದು ಹೆಜ್ಜೆ ಇಡುತ್ತದೆ. ಈ ರೀತಿಯಲ್ಲಿ ಮತ್ತೊಂದು ಮಗು ಕಂಡುಬಂದರೆ, ಅದು ಮುಂದಿನ ವಸ್ತುವಾಗಿದೆ. ಮುಂದಿನ ಚೈಲ್ಡ್ ಇಲ್ಲದಿದ್ದರೆ ಮತ್ತು ಪ್ರಸ್ತುತ ವಸ್ತುವು ಮೂಲವಾಗಿರದಿದ್ದರೆ, ಮುಂದಿನ ವಸ್ತುವು ಪ್ರಸ್ತುತ ವಸ್ತುವಿನ ಪೋಷಕವಾಗಿರುತ್ತದೆ. ಉಳಿದ ಸಂದರ್ಭದಲ್ಲಿ, ಮುಂದಿನ ಚೈಲ್ಡ್ ಇಲ್ಲದಿದ್ದಾಗ ಮತ್ತು ಪ್ರಸ್ತುತ ವಸ್ತುವು ಮೂಲವಾಗಿದ್ದಾಗ, ರಿವರ್ಸ್ ಸರ್ಚ್ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ಹುಡುಕಾಟದ ಪ್ರತಿ ಹಂತಕ್ಕೂ ಒಂದು ವಸ್ತುವಿನ ನೆರೆಹೊರೆಯವರನ್ನು ಒಮ್ಮೆ ಪಟ್ಟಿ ಮಾಡುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಪಟ್ಟಿ ಮಾಡಬೇಕಾದ ವಸ್ತುಗಳು ಇದ್ದರೆ, ಹುಡುಕಾಟವು ಹಂತಗಳನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ, ಆದ್ದರಿಂದ ವಸ್ತುಗಳ ನೆರೆಹೊರೆಯವರನ್ನು ಅದು ಎಷ್ಟು ಬಾರಿ ಉತ್ಪಾದಿಸುತ್ತದೆ ಎಂಬುದು ಪುನರಾವರ್ತಿತ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟವು ಅದೇ ಕೆಲಸವನ್ನು ಎಷ್ಟು ಬಾರಿ ಮಾಡುತ್ತದೆ ಎಂಬುದರ ಎರಡು ಅಂಶಗಳೊಳಗೆ ಇರುತ್ತದೆ. ಅನ್ವಯಿಕೆಗಳು ರಿವರ್ಸ್ ಸರ್ಚ್ ಅನ್ನು ಅನ್ವಯಿಸಲಾಗಿರುವ ಸಮಸ್ಯೆಗಳ ಉದಾಹರಣೆಗಳಲ್ಲಿ ಈ ಕೆಳಗಿನ ಸಂಯೋಜಿತ ಪೀಳಿಗೆಯ ಸಮಸ್ಯೆಗಳು ಸೇರಿವೆಃ ಸರಳ ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ಗಳ ಶೃಂಗಗಳು ಒಂದು-ಆಯಾಮದ ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ ಅನ್ನು ಅರ್ಧ-ಸ್ಥಳಗಳ ಛೇದಕ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಿದರೆ, ಅದರ ಶೃಂಗಗಳನ್ನು ಅರ್ಧ-ಸ್ಥಳಗಳನ್ನು ಸುತ್ತುವರಿದ ಹೆಚ್ಚಿನ ಹೈಪರ್ ಪ್ಲೇನ್ಗಳ ಛೇದಕ ಬಿಂದುಗಳು ಎಂದು ವಿವರಿಸಬಹುದು; ಯಾವುದೇ ಶೃಂಗವು ಈ ಹೈಪರ್ ಪ್ಲೇನ್ಗಳಿಗಿಂತ ಹೆಚ್ಚಿನವುಗಳ ಛೇದಕವಾಗಿರದಿದ್ದರೆ ಅದು ಸರಳವಾದ ಪಾಲಿಟೋಪ್ ಆಗಿದೆ. ಶೃಂಗ ಗಣನೆಯ ಸಮಸ್ಯೆಯು ಈ ಎಲ್ಲಾ ಶೃಂಗಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಪಾಲಿಟೋಪ್ನ ಅಂಚುಗಳು ಸಾಮಾನ್ಯ ಹೈಪರ್ ಪ್ಲೇನ್ಗಳನ್ನು ಹೊಂದಿರುವ ಶೃಂಗಗಳ ಜೋಡಿಗಳನ್ನು ಸಂಪರ್ಕಿಸುತ್ತವೆ, ಆದ್ದರಿಂದ ಶೃಂಗಗಳು ಮತ್ತು ಅಂಚುಗಳು ಪ್ರತಿ ಶೃಂಗವು ನೆರೆಹೊರೆಯನ್ನು ಹೊಂದಿರುವ ಸ್ಥಿತಿ ಜಾಗವನ್ನು ರೂಪಿಸುತ್ತವೆ. ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಿದ್ಧಾಂತದ ಸಿಂಪ್ಲೆಕ್ಸ್ ಅಲ್ಗಾರಿದಮ್ ನಿರ್ದೇಶಾಂಕಗಳ ನಿರ್ದಿಷ್ಟ ರೇಖೀಯ ಕಾರ್ಯವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವ ಶೃಂಗವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ, ಶೃಂಗದಿಂದ ಶೃಂಗಕ್ಕೆ ನಡೆಯುವ ಮೂಲಕ, ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಕಾರ್ಯದ ಹೆಚ್ಚಿನ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ; "ಪಿವೋಟ್ ನಿಯಮ" ದ ಹಲವಾರು ಪ್ರಮಾಣಿತ ಆಯ್ಕೆಗಳಿವೆ, ಅದು ಯಾವ ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡಬೇಕೆಂದು ಹೆಚ್ಚು ನಿಖರವಾಗಿ ಸೂಚಿಸುತ್ತದೆ. ಅಂತಹ ಯಾವುದೇ ಪಿವೋಟ್ ನಿಯಮವನ್ನು ಪಾಲಿಟೋಪ್ನ ವಿಸ್ತಾರವಾದ ಮರದ ಮೂಲ ಕಾರ್ಯವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಅದರ ಮೂಲವು ಅತ್ಯುತ್ತಮ ಶೃಂಗವಾಗಿದೆ. ಈ ದತ್ತಾಂಶಕ್ಕೆ ಹಿಮ್ಮುಖ ಹುಡುಕಾಟವನ್ನು ಅನ್ವಯಿಸುವುದರಿಂದ ಪಾಲಿಟೋಪ್ನ ಎಲ್ಲಾ ಶೃಂಗಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಇದೇ ರೀತಿಯ ಅಲ್ಗಾರಿದಮ್ ಸರಳವಾದ ಪಾಲಿಟೋಪ್ ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವ ಅಗತ್ಯವಿಲ್ಲದೇ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂನ ಎಲ್ಲಾ ಬೇಸ್ಗಳನ್ನು ಸಹ ಎಣಿಸಬಹುದು. ಹೈಪರ್ ಪ್ಲೇನ್ ವ್ಯವಸ್ಥೆಗಳ ಜೀವಕೋಶಗಳು ಹೈಪರ್ ಪ್ಲೇನ್ ವ್ಯವಸ್ಥೆಯು ಯೂಕ್ಲಿಡಿಯನ್ ಜಾಗವನ್ನು ಜೀವಕೋಶಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ, ಪ್ರತಿಯೊಂದೂ ಅದರ ಬಿಂದುಗಳು ಹೈಪರ್ ಪ್ಲೇನ್ಗಳಲ್ಲಿ ಒಂದಕ್ಕೆ ಸೇರಿವೆಯೇ (ಚಿಹ್ನೆ 0), ಹೈಪರ್ ಪ್ಲೇನ್ನ ಒಂದು ಬದಿಯಲ್ಲಿದೆಯೇ (ಚಿಹ್ನೆ + 1), ಅಥವಾ ಇನ್ನೊಂದು ಬದಿಯಲ್ಲಿದೆಯೇ (ಚಿಹ್ನೆ-1) ಎಂಬುದನ್ನು ವಿವರಿಸುವ "ಸೈನ್ ವೆಕ್ಟರ್" ನಿಂದ ವಿವರಿಸಲ್ಪಡುತ್ತದೆ. ಕೋಶಗಳು ಸ್ಥಳೀಯ ಚಲನೆಗಳ ಅಡಿಯಲ್ಲಿ ಸಂಪರ್ಕಿತ ಸ್ಥಿತಿ ಸ್ಥಳವನ್ನು ರೂಪಿಸುತ್ತವೆ, ಅದು ಒಂದೇ ಚಿಹ್ನೆಯನ್ನು ಒಂದು ಘಟಕದಿಂದ ಬದಲಾಯಿಸುತ್ತದೆ, ಮತ್ತು ಈ ಕಾರ್ಯಾಚರಣೆಯು ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಕಾರ್ಯಸಾಧ್ಯತೆಯ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಮೂಲಕ ಮಾನ್ಯವಾದ ಕೋಶವನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಸಾಧ್ಯವಿದೆ. ಮೂಲ ವಾಹಕವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವ ಮೂಲಕ ಮೂಲ ಕೋಶದ ಯಾವುದೇ ಆಯ್ಕೆಗಾಗಿ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ನಿರ್ಮಿಸಬಹುದು, ಇದು ಸೈನ್ ವೆಕ್ಟರ್ ಅನ್ನು ಮೂಲಕ್ಕೆ ಹತ್ತಿರ ತರುವ ಮೊದಲ ಸಂಭವನೀಯ ಬದಲಾವಣೆಯನ್ನು ಮಾಡುತ್ತದೆ. ಈ ಸ್ಥಿತಿ ಜಾಗಕ್ಕಾಗಿ ರಿವರ್ಸ್ ಸರ್ಚ್ ಅನ್ನು ಬಳಸುವುದು ಮತ್ತು ಮೂಲ ಆಪರೇಟರ್ ಪ್ರತಿ ಕೋಶಕ್ಕೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಎಲ್ಲಾ ಕೋಶಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಪಾಯಿಂಟ್-ಸೆಟ್ ತ್ರಿಕೋನಗಳು ಸಮತಲ ಬಿಂದು ಗುಂಪಿನ ತ್ರಿಕೋನಗಳನ್ನು "ಫ್ಲಿಪ್" ಚಲನೆಗಳಿಂದ ಸಂಪರ್ಕಿಸಲಾಗುತ್ತದೆ, ಅದು ತ್ರಿಕೋನದಿಂದ ಒಂದು ಕರ್ಣೀಯವನ್ನು ತೆಗೆದು ಅದನ್ನು ಇನ್ನೊಂದರಿಂದ ಬದಲಾಯಿಸುತ್ತದೆ. ಡೆಲೌನೆ ತ್ರಿಕೋನವನ್ನು ಮೂಲವಾಗಿ ಆಯ್ಕೆ ಮಾಡಿದರೆ, ಪ್ರತಿ ತ್ರಿಕೋನವನ್ನು ಡೆಲೌನೆ ತ್ರಿಕೋನಕ್ಕೆ ತಿರುಗಿಸಬಹುದು, ಇದರಲ್ಲಿ ನಾಲ್ಕು ಬಿಂದುಗಳ ಕೆಲವು ಉಪಗುಂಪಿನ ತ್ರಿಕೋನವನ್ನು ಅದರ ಡೆಲೌನೆ ತ್ರಿಕೋನದಿಂದ ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ. ಪ್ರತಿ ತ್ರಿಕೋನದ ಪೋಷಕನಾಗಿ ಮೊದಲ ಡೆಲೌನೆ ಫ್ಲಿಪ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು ಮತ್ತು ಸ್ಥಳೀಯ ಹುಡುಕಾಟವನ್ನು ಅನ್ವಯಿಸುವುದು, ಪ್ರತಿ ತ್ರಿಕೋನಕ್ಕೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಎಲ್ಲಾ ತ್ರಿಕೋನಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡಲು ಒಂದು ಕ್ರಮಾವಳಿಯನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಸಂಪರ್ಕಿತ ಉಪಗ್ರಾಫ್ಗಳು ನಿರ್ದಿಷ್ಟ ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ನ ಸಂಪರ್ಕಿತ ಉಪಗ್ರಾಫ್ಗಳು ಮತ್ತು ಸಂಪರ್ಕಿತ ಪ್ರೇರಿತ ಉಪಗ್ರಾಫ್ಗಳು, ಅದರ ಸ್ಥಳೀಯ ಚಲನೆಗಳು ಅನುಕ್ರಮವಾಗಿ ಗ್ರಾಫ್ನ ಒಂದೇ ಅಂಚು ಅಥವಾ ಶೃಂಗವನ್ನು ಸೇರಿಸುವುದು ಅಥವಾ ತೆಗೆದುಹಾಕುವುದು. ಮೊದಲ ಅಂಚು ಅಥವಾ ಶೃಂಗವನ್ನು (ಅಂಚುಗಳು ಅಥವಾ ಶೃಂಗಗಳ ಕೆಲವು ಕ್ರಮದಲ್ಲಿ) ಸೇರಿಸುವ ಮೂಲಕ ಈ ಸ್ಥಿತಿ ಜಾಗದ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ಪಡೆಯಬಹುದು, ಅದರ ಸೇರ್ಪಡೆಯು ಮತ್ತೊಂದು ಸಂಪರ್ಕಿತ ಉಪ ನಕ್ಷೆಯನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ; ಅದರ ಮೂಲವು ಇಡೀ ನಕ್ಷೆಯಾಗಿದೆ. ಈ ಸ್ಟೇಟ್ ಸ್ಪೇಸ್ ಮತ್ತು ಮೂಲ ಆಪರೇಟರ್ಗೆ ಸ್ಥಳೀಯ ಹುಡುಕಾಟವನ್ನು ಅನ್ವಯಿಸುವುದರಿಂದ ಪ್ರತಿ ಸಬ್ಗ್ರಾಫ್ಗೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಎಲ್ಲಾ ಸಂಪರ್ಕಿತ ಸಬ್ಗ್ರಾಫ್ಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಇತರ ಅನ್ವಯಿಕೆಗಳು ಈ ಕೆಳಗಿನ ರಚನೆಗಳನ್ನು ಉತ್ಪಾದಿಸುವ ಕ್ರಮಾವಳಿಗಳನ್ನು ಒಳಗೊಂಡಿವೆಃ ಪಾಲಿಮಿನೋಸ್, ಪಾಲಿಯಾಮಂಡ್ ಮೂಲದ್ರವ್ಯಗಳು ಮತ್ತು ಪಾಲಿಹೆಕ್ಸ್ (ಗಣಿತ) ಹೈಡ್ರೋಕಾರ್ಬನ್ ಅಣುಗಳು. ನಿರ್ದೇಶಿತ ಅಸೈಕ್ಲಿಕ್ ಗ್ರಾಫ್ಗಳ ಟೋಪೋಲಾಜಿಕಲ್ ಕ್ರಮಗಳು, ಎರಡು ಅಂಶಗಳ ಕ್ರಮವನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುವ ಸ್ಥಳೀಯ ಚಲನೆಗಳನ್ನು ಹೊಂದಿರುವ ಸ್ಥಿತಿ ಜಾಗವನ್ನು ಬಳಸುತ್ತವೆ. ಗ್ರಾಫ್ಗಳ ಮರಗಳು, ಪ್ಲ್ಯಾನರ್ ಪಾಯಿಂಟ್ ಸೆಟ್ಗಳ ಮರಗಳನ್ನು ದಾಟದ ಮರಗಳು, ಮತ್ತು ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳ ಬೇಸ್ಗಳು, ಒಂದು ಅಂಚನ್ನು ಇನ್ನೊಂದಕ್ಕೆ ಬದಲಾಯಿಸುವ ರಾಜ್ಯ ಸ್ಥಳವನ್ನು ಬಳಸುತ್ತವೆ. ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ ಯೂಲರ್ ಪ್ರವಾಸಗಳು. ವಿರಳ ಗ್ರಾಫ್ಗಳ ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳು. ಗರಿಷ್ಠ ಸಮತಟ್ಟಾದ ನಕ್ಷೆಗಳು ಮತ್ತು ಪಾಲಿಹೆಡ್ರಲ್ ನಕ್ಷೆಗಳು. ನಿರ್ದಿಷ್ಟ ಪಾಯಿಂಟ್ ಸೆಟ್ನಲ್ಲಿ ದಾಟದ ಕನಿಷ್ಠ ಕಟ್ಟುನಿಟ್ಟಾದ ಗ್ರಾಫ್ಗಳು. ಸುತ್ತಮುತ್ತಲಿನ ಬಹುಭುಜಾಕೃತಿಗಳು, ಕೆಲವು ನಿರ್ದಿಷ್ಟ ಬಿಂದುಗಳನ್ನು ಶೃಂಗಗಳಾಗಿ ಹೊಂದಿರುವ ಮತ್ತು ಉಳಿದವುಗಳನ್ನು ಸುತ್ತುವರೆದಿರುವ ಬಹುಭುಜಾಕೃತಿಗಳು, ಬಹುಭುಜಾಕೃತಿಯ ಒಂದು ಶೃಂಗವನ್ನು ಸೇರಿಸುವ ಅಥವಾ ತೆಗೆದುಹಾಕುವ ಸ್ಥಿತಿ ಜಾಗವನ್ನು ಬಳಸುತ್ತವೆ. ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ಗಳ ಮಿಂಕೋವ್ಸ್ಕಿಯ ಶೃಂಗಗಳು ಅಥವಾ ಮುಖಗಳು. ಮೊನೊಮಿಯಲ್ ಐಡಿಯಲ್ಗಳ ಮೂಲೆಗಳು (ಮಲ್ಟಿಡಿಗ್ರೀಗಳು). ಉಲ್ಲೇಖಗಳು ಹುಡುಕಾಟ ಕ್ರಮಾವಳಿಗಳು ಸಂಯೋಜಿತ ಕ್ರಮಾವಳಿಗಳು