Contraction hierarchies
ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ, ಸಂಕೋಚನ ಶ್ರೇಣಿವ್ಯವಸ್ಥೆಗಳ ವಿಧಾನವು ಗ್ರಾಫ್ನಲ್ಲಿನ ಚಿಕ್ಕದಾದ ಮಾರ್ಗವನ್ನು ಕಂಡುಹಿಡಿಯುವ ವೇಗ-ಹೆಚ್ಚಿಸುವ ತಂತ್ರವಾಗಿದೆ. ಅತ್ಯಂತ ಅಂತರ್ಬೋಧೆಯ ಅನ್ವಯಗಳೆಂದರೆ ಕಾರು-ಸಂಚರಣೆ ವ್ಯವಸ್ಥೆಗಳುಃ ಬಳಕೆದಾರರು ಸಾಧ್ಯವಾದಷ್ಟು ತ್ವರಿತವಾದ ಮಾರ್ಗವನ್ನು ಬಳಸಲು ಬಯಸುತ್ತಾರೆ. ಇಲ್ಲಿ ಹೊಂದುವಂತೆ ಮಾಡಲಾದ ಮೆಟ್ರಿಕ್ ಎಂದರೆ ಪ್ರಯಾಣದ ಸಮಯ. ಛೇದನಗಳನ್ನು ಶೃಂಗಗಳಿಂದ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ, ರಸ್ತೆ ವಿಭಾಗಗಳು ಅವುಗಳನ್ನು ಅಂಚುಗಳಿಂದ ಸಂಪರ್ಕಿಸುತ್ತವೆ. ಅಂಚಿನ ತೂಕವು ರಸ್ತೆಯ ಈ ಭಾಗದಲ್ಲಿ ವಾಹನ ಚಲಾಯಿಸಲು ತೆಗೆದುಕೊಳ್ಳುವ ಸಮಯವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಒಂದು ಮಾರ್ಗವು ಅಂಚುಗಳ ಅನುಕ್ರಮವಾಗಿದೆ (ರಸ್ತೆ ವಿಭಾಗಗಳು); ಸಾಧ್ಯವಿರುವ ಎಲ್ಲಾ ಮಾರ್ಗಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಮೊತ್ತದ ಅಂಚಿನ ತೂಕವನ್ನು ಹೊಂದಿರುವ ಮಾರ್ಗವು ಅತ್ಯಂತ ಚಿಕ್ಕದಾಗಿದೆ. ಗ್ರಾಫ್ ನಲ್ಲಿನ ಚಿಕ್ಕದಾದ ಮಾರ್ಗವನ್ನು ಡಿಜ್ಕ್ಸ್ಟ್ರಾ ಅಲ್ಗಾರಿದಮ್ ಬಳಸಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು ಆದರೆ, ರಸ್ತೆ ಜಾಲಗಳು ಹತ್ತಾರು ಮಿಲಿಯನ್ ಶೃಂಗಗಳನ್ನು ಒಳಗೊಂಡಿರುವುದರಿಂದ, ಇದು ಅಪ್ರಾಯೋಗಿಕವಾಗಿದೆ. ಸಂಕೋಚನ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳು ರಸ್ತೆ ಜಾಲಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಗ್ರಾಫ್ಗಳ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಬಳಸಿಕೊಳ್ಳಲು ಹೊಂದುವಂತೆ ವೇಗವನ್ನು ಹೆಚ್ಚಿಸುವ ವಿಧಾನವಾಗಿದೆ. ಪೂರ್ವ ಸಂಸ್ಕರಣಾ ಹಂತದಲ್ಲಿ ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ರಚಿಸುವ ಮೂಲಕ ವೇಗವನ್ನು ಸಾಧಿಸಲಾಗುತ್ತದೆ, ನಂತರ ಅವುಗಳನ್ನು "ಮುಖ್ಯವಲ್ಲದ" ಶೃಂಗಗಳನ್ನು ಬಿಟ್ಟುಬಿಡಲು ಕಡಿಮೆ-ಮಾರ್ಗದ ಪ್ರಶ್ನೆಯ ಸಮಯದಲ್ಲಿ ಬಳಸಲಾಗುತ್ತದೆ. ಇದು ರಸ್ತೆ ಜಾಲಗಳು ಹೆಚ್ಚು ಶ್ರೇಣೀಕೃತವಾಗಿವೆ ಎಂಬ ಅವಲೋಕನವನ್ನು ಆಧರಿಸಿದೆ. ಕೆಲವು ಛೇದಕಗಳು, ಉದಾಹರಣೆಗೆ ಹೆದ್ದಾರಿ ಜಂಕ್ಷನ್ಗಳು, "ಹೆಚ್ಚು ಮುಖ್ಯವಾದವು" ಮತ್ತು ಶ್ರೇಣೀಕರಣದಲ್ಲಿ ಎತ್ತರದಲ್ಲಿರುತ್ತವೆ, ಉದಾಹರಣೆಗೆ ಡೆಡ್ ಎಂಡ್ಗೆ ಹೋಗುವ ಜಂಕ್ಷನ್. ಎರಡು ಪ್ರಮುಖ ಜಂಕ್ಷನ್ಗಳ ನಡುವಿನ ಪೂರ್ವಭಾವಿ ಅಂತರವನ್ನು ಉಳಿಸಲು ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ಬಳಸಬಹುದು, ಅಂದರೆ ಅಲ್ಗಾರಿದಮ್ ಪ್ರಶ್ನೆಯ ಸಮಯದಲ್ಲಿ ಈ ಜಂಕ್ಷನ್ಗಳ ನಡುವಿನ ಪೂರ್ಣ ಮಾರ್ಗವನ್ನು ಪರಿಗಣಿಸಬೇಕಾಗಿಲ್ಲ. ಮಾನವರು ಯಾವ ರಸ್ತೆಗಳನ್ನು "ಮುಖ್ಯ" ಎಂದು ಪರಿಗಣಿಸುತ್ತಾರೆ ಎಂಬುದರ ಬಗ್ಗೆ ಸಂಕೋಚನ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳು ತಿಳಿದಿಲ್ಲ (ಉದಾ. ಹೆದ್ದಾರಿಗಳು), ಆದರೆ ಅವುಗಳನ್ನು ಗ್ರಾಫ್ ಅನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ಒದಗಿಸಲಾಗಿದೆ ಮತ್ತು ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಶೃಂಗಗಳಿಗೆ ಪ್ರಾಮುಖ್ಯತೆಯನ್ನು ನೀಡಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ. ಸಂಕೋಚನ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳನ್ನು ಕಾರ್-ನ್ಯಾವಿಗೇಷನ್ ವ್ಯವಸ್ಥೆಗಳಲ್ಲಿನ ವೇಗದ ಕ್ರಮಾವಳಿಗಳಿಗೆ ಮಾತ್ರ ಅನ್ವಯಿಸಲಾಗುವುದಿಲ್ಲ, ಆದರೆ ವೆಬ್-ಆಧಾರಿತ ಮಾರ್ಗ ಯೋಜಕರು, ಟ್ರಾಫಿಕ್ ಸಿಮ್ಯುಲೇಶನ್ ಮತ್ತು ಲಾಜಿಸ್ಟಿಕ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ನಲ್ಲಿಯೂ ಸಹ ಅನ್ವಯಿಸಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ನ ಅನುಷ್ಠಾನಗಳು ಓಪನ್ ಸೋರ್ಸ್ ಸಾಫ್ಟ್ವೇರ್ ಆಗಿ ಸಾರ್ವಜನಿಕವಾಗಿ ಲಭ್ಯವಿವೆ. ಅಲ್ಗಾರಿದಮ್ ಸಂಕೋಚನ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳು (ಸಿಎಚ್) ಅಲ್ಗಾರಿದಮ್ ಪೂರ್ವ ಸಂಸ್ಕರಣೆ ಹಂತ ಮತ್ತು ಪ್ರಶ್ನೆಯ ಹಂತವನ್ನು ಒಳಗೊಂಡಿರುವ ಚಿಕ್ಕದಾದ ಮಾರ್ಗ ಸಮಸ್ಯೆಗೆ ಎರಡು ಹಂತದ ವಿಧಾನವಾಗಿದೆ. ರಸ್ತೆ ಜಾಲಗಳು ವಿರಳವಾಗಿ ಬದಲಾಗುವುದರಿಂದ, ಪ್ರಶ್ನೆಗಳಿಗೆ ಉತ್ತರಿಸುವ ಮೊದಲು ಕೆಲವು ಲೆಕ್ಕಾಚಾರಗಳನ್ನು ಮೊದಲೇ ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಹೆಚ್ಚಿನ ಸಮಯವನ್ನು (ಸೆಕೆಂಡುಗಳಿಂದ ಗಂಟೆಗಳವರೆಗೆ) ಬಳಸಬಹುದು. ಈ ಪೂರ್ವ ಸಂಗಣಿತ ದತ್ತಾಂಶವನ್ನು ಬಳಸಿಕೊಂಡು, ಅನೇಕ ಪ್ರಶ್ನೆಗಳಿಗೆ ಪ್ರತಿಯೊಂದಕ್ಕೂ ಬಹಳ ಕಡಿಮೆ ಸಮಯವನ್ನು (ಮೈಕ್ರೋ ಸೆಕೆಂಡುಗಳು) ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ ಉತ್ತರಿಸಬಹುದು. ಈ ವೇಗವನ್ನು ಸಾಧಿಸಲು ಸಿಎಚ್ಗಳು ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ಅವಲಂಬಿಸಿವೆ. ಒಂದು ಶಾರ್ಟ್ಕಟ್ ಎರಡು ಶೃಂಗಗಳನ್ನು ಸಂಪರ್ಕಿಸುತ್ತದೆ ಮತ್ತು ಮೂಲ ಗ್ರಾಫ್ನಲ್ಲಿ ಪಕ್ಕದಲ್ಲಿಲ್ಲ. ಇದರ ಅಂಚಿನ ತೂಕವು ಚಿಕ್ಕದಾದ-ಪಥದ ಅಂಚಿನ ತೂಕದ ಮೊತ್ತವಾಗಿದೆ. ಹೆದ್ದಾರಿಯಿಂದ ಸಂಪರ್ಕ ಹೊಂದಿದ ಎರಡು ದೊಡ್ಡ ನಗರಗಳನ್ನು ಪರಿಗಣಿಸಿ. ಈ ಎರಡು ನಗರಗಳ ನಡುವೆ, ಸಣ್ಣ ಹಳ್ಳಿಗಳು ಮತ್ತು ಉಪನಗರಗಳಿಗೆ ಹೋಗುವ ಬಹುಸಂಖ್ಯೆಯ ಜಂಕ್ಷನ್ಗಳಿವೆ. ಹೆಚ್ಚಿನ ಚಾಲಕರು ಒಂದು ನಗರದಿಂದ ಇನ್ನೊಂದು ನಗರಕ್ಕೆ ಹೋಗಲು ಬಯಸುತ್ತಾರೆ-ಬಹುಶಃ ದೊಡ್ಡ ಮಾರ್ಗದ ಭಾಗವಾಗಿ-ಮತ್ತು ದಾರಿಯಲ್ಲಿ ಒಂದು ನಿರ್ಗಮನವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದಿಲ್ಲ. ಈ ರಸ್ತೆ ವಿನ್ಯಾಸವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಪ್ರತಿ ಛೇದಕವನ್ನು ನೋಡ್ನಿಂದ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ನೆರೆಯ ಛೇದಕಗಳ ನಡುವೆ ಅಂಚುಗಳನ್ನು ರಚಿಸಲಾಗುತ್ತದೆ. ಈ ಎರಡು ನಗರಗಳ ನಡುವಿನ ಅಂತರವನ್ನು ಲೆಕ್ಕ ಹಾಕಲು, ಅಲ್ಗಾರಿದಮ್ ದಾರಿಯುದ್ದಕ್ಕೂ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಹಾದುಹೋಗಬೇಕು, ಅವುಗಳ ಉದ್ದವನ್ನು ಸೇರಿಸಬೇಕು. ಈ ದೂರವನ್ನು ಒಮ್ಮೆ ಮುಂಚಿತವಾಗಿ ಗಣನೆಗೆ ತೆಗೆದುಕೊಂಡು ಅದನ್ನು ಎರಡು ದೊಡ್ಡ ನಗರಗಳ ನಡುವೆ ರಚಿಸಲಾದ ಹೆಚ್ಚುವರಿ ಅಂಚಿನಲ್ಲಿ ಸಂಗ್ರಹಿಸುವುದರಿಂದ ಪ್ರತಿ ಬಾರಿಯೂ ಈ ಹೆದ್ದಾರಿಯನ್ನು ಪ್ರಶ್ನೆಯಲ್ಲಿ ಮೌಲ್ಯಮಾಪನ ಮಾಡಬೇಕಾದಾಗ ಲೆಕ್ಕಾಚಾರಗಳನ್ನು ಉಳಿಸುತ್ತದೆ. ಈ ಹೆಚ್ಚುವರಿ ಅಂಚನ್ನು "ಶಾರ್ಟ್ಕಟ್" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ನೈಜ ಜಗತ್ತಿನಲ್ಲಿ ಯಾವುದೇ ಪ್ರತಿರೂಪವನ್ನು ಹೊಂದಿಲ್ಲ. ಸಂಕೋಚನ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಯು ರಸ್ತೆಯ ಪ್ರಕಾರಗಳ ಬಗ್ಗೆ ಯಾವುದೇ ಜ್ಞಾನವನ್ನು ಹೊಂದಿಲ್ಲ ಆದರೆ ಗ್ರಾಫ್ ಅನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ಮಾತ್ರ ಬಳಸಿಕೊಂಡು ಯಾವ ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ರಚಿಸಬೇಕು ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ. ಪೂರ್ವ ಸಂಸ್ಕರಣಾ ಹಂತ ಸಿಎಚ್ ಅಲ್ಗಾರಿದಮ್ ಹುಡುಕಾಟದ ಸ್ಥಳವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಪೂರ್ವ ಸಂಸ್ಕರಣಾ ಹಂತದಲ್ಲಿ ರಚಿಸಲಾದ ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ಅವಲಂಬಿಸಿದೆ-ಅಂದರೆ ಸಿಎಚ್ ಪ್ರಶ್ನಿಸುವ ಸಮಯದಲ್ಲಿ ನೋಡಬೇಕಾದ ಶೃಂಗಗಳ ಸಂಖ್ಯೆ. ಇದನ್ನು ಸಾಧಿಸಲು, ಪುನರಾವರ್ತಿತ ಶೃಂಗ ಸಂಕೋಚನಗಳನ್ನು ನಡೆಸಲಾಗುತ್ತದೆ. ಒಂದು ಶೃಂಗವನ್ನು ಸಂಕುಚಿತಗೊಳಿಸುವಾಗ ಅದನ್ನು ಗ್ರಾಫ್ನಿಂದ ತಾತ್ಕಾಲಿಕವಾಗಿ ತೆಗೆದುಹಾಕಲಾಗುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಜೋಡಿ ನೆರೆಯ ಶೃಂಗಗಳ ನಡುವೆ ಒಂದು ಶಾರ್ಟ್ಕಟ್ ಅನ್ನು ರಚಿಸಲಾಗುತ್ತದೆ. ನಡುವಿನ ಮತ್ತು ಒಳಗೊಂಡಿರುವ ಚಿಕ್ಕ ಮಾರ್ಗವನ್ನು ನಿರ್ಧರಿಸುವ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಸಾಕ್ಷಿ ಹುಡುಕಾಟ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಇನ್ನೂ ಸಂಕುಚಿತಗೊಳ್ಳದ ನೋಡ್ಗಳನ್ನು ಮಾತ್ರ ಬಳಸಿಕೊಂಡು ಫಾರ್ವರ್ಡ್ ಸರ್ಚ್ ಅನ್ನು ಬಳಸುವ ಮಾರ್ಗವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಮೂಲಕ ಇದನ್ನು ಮಾಡಬಹುದು. ನೋಡ್ ಆರ್ಡರ್ ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನ ಶೃಂಗಗಳನ್ನು ಸಂಕೋಚನಗಳ ಮೂಲಕ ಗ್ರಾಫ್ಗೆ ಸೇರಿಸಲಾದ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವ ರೀತಿಯಲ್ಲಿ ಸಂಕುಚಿತಗೊಳಿಸಬೇಕು. ಆಪ್ಟಿಮಲ್ ನೋಡ್ ಆರ್ಡರಿಂಗ್ ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಆಗಿರುವುದರಿಂದ, ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಅನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಬಾಟಮ್-ಅಪ್ ಮತ್ತು ಟಾಪ್-ಡೌನ್ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಅಸ್ತಿತ್ವದಲ್ಲಿವೆ. ಒಂದೆಡೆ, ಕಂಪ್ಯೂಟೇಶನಲ್ ಆಗಿ ಅಗ್ಗದ ಬಾಟಮ್-ಅಪ್ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಶೃಂಗಗಳನ್ನು ದುರಾಸೆಯ ಶೈಲಿಯಲ್ಲಿ ಸಂಕುಚಿತಗೊಳಿಸುವ ಕ್ರಮವನ್ನು ನಿರ್ಧರಿಸುತ್ತದೆ; ಇದರರ್ಥ ಕ್ರಮವು ಮುಂಚಿತವಾಗಿ ತಿಳಿದಿಲ್ಲ ಆದರೆ ಹಿಂದಿನ ಸಂಕೋಚನವನ್ನು ಪೂರ್ಣಗೊಳಿಸಿದ ನಂತರ ಸಂಕೋಚನಕ್ಕಾಗಿ ಮುಂದಿನ ನೋಡ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ. ಮತ್ತೊಂದೆಡೆ, ಟಾಪ್-ಡೌನ್ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಮೊದಲ ನೋಡ್ ಸಂಕುಚಿತಗೊಳ್ಳುವ ಮೊದಲು ಇಡೀ ನೋಡ್ ಕ್ರಮವನ್ನು ಪೂರ್ವಭಾವಿಯಾಗಿ ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆ. ಇದು ಉತ್ತಮ ಫಲಿತಾಂಶಗಳನ್ನು ನೀಡುತ್ತದೆ ಆದರೆ ಹೆಚ್ಚಿನ ಪೂರ್ವ ಸಂಸ್ಕರಣೆಯ ಸಮಯ ಬೇಕಾಗುತ್ತದೆ. ಬಾಟಮ್-ಅಪ್ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ನಲ್ಲಿ, ಸಂಕೋಚನಕ್ಕಾಗಿ ಮುಂದಿನ ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಅಂಶಗಳ ಸಂಯೋಜನೆಯನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಶಾರ್ಟ್ಕಟ್ಗಳ ಸಂಖ್ಯೆಯು ಪ್ರಿಪ್ರೊಸೆಸಿಂಗ್ ಮತ್ತು ಕ್ವೆರಿ ರನ್ಟೈಮ್ ಅನ್ನು ನಿರ್ಧರಿಸುವ ಪ್ರಾಥಮಿಕ ಅಂಶವಾಗಿರುವುದರಿಂದ, ನಾವು ಅದನ್ನು ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕದಾಗಿಡಲು ಬಯಸುತ್ತೇವೆ. ಆದ್ದರಿಂದ ಸಂಕೋಚನಕ್ಕಾಗಿ ಮುಂದಿನ ನೋಡ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಅತ್ಯಂತ ಪ್ರಮುಖ ಪದವೆಂದರೆ ನೋಡ್ ಅನ್ನು ಸಂಕುಚಿತಗೊಳಿಸುವಾಗ ಸೇರಿಸಲಾದ ಅಂಚುಗಳ ನಿವ್ವಳ ಸಂಖ್ಯೆ. ಇದನ್ನು ಸಂಕುಚಿತಗೊಳಿಸಬೇಕಾದರೆ ರಚಿಸಲಾಗುವ ಶಾರ್ಟ್ಕಟ್ಗಳ ಸಂಖ್ಯೆ ಎಲ್ಲಿದೆ ಮತ್ತು ಇದಕ್ಕೆ ಕಾರಣವಾಗುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಈ ಮಾನದಂಡವನ್ನು ಮಾತ್ರ ಬಳಸಿಕೊಂಡು, ರೇಖೀಯ ಮಾರ್ಗವು ರೇಖೀಯ ಕ್ರಮಾನುಗತಕ್ಕೆ (ಅನೇಕ ಹಂತಗಳು) ಕಾರಣವಾಗುತ್ತದೆ ಮತ್ತು ಯಾವುದೇ ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ರಚಿಸಲಾಗುವುದಿಲ್ಲ. ಈಗಾಗಲೇ ಸಂಕುಚಿತಗೊಂಡಿರುವ ಹತ್ತಿರದ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಪರಿಗಣಿಸುವ ಮೂಲಕ, ಏಕರೂಪದ ಸಂಕೋಚನ ಮತ್ತು ಸಮತಟ್ಟಾದ ಶ್ರೇಣಿವ್ಯವಸ್ಥೆಯನ್ನು (ಕಡಿಮೆ ಮಟ್ಟಗಳು) ಸಾಧಿಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಪ್ರತಿ ಬಾರಿ ನೆರೆಯ ಶೃಂಗವು ಸಂಕುಚಿತಗೊಂಡಾಗ ಹೆಚ್ಚಾಗುವ ಪ್ರತಿ ನೋಡ್ಗೆ ಕೌಂಟರ್ ಅನ್ನು ನಿರ್ವಹಿಸುವ ಮೂಲಕ ಇದನ್ನು ಮಾಡಬಹುದು. ನಂತರ ಹೆಚ್ಚಿನ ಕೌಂಟರ್ಗಳನ್ನು ಹೊಂದಿರುವ ನೋಡ್ಗಳಿಗಿಂತ ಕಡಿಮೆ ಕೌಂಟರ್ಗಳನ್ನು ಹೊಂದಿರುವ ನೋಡ್ಗಳಿಗೆ ಆದ್ಯತೆ ನೀಡಲಾಗುತ್ತದೆ. ಮತ್ತೊಂದೆಡೆ, ಟಾಪ್-ಡೌನ್ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಉತ್ತಮ ಫಲಿತಾಂಶಗಳನ್ನು ನೀಡುತ್ತದೆ ಆದರೆ ಹೆಚ್ಚಿನ ಪೂರ್ವ ಸಂಸ್ಕರಣೆಯ ಸಮಯ ಬೇಕಾಗುತ್ತದೆ. ಅವು ಅನೇಕ ಚಿಕ್ಕದಾದ ಮಾರ್ಗಗಳ ಭಾಗವಾಗಿರುವ ಶೃಂಗಗಳನ್ನು ಕೆಲವು ಚಿಕ್ಕದಾದ ಮಾರ್ಗಗಳಿಗೆ ಮಾತ್ರ ಅಗತ್ಯವಿರುವವುಗಳಿಗಿಂತ ಹೆಚ್ಚು ಮುಖ್ಯವೆಂದು ವರ್ಗೀಕರಿಸುತ್ತವೆ. ನೆಸ್ಟೆಡ್ ಡಿಸ್ಸೆಕ್ಷನ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಇದನ್ನು ಅಂದಾಜು ಮಾಡಬಹುದು. ನೆಸ್ಟೆಡ್ ಡಿಸ್ಸೆಕ್ಷನ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು, ಒಬ್ಬರು ಪುನರಾವರ್ತಿತವಾಗಿ ಗ್ರಾಫ್ ಅನ್ನು ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸುತ್ತಾರೆ, ನಂತರ ಅವುಗಳನ್ನು ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ. ಅಂದರೆ, ಗ್ರಾಫ್ನಿಂದ ತೆಗೆದುಹಾಕಿದಾಗ ಸರಿಸುಮಾರು ಸಮಾನ ಗಾತ್ರದ ಎರಡು ವಿಚ್ಛೇದಿತ ತುಣುಕುಗಳಾಗಿ ಬೇರ್ಪಡಿಸುವ ನೋಡ್ಗಳ ಉಪವಿಭಾಗವನ್ನು ಹುಡುಕಿ. ಎಲ್ಲಾ ನೋಡ್ಗಳನ್ನು ನೋಡ್ ಕ್ರಮದಲ್ಲಿ ಕೊನೆಯದಾಗಿ ಇರಿಸಿ ಮತ್ತು ನಂತರ ನೆಸ್ಟೆಡ್ ವಿಭಜನೆಯನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ ಮತ್ತು, ಗ್ರಾಫ್ನ ಅರ್ಧದಿಂದ ಗ್ರಾಫ್ನ ಇನ್ನೊಂದು ಅರ್ಧದವರೆಗಿನ ಎಲ್ಲಾ ಪ್ರಶ್ನೆಗಳು ಸಣ್ಣ ವಿಭಜಕದ ಮೂಲಕ ಹಾದುಹೋಗಬೇಕು ಮತ್ತು ಆದ್ದರಿಂದ ಈ ವಿಭಜಕದಲ್ಲಿನ ನೋಡ್ಗಳು ಹೆಚ್ಚಿನ ಪ್ರಾಮುಖ್ಯತೆಯನ್ನು ಹೊಂದಿವೆ. ಅವುಗಳ ಸಣ್ಣ ವಿಭಜಕಗಳ ಕಾರಣದಿಂದಾಗಿ ನೆಸ್ಟೆಡ್ ವಿಭಜನೆಗಳನ್ನು ರಸ್ತೆ ಜಾಲಗಳಲ್ಲಿ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಪ್ರಶ್ನೆಯ ಹಂತದಲ್ಲಿ, ಆರಂಭಿಕ ನೋಡ್ನಿಂದ ಪ್ರಾರಂಭಿಸಿ ದ್ವಿ-ದಿಕ್ಕಿನ ಹುಡುಕಾಟವನ್ನು ನಡೆಸಲಾಗುತ್ತದೆ ಮತ್ತು ಪೂರ್ವ ಸಂಸ್ಕರಣೆಯ ಹಂತದಲ್ಲಿ ರಚಿಸಲಾದ ಶಾರ್ಟ್ಕಟ್ಗಳಿಂದ ಮೂಲ ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಗುರಿ ನೋಡ್ ಅನ್ನು ಹೆಚ್ಚಿಸಲಾಗುತ್ತದೆ. ಮತ್ತು ನಡುವಿನ ಚಿಕ್ಕ ಮಾರ್ಗದಲ್ಲಿನ ಅತ್ಯಂತ ಪ್ರಮುಖ ಶೃಂಗವು ಎರಡೂ ಅಥವಾ ಸ್ವತಃ ಅಥವಾ ಎರಡಕ್ಕಿಂತಲೂ ಹೆಚ್ಚು ಮುಖ್ಯವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ವರ್ಟೆಕ್ಸ್ ಮಿನಿಮೈಸಿಂಗ್ ಮೂಲ ಗ್ರಾಫ್ ಮತ್ತು ಹಿಡಿತದಲ್ಲಿ ಕಡಿಮೆ ಹಾದಿಯಲ್ಲಿದೆ. ಇದು, ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ಹೇಗೆ ರಚಿಸಲಾಗುತ್ತದೆ ಎಂಬುದರ ಸಂಯೋಜನೆಯೊಂದಿಗೆ, ಮುಂದಕ್ಕೆ ಮತ್ತು ಹಿಂದಕ್ಕೆ ಹುಡುಕಾಟವು ಶ್ರೇಣಿಯಲ್ಲಿ ಹೆಚ್ಚು ಮುಖ್ಯವಾದ ನೋಡ್ಗಳಿಗೆ (ಮೇಲ್ಮುಖವಾಗಿ) ಕಾರಣವಾಗುವ ಅಂಚುಗಳನ್ನು ಮಾತ್ರ ವಿಶ್ರಾಂತಿ ಮಾಡಬೇಕಾಗುತ್ತದೆ, ಇದು ಹುಡುಕಾಟದ ಸ್ಥಳವನ್ನು ಚಿಕ್ಕದಾಗಿಸುತ್ತದೆ. ಎಲ್ಲಾ ಅಪ್-(ಡೌನ್-ಅಪ್)-ಡೌನ್ ಮಾರ್ಗಗಳಲ್ಲಿ, ಒಳಗಿನ (ಡೌನ್-ಅಪ್) ಅನ್ನು ಬಿಟ್ಟುಬಿಡಬಹುದು, ಏಕೆಂದರೆ ಪೂರ್ವ ಸಂಸ್ಕರಣೆಯ ಹಂತದಲ್ಲಿ ಶಾರ್ಟ್ಕಟ್ ಅನ್ನು ರಚಿಸಲಾಗಿದೆ. ಒಂದು ಸಿಎಚ್ ಪ್ರಶ್ನೆಯು, ಮೇಲೆ ವಿವರಿಸಿದಂತೆ, ಸಮಯ ಅಥವಾ ದೂರವನ್ನು ನೀಡುತ್ತದೆ ಆದರೆ ನಿಜವಾದ ಮಾರ್ಗವನ್ನು ನೀಡುವುದಿಲ್ಲ. ಚಿಕ್ಕದಾದ ಮಾರ್ಗದ ಅಂಚುಗಳ (ರಸ್ತೆಗಳು) ಪಟ್ಟಿಯನ್ನು ಪಡೆಯಲು, ತೆಗೆದ ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ಅನ್ಪ್ಯಾಕ್ ಮಾಡಬೇಕಾಗುತ್ತದೆ. ಪ್ರತಿ ಶಾರ್ಟ್ಕಟ್ ಎರಡು ಅಂಚುಗಳ ಸಂಯೋಜನೆಯಾಗಿದೆಃ ಮೂಲ ಗ್ರಾಫ್ನ ಎರಡು ಅಂಚುಗಳು, ಅಥವಾ ಎರಡು ಶಾರ್ಟ್ಕಟ್ಗಳು, ಅಥವಾ ಒಂದು ಮೂಲ ಅಂಚು ಮತ್ತು ಒಂದು ಶಾರ್ಟ್ಕಟ್. ಸಂಕೋಚನದ ಸಮಯದಲ್ಲಿ ಪ್ರತಿ ಶಾರ್ಟ್ಕಟ್ನ ಮಧ್ಯದ ಶೃಂಗವನ್ನು ಸಂಗ್ರಹಿಸುವುದರಿಂದ ಕಡಿಮೆ ಮಾರ್ಗದ ರೇಖೀಯ-ಸಮಯದ ಪುನರಾವರ್ತಿತ ಅನ್ಪ್ಯಾಕ್ ಮಾಡಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಕಸ್ಟಮೈಸ್ಡ್ ಸಂಕೋಚನ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳು ನೆಟ್ವರ್ಕ್ ಟೋಪೋಲಜಿಗಿಂತ ಅಂಚಿನ ತೂಕವನ್ನು ಹೆಚ್ಚಾಗಿ ಬದಲಾಯಿಸಿದರೆ, ಪೂರ್ವ ಸಂಸ್ಕರಣೆ ಮತ್ತು ಪ್ರಶ್ನೆಯ ಹಂತದ ನಡುವೆ ಕಸ್ಟಮೈಸೇಶನ್ ಹಂತವನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಸಿಎಚ್ ಅನ್ನು ಮೂರು-ಹಂತದ ವಿಧಾನಕ್ಕೆ ವಿಸ್ತರಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ಕಡಿಮೆ ದೂರ ಮತ್ತು ಕಡಿಮೆ ಸಮಯದ ನಡುವೆ ಬದಲಾಯಿಸಲು ಅಥವಾ ಪ್ರಸ್ತುತ ಸಂಚಾರ ಮಾಹಿತಿ ಮತ್ತು ಕೆಲವು ರೀತಿಯ ರಸ್ತೆಗಳನ್ನು (ದೋಣಿಗಳು, ಹೆದ್ದಾರಿಗಳು) ತಪ್ಪಿಸುವಂತಹ ಬಳಕೆದಾರರ ಆದ್ಯತೆಗಳನ್ನು ಸೇರಿಸಲು ಇದನ್ನು ಬಳಸಬಹುದು. ಪೂರ್ವ ಸಂಸ್ಕರಣಾ ಹಂತದಲ್ಲಿ, ನೋಡ್ಗಳು ಸಂಕುಚಿತಗೊಳ್ಳುವ ಕ್ರಮವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಹೆಚ್ಚಿನ ರನ್ಟೈಮ್ ಅನ್ನು ಖರ್ಚು ಮಾಡಲಾಗುತ್ತದೆ. ಪೂರ್ವ ಸಂಸ್ಕರಣೆ ಹಂತದಲ್ಲಿ ಸಂಕೋಚನ ಕಾರ್ಯಾಚರಣೆಗಳ ಈ ಅನುಕ್ರಮವನ್ನು ಕಸ್ಟಮೈಸೇಶನ್ ಹಂತದಲ್ಲಿ ನಂತರ ಅಗತ್ಯವಿದ್ದಾಗ ಉಳಿಸಬಹುದು. ಪ್ರತಿ ಬಾರಿ ಮೆಟ್ರಿಕ್ ಅನ್ನು ಕಸ್ಟಮೈಸ್ ಮಾಡಿದಾಗ, ಕಸ್ಟಮ್ ಮೆಟ್ರಿಕ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಸಂಗ್ರಹಿಸಿದ ಕ್ರಮದಲ್ಲಿ ಸಂಕೋಚನಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಅನ್ವಯಿಸಬಹುದು. ಹೆಚ್ಚುವರಿಯಾಗಿ, ಹೊಸ ಅಂಚಿನ ತೂಕವನ್ನು ಅವಲಂಬಿಸಿ ಕೆಲವು ಶಾರ್ಟ್ಕಟ್ಗಳನ್ನು ಮರು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಅಗತ್ಯವಿರಬಹುದು. ಇದು ಕೆಲಸ ಮಾಡಲು, ಸಂಕೋಚನದ ಕ್ರಮವನ್ನು ಮೆಟ್ರಿಕ್-ಸ್ವತಂತ್ರ ನೆಸ್ಟೆಡ್ ವಿಭಜನೆಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಲೆಕ್ಕ ಹಾಕಬೇಕಾಗುತ್ತದೆ. ಮೇಲೆ ವಿವರಿಸಿದಂತೆ ವಿಸ್ತರಣೆಗಳು ಮತ್ತು ಅನ್ವಯಗಳು ಸಿಎಚ್ಗಳು ಒಂದು ಆರಂಭಿಕ ನೋಡ್ನಿಂದ ಒಂದು ಗುರಿ ನೋಡ್ಗೆ ಕಡಿಮೆ ಮಾರ್ಗವನ್ನು ಹುಡುಕುತ್ತವೆ. ಇದನ್ನು ಒನ್-ಟು-ಒನ್ ಚಿಕ್ಕದಾದ ಮಾರ್ಗ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಉದಾಹರಣೆಗೆ ಕಾರ್-ನ್ಯಾವಿಗೇಷನ್ ವ್ಯವಸ್ಥೆಗಳಲ್ಲಿ ಇದನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಇತರ ಅನ್ವಯಿಕೆಗಳಲ್ಲಿ ರಸ್ತೆ ವಿಭಾಗಗಳಿಗೆ ಜಿಪಿಎಸ್ ಕುರುಹುಗಳನ್ನು ಹೊಂದಿಸುವುದು ಮತ್ತು ಸಂಚಾರ ಸಿಮ್ಯುಲೇಟರ್ಗಳನ್ನು ವೇಗಗೊಳಿಸುವುದು ಸೇರಿವೆ, ಇದು ಜಾಲಬಂಧದಲ್ಲಿನ ಎಲ್ಲಾ ಚಾಲಕರು ತೆಗೆದುಕೊಳ್ಳುವ ಸಂಭಾವ್ಯ ಮಾರ್ಗಗಳನ್ನು ಪರಿಗಣಿಸಬೇಕಾಗುತ್ತದೆ. ಮಾರ್ಗ ಮುನ್ಸೂಚನೆಯಲ್ಲಿ, ವಾಹನವು ಅದರ ಪ್ರಸ್ತುತ ಮತ್ತು ಹಿಂದಿನ ಸ್ಥಾನಗಳು ಅದರ ಆರಂಭಿಕ ಹಂತದಿಂದ ಯಾವುದೇ ಸಂಭವನೀಯ ಗುರಿಯವರೆಗಿನ ಕಡಿಮೆ ಮಾರ್ಗವನ್ನು ಎಷ್ಟು ಚೆನ್ನಾಗಿ ಒಪ್ಪಿಕೊಳ್ಳುತ್ತವೆ ಎಂಬುದನ್ನು ಲೆಕ್ಕಹಾಕುವ ಮೂಲಕ ವಾಹನವು ಎಲ್ಲಿಗೆ ಹೋಗುತ್ತದೆ ಎಂಬುದನ್ನು ಅಂದಾಜು ಮಾಡಲು ಪ್ರಯತ್ನಿಸುತ್ತದೆ. ಸಿಎಚ್ಎಸ್ ಬಳಸಿ ಇದನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡಬಹುದು. ಒಂದರಿಂದ ಅನೇಕ ಸನ್ನಿವೇಶಗಳಲ್ಲಿ, ಆರಂಭಿಕ ನೋಡ್ ಮತ್ತು ಗುರಿ ನೋಡ್ಗಳ ಗುಂಪನ್ನು ನೀಡಲಾಗುತ್ತದೆ ಮತ್ತು ಎಲ್ಲದಕ್ಕೂ ದೂರವನ್ನು ಲೆಕ್ಕ ಹಾಕಬೇಕಾಗುತ್ತದೆ. ಒಂದರಿಂದ ಅನೇಕ ಪ್ರಶ್ನೆಗಳಿಗೆ ಅತ್ಯಂತ ಪ್ರಮುಖವಾದ ಅಪ್ಲಿಕೇಶನ್ಗಳು ಪಾಯಿಂಟ್-ಆಫ್-ಇಂಟರೆಸ್ಟ್ ಸರ್ಚ್ಗಳಾಗಿವೆ. ಸಾಮಾನ್ಯ ಉದಾಹರಣೆಗಳಲ್ಲಿ ಭೌಗೋಳಿಕ ಅಂತರವನ್ನು ಮೆಟ್ರಿಕ್ ಎಂದು ಬಳಸುವ ಬದಲು ನಿಜವಾದ ಪ್ರಯಾಣದ ಸಮಯವನ್ನು ಬಳಸಿಕೊಂಡು ಹತ್ತಿರದ ಅನಿಲ ಕೇಂದ್ರ, ರೆಸ್ಟೋರೆಂಟ್ ಅಥವಾ ಅಂಚೆ ಕಚೇರಿಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಸೇರಿದೆ. ಅನೇಕರಿಂದ ಅನೇಕ ಚಿಕ್ಕದಾದ ಮಾರ್ಗ ಸನ್ನಿವೇಶದಲ್ಲಿ, ಆರಂಭಿಕ ನೋಡ್ಗಳ ಒಂದು ಸೆಟ್ ಮತ್ತು ಗುರಿ ನೋಡ್ಗಳ ಒಂದು ಸೆಟ್ ಅನ್ನು ನೀಡಲಾಗುತ್ತದೆ ಮತ್ತು ಎಲ್ಲದಕ್ಕೂ ದೂರವನ್ನು ಲೆಕ್ಕ ಹಾಕಬೇಕಾಗುತ್ತದೆ. ಇದನ್ನು ಉದಾಹರಣೆಗೆ ಲಾಜಿಸ್ಟಿಕ್ ಅನ್ವಯಿಕೆಗಳಲ್ಲಿ ಬಳಸಲಾಗುತ್ತದೆ. ಸಿಎಚ್ಎಸ್ ಅನ್ನು ಈ ಕೆಳಗಿನ ರೀತಿಯಲ್ಲಿ ಅನೇಕ ಪ್ರಶ್ನೆಗಳಿಗೆ ವಿಸ್ತರಿಸಬಹುದು. ಮೊದಲಿಗೆ, ಪ್ರತಿಯೊಂದರಿಂದಲೂ ಹಿಮ್ಮುಖವಾಗಿ ಮೇಲ್ಮುಖವಾಗಿ ಹುಡುಕಿ. ಈ ಹುಡುಕಾಟದ ಸಮಯದಲ್ಲಿ ಸ್ಕ್ಯಾನ್ ಮಾಡಲಾದ ಪ್ರತಿ ಶೃಂಗಕ್ಕೂ, ಒಂದು ಬಕೆಟ್ನಲ್ಲಿ ಒಂದು ಸ್ಟೋರ್. ನಂತರ, ಪ್ರತಿ ಖಾಲಿ ಇಲ್ಲದ ಬಕೆಟ್ಗಾಗಿ, ಅನುಗುಣವಾದ ಶೃಂಗದ ಮೇಲಿನ ಮಾರ್ಗವು ಯಾವುದೇ ಉತ್ತಮ ದೂರವನ್ನು ಸುಧಾರಿಸುತ್ತದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತಾ, ಪ್ರತಿಯೊಂದರಿಂದಲೂ ಮುಂದಕ್ಕೆ ಮೇಲ್ಮುಖವಾಗಿ ಹುಡುಕಾಟವನ್ನು ನಡೆಸಲಾಗುತ್ತದೆ. ಅಂದರೆ, ಯಾವುದಾದರೂ ಇದ್ದರೆ. ಕೆಲವು ಅನ್ವಯಗಳಿಗೆ ಒಂದರಿಂದ ಎಲ್ಲ ಲೆಕ್ಕಾಚಾರಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ, ಅಂದರೆ, ಮೂಲ ಶೃಂಗದಿಂದ ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಎಲ್ಲಾ ಇತರ ಶೃಂಗಗಳಿಗೆ ಇರುವ ದೂರವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು. ಡಿಜ್ಕ್ಸ್ಟ್ರಾ ಅಲ್ಗಾರಿದಮ್ ಪ್ರತಿ ಅಂಚಿಗೆ ನಿಖರವಾಗಿ ಒಮ್ಮೆ ಭೇಟಿ ನೀಡುವುದರಿಂದ ಮತ್ತು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಚಲಿಸುವುದರಿಂದ ಇದು ಸೈದ್ಧಾಂತಿಕವಾಗಿ ಸೂಕ್ತವಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಡಿಜ್ಕ್ಸ್ಟ್ರಾ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಮಾನಾಂತರಗೊಳಿಸುವುದು ಕಷ್ಟ ಮತ್ತು ಅದರ ಕೆಟ್ಟ ಸ್ಥಳದಿಂದಾಗಿ ಕ್ಯಾಶ್-ಆಪ್ಟಿಮಲ್ ಅಲ್ಲ. ಸಿಎಚ್ಎಸ್ ಅನ್ನು ಹೆಚ್ಚು ಕ್ಯಾಶ್-ಆಪ್ಟಿಮಲ್ ಅನುಷ್ಠಾನಕ್ಕೆ ಬಳಸಬಹುದು. ಇದಕ್ಕಾಗಿ, ಶಾರ್ಟ್ಕಟ್-ಪುಷ್ಟೀಕರಿಸಿದ ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಎಲ್ಲಾ ನೋಡ್ಗಳ ಮೇಲೆ ಮುಂದಕ್ಕೆ ಮೇಲ್ಮುಖವಾಗಿ ಹುಡುಕುವ ನಂತರ ಕೆಳಮುಖವಾಗಿ ಸ್ಕ್ಯಾನ್ ಮಾಡಲಾಗುತ್ತದೆ. ನಂತರದ ಕಾರ್ಯಾಚರಣೆಯು ಮೆಮೊರಿಯ ಮೂಲಕ ರೇಖೀಯ ಶೈಲಿಯಲ್ಲಿ ಸ್ಕ್ಯಾನ್ ಮಾಡುತ್ತದೆ, ಏಕೆಂದರೆ ನೋಡ್ಗಳನ್ನು ಪ್ರಾಮುಖ್ಯತೆಯ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಕ್ರಮದಲ್ಲಿ ಸಂಸ್ಕರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಅದಕ್ಕೆ ಅನುಗುಣವಾಗಿ ಮೆಮೊರಿಯಲ್ಲಿ ಇರಿಸಬಹುದು. ಗಮನಿಸಿ, ಇದು ಸಾಧ್ಯ ಏಕೆಂದರೆ ಎರಡನೇ ಹಂತದಲ್ಲಿ ನೋಡ್ಗಳನ್ನು ಸಂಸ್ಕರಿಸುವ ಕ್ರಮವು ಮೂಲ ನೋಡ್ನಿಂದ ಸ್ವತಂತ್ರವಾಗಿದೆ. ಉತ್ಪಾದನೆಯಲ್ಲಿ, ಕಾರು-ಸಂಚರಣೆ ವ್ಯವಸ್ಥೆಗಳು ನಿರೀಕ್ಷಿತ ಸಂಚಾರ ಮಾಹಿತಿಯನ್ನು ಬಳಸಿಕೊಂಡು ವೇಗದ ಪ್ರಯಾಣ ಮಾರ್ಗಗಳನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಮತ್ತು ಪರ್ಯಾಯ ಮಾರ್ಗಗಳನ್ನು ಪ್ರದರ್ಶಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ. ಎರಡನ್ನೂ ಸಿಎಚ್ಎಸ್ ಬಳಸಿ ಮಾಡಬಹುದು. ಮೊದಲನೆಯದನ್ನು ಸಮಯ-ಅವಲಂಬಿತ ಜಾಲಗಳೊಂದಿಗೆ ರೂಟಿಂಗ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಅಲ್ಲಿ ನಿರ್ದಿಷ್ಟ ಅಂಚಿನ ಪ್ರಯಾಣದ ಸಮಯವು ಸ್ಥಿರವಾಗಿರುವುದಿಲ್ಲ ಆದರೆ ಅಂಚನ್ನು ಪ್ರವೇಶಿಸುವಾಗ ದಿನದ ಸಮಯದ ಕಾರ್ಯವಾಗಿರುತ್ತದೆ. ಪರ್ಯಾಯ ಮಾರ್ಗಗಳು ಸುಗಮವಾಗಿ ಕಾಣಬೇಕು, ಚಿಕ್ಕದಾದ ಮಾರ್ಗಕ್ಕಿಂತ ಗಮನಾರ್ಹವಾಗಿ ಭಿನ್ನವಾಗಿರಬೇಕು ಆದರೆ ಗಮನಾರ್ಹವಾಗಿ ಉದ್ದವಾಗಿರಬಾರದು. ಸಿಎಚ್ಎಸ್ ಅನ್ನು ಒಂದೇ ಸಮಯದಲ್ಲಿ ಅನೇಕ ಮಾಪನಗಳನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸಲು ವಿಸ್ತರಿಸಬಹುದು; ಇದನ್ನು ಬಹು-ಮಾನದಂಡ ಮಾರ್ಗ ಯೋಜನೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಪ್ರಯಾಣದ ವೆಚ್ಚ ಮತ್ತು ಸಮಯ ಎರಡನ್ನೂ ಕಡಿಮೆ ಮಾಡಬಹುದು. ಮತ್ತೊಂದು ಉದಾಹರಣೆಯೆಂದರೆ ವಿದ್ಯುತ್ ಚಾಲಿತ ವಾಹನಗಳು, ಇದಕ್ಕಾಗಿ ಲಭ್ಯವಿರುವ ಬ್ಯಾಟರಿ ಚಾರ್ಜ್ ಬ್ಯಾಟರಿಯು ಖಾಲಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸದ ಕಾರಣ ಮಾನ್ಯ ಮಾರ್ಗಗಳನ್ನು ನಿರ್ಬಂಧಿಸುತ್ತದೆ. ಸಿದ್ಧಾಂತ ಸಂಕೋಚನ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳ ಪೂರ್ವ ಸಂಸ್ಕರಣೆ ಮತ್ತು ಪ್ರಶ್ನೆಯ ಕಾರ್ಯಕ್ಷಮತೆಯ ಮೇಲೆ ಹಲವಾರು ಮಿತಿಗಳನ್ನು ಸ್ಥಾಪಿಸಲಾಗಿದೆ. ಈ ಕೆಳಗಿನವು ಗ್ರಾಫ್ನಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆ, ಅಂಚುಗಳ ಸಂಖ್ಯೆ, ಹೆದ್ದಾರಿ ಆಯಾಮ, ಗ್ರಾಫ್ ವ್ಯಾಸ, ಮರದ ಆಳ ಮತ್ತು ಮರದ ಅಗಲವಾಗಿದೆ. ಸಂಕೋಚನ ಕ್ರಮಾನುಗತ ಕಾರ್ಯಕ್ಷಮತೆಯ ಮೊದಲ ವಿಶ್ಲೇಷಣೆಯು ಭಾಗಶಃ ಹೆದ್ದಾರಿ ಆಯಾಮ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಪ್ರಮಾಣವನ್ನು ಅವಲಂಬಿಸಿದೆ. ಈ ಪ್ರಮಾಣದ ವ್ಯಾಖ್ಯಾನವು ತಾಂತ್ರಿಕವಾಗಿದ್ದರೂ, ಪ್ರತಿಯೊಂದಕ್ಕೂ ವಿರಳವಾದ ಶೃಂಗಗಳ ಗುಂಪನ್ನು ಹೊಂದಿದ್ದರೆ ಅಂತರ್ಬೋಧೆಯಿಂದ ಗ್ರಾಫ್ ಒಂದು ಸಣ್ಣ ಹೆದ್ದಾರಿ ಆಯಾಮವನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಅಂದರೆ ಅದಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಉದ್ದದ ಪ್ರತಿ ಚಿಕ್ಕ ಮಾರ್ಗವು ಒಂದು ಶೃಂಗವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಹೆದ್ದಾರಿಯ ಆಯಾಮದ ನಿಖರವಾದ ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕ ಹಾಕುವುದು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಮತ್ತು ಡಬ್ಲ್ಯೂ [1]-ಹಾರ್ಡ್ ಆಗಿದೆ, ಆದರೆ ಗ್ರಿಡ್ಗಳಿಗೆ ಇದು ಹೆದ್ದಾರಿಯ ಆಯಾಮ ಎಂದು ತಿಳಿದಿದೆ. ಕಸ್ಟಮೈಸ್ ಮಾಡಬಹುದಾದ ಸಂಕೋಚನ ಶ್ರೇಣಿಯ ಕೆಲಸದಲ್ಲಿ ಪರ್ಯಾಯ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಲಾಗಿದೆ. ಪ್ರಶ್ನೆಯ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು ಹೀಗೆ ಸೀಮಿತಗೊಳಿಸಬಹುದು. ಮರದ ಆಳವನ್ನು ಮರದ ಅಗಲದ ದೃಷ್ಟಿಯಿಂದ ಬಂಧಿಸಬಹುದಾದ್ದರಿಂದ, ಇದು ಮಾನ್ಯವಾದ ಮೇಲಿನ ಮಿತಿಯೂ ಆಗಿದೆ. ಮುಖ್ಯ ಮೂಲವೆಂದರೆ ಆದರೆ ಕೆಟ್ಟ ಕೇಸ್ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯದ ಪರಿಣಾಮಗಳನ್ನು ಉತ್ತಮವಾಗಿ ವಿವರಿಸಲಾಗಿದೆ. ಪೂರ್ವ ಸಂಸ್ಕರಣಾ ಕಾರ್ಯಕ್ಷಮತೆ ಪ್ರಶ್ನೆ ಕಾರ್ಯಕ್ಷಮತೆ ಉಲ್ಲೇಖಗಳು ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಓಪನ್ ಸೋರ್ಸ್ ಅನುಷ್ಠಾನಗಳು https://www.graphhopper.com https://github.com/ifsttar/Tempus https://github.com/RoutingKit/RoutingKit http://project-osrm.org http://www.opentripplanner.org ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳು ರೂಟಿಂಗ್ ಕ್ರಮಾವಳಿಗಳನ್ನು ಹುಡುಕಿ