Bidirectional search
ಬೈಡೈರೆಕ್ಷನಲ್ ಸರ್ಚ್ ಒಂದು ಗ್ರಾಫ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು, ಇದು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ನಲ್ಲಿ ಆರಂಭಿಕ ಶೃಂಗದಿಂದ ಗುರಿ ಶೃಂಗಕ್ಕೆ ಕಡಿಮೆ ಮಾರ್ಗವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಇದು ಎರಡು ಏಕಕಾಲಿಕ ಹುಡುಕಾಟಗಳನ್ನು ನಡೆಸುತ್ತದೆಃ ಒಂದು ಆರಂಭಿಕ ಸ್ಥಿತಿಯಿಂದ ಮುಂದಕ್ಕೆ, ಮತ್ತು ಗೋಲಿನಿಂದ ಹಿಂದಕ್ಕೆ, ಇಬ್ಬರೂ ಭೇಟಿಯಾದಾಗ ನಿಲ್ಲುತ್ತದೆ. ಈ ವಿಧಾನದ ಕಾರಣವೆಂದರೆ ಅನೇಕ ಸಂದರ್ಭಗಳಲ್ಲಿ ಇದು ವೇಗವಾಗಿರುತ್ತದೆಃ ಉದಾಹರಣೆಗೆ, ಹುಡುಕಾಟ ಸಮಸ್ಯೆಯ ಸಂಕೀರ್ಣತೆಯ ಸರಳೀಕೃತ ಮಾದರಿಯಲ್ಲಿ ಎರಡೂ ಹುಡುಕಾಟಗಳು ಕವಲೊಡೆಯುವ ಅಂಶ ಬಿ ಯೊಂದಿಗೆ ಮರವನ್ನು ವಿಸ್ತರಿಸುತ್ತವೆ ಮತ್ತು ಪ್ರಾರಂಭದಿಂದ ಗುರಿಯವರೆಗಿನ ಅಂತರವು ಡಿ ಆಗಿರುತ್ತದೆ, ಎರಡು ಹುಡುಕಾಟಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ಸಂಕೀರ್ಣತೆ ಒ (ಬಿಡಿ/2) ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ (ಬಿಗ್ ಒ ಸಂಕೇತದಲ್ಲಿ), ಮತ್ತು ಈ ಎರಡು ಹುಡುಕಾಟ ಸಮಯಗಳ ಮೊತ್ತವು ಪ್ರಾರಂಭದಿಂದ ಗುರಿಯವರೆಗೆ ಒಂದೇ ಹುಡುಕಾಟದಿಂದ ಉಂಟಾಗುವ ಒ (ಬಿಡಿ) ಸಂಕೀರ್ಣತೆಗಿಂತ ತುಂಬಾ ಕಡಿಮೆಯಾಗಿದೆ. ಆಂಡ್ರ್ಯೂ ಗೋಲ್ಡ್ಬರ್ಗ್ ಮತ್ತು ಇತರರು ಡಿಜ್ಕ್ಸ್ಟ್ರಾ ಅಲ್ಗಾರಿದಮ್ನ ದ್ವಿಮುಖ ಆವೃತ್ತಿಗೆ ಸರಿಯಾದ ಮುಕ್ತಾಯ ಷರತ್ತುಗಳನ್ನು ವಿವರಿಸಿದರು. ಎ * ಸರ್ಚ್ನಲ್ಲಿರುವಂತೆ, ದ್ವಿ-ದಿಕ್ಕಿನ ಹುಡುಕಾಟವನ್ನು ಗೋಲಿಗೆ (ಮುಂಭಾಗದ ಮರದಲ್ಲಿ) ಅಥವಾ ಆರಂಭದಿಂದ (ಹಿಂದುಳಿದ ಮರದಲ್ಲಿ) ಉಳಿದಿರುವ ಅಂತರದ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಂದಾಜಿನಿಂದ ನಿರ್ದೇಶಿಸಬಹುದು. ದ್ವಿ-ದಿಕ್ಕಿನ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಿದ ಮತ್ತು ಕಾರ್ಯಗತಗೊಳಿಸಿದ ಮೊದಲ ವ್ಯಕ್ತಿ. ಪ್ರಾರಂಭದಿಂದ ಹೊರಹೊಮ್ಮುವ ಹುಡುಕಾಟ ಮರಗಳು ಮತ್ತು ಗೋಲು ನೋಡ್ಗಳು ದ್ರಾವಣ ಸ್ಥಳದ ಮಧ್ಯದಲ್ಲಿ ಭೇಟಿಯಾಗಲು ವಿಫಲವಾದವು. ಬಿ. ಎಚ್. ಎಫ್. ಎಫ್. ಎ ಅಲ್ಗಾರಿದಮ್ ಈ ದೋಷವನ್ನು ಚಾಂಪಿಯಕ್ಸ್ (1977) ಅನ್ನು ಸರಿಪಡಿಸಿತು. ಸ್ವೀಕಾರಾರ್ಹ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಏಕ-ದಿಕ್ಕಿನ ಎ * ಅಲ್ಗಾರಿದಮ್ ಕಂಡುಹಿಡಿದ ಪರಿಹಾರವು ಕಡಿಮೆ ಮಾರ್ಗದ ಉದ್ದವನ್ನು ಹೊಂದಿದೆ; ಡಿ ಚಾಂಪಿಯಕ್ಸ್ (1983) ನಲ್ಲಿ ವಿವರಿಸಲಾದ ಬಿ. ಎಚ್. ಎಫ್. ಎಫ್. ಎ. 2 ದ್ವಿ-ದಿಕ್ಕಿನ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಆವೃತ್ತಿಗೆ ಅದೇ ಗುಣಲಕ್ಷಣವಿದೆ. ಇತರರಲ್ಲಿ, ಬಿ. ಎಚ್. ಎಫ್. ಎಫ್. ಎ. ಗಿಂತ ಬಿ. ಎಚ್. ಎಫ್. ಎಫ್. ಎ. 2 ಹೆಚ್ಚು ಎಚ್ಚರಿಕೆಯಿಂದ ಮುಕ್ತಾಯಗೊಳಿಸುವ ಷರತ್ತುಗಳನ್ನು ಹೊಂದಿದೆ. ಬೈಡೈರೆಕ್ಷನಲ್ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಸರ್ಚ್ ಎನ್ನುವುದು ಒಂದು ರಾಜ್ಯದಿಂದ ಮತ್ತೊಂದು ರಾಜ್ಯಕ್ಕೆ ಏಕಕಾಲದಲ್ಲಿ ನಡೆಯುವ ರಾಜ್ಯ ಬಾಹ್ಯಾಕಾಶ ಹುಡುಕಾಟವಾಗಿದೆ. ಇದು ಆಪರೇಟರ್ಗಳ ಮಾನ್ಯವಾದ ಪಟ್ಟಿಯನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ, ಅದನ್ನು ಅನ್ವಯಿಸಿದರೆ ಅದು ನಮಗೆ ನೀಡುತ್ತದೆ. ರಿವರ್ಸ್ ಸರ್ಚ್ಗೆ ಆಪರೇಟರ್ಗಳು ಇನ್ವರ್ಟಿಬಲ್ ಆಗಿರಬೇಕು ಎಂದು ತೋರುತ್ತದೆಯಾದರೂ, ಯಾವುದೇ ನೋಡ್ ಅನ್ನು ನೀಡಿದರೆ, ಪ್ರತಿಯೊಂದು ಮೂಲ ನೋಡ್ಗಳಿಂದ ಕೆಲವು ಮಾನ್ಯ ಆಪರೇಟರ್ ಇರುವಂತಹ ಮೂಲ ನೋಡ್ಗಳ ಗುಂಪನ್ನು ಕಂಡುಹಿಡಿಯಲು ಮಾತ್ರ ಸಾಧ್ಯವಾಗುತ್ತದೆ. ಇದನ್ನು ಅನೇಕವೇಳೆ ಮಾರ್ಗ-ಹುಡುಕುವ ಡೊಮೇನ್ನಲ್ಲಿರುವ ಏಕಮುಖ ರಸ್ತೆಗೆ ಹೋಲಿಸಲಾಗುತ್ತದೆಃ ಎರಡೂ ದಿಕ್ಕುಗಳಲ್ಲಿ ಪ್ರಯಾಣಿಸಲು ಸಾಧ್ಯವಾಗುವುದು ಅನಿವಾರ್ಯವಲ್ಲ, ಆದರೆ ರಸ್ತೆಯ ಕೊನೆಯಲ್ಲಿ ನಿಂತಾಗ ರಸ್ತೆಯ ಆರಂಭವನ್ನು ಸಂಭವನೀಯ ಮಾರ್ಗವಾಗಿ ನಿರ್ಧರಿಸುವುದು ಅವಶ್ಯಕವಾಗಿದೆ. ಅಂತೆಯೇ, ವಿಲೋಮ ಕಮಾನುಗಳನ್ನು ಹೊಂದಿರುವ ಅಂಚುಗಳಿಗೆ (ಅಂದರೆ. ಎರಡೂ ದಿಕ್ಕುಗಳಲ್ಲಿ ಚಲಿಸುವ ಚಾಪಗಳು) ಪ್ರತಿ ದಿಕ್ಕಿಗೂ ಸಮಾನ ವೆಚ್ಚವಾಗುವುದು ಅನಿವಾರ್ಯವಲ್ಲ. ಹಿಮ್ಮುಖ ಹುಡುಕಾಟವು ಯಾವಾಗಲೂ ವಿಲೋಮ ವೆಚ್ಚವನ್ನು ಬಳಸುತ್ತದೆ (ಅಂದರೆ. ಮುಂದಕ್ಕೆ ದಿಕ್ಕಿನಲ್ಲಿ ಆರ್ಕ್ನ ವೆಚ್ಚ). ಹೆಚ್ಚು ಔಪಚಾರಿಕವಾಗಿ, ಪೋಷಕರೊಂದಿಗಿನ ನೋಡ್ ಆಗಿದ್ದರೆ, ನಂತರ, ನಿಂದ ಗೆ ವೆಚ್ಚ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. (Auer Kaindl 2004) ಪರಿಭಾಷೆ ಮತ್ತು ಸಂಕೇತವು ಹುಡುಕಾಟ ವೃಕ್ಷದ ಕವಲೊಡೆಯುವ ಅಂಶವು ನೋಡ್ನಿಂದ ನೋಡ್ಗೆ ಚಲಿಸುವುದಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ವೆಚ್ಚವು ಮೂಲದಿಂದ ನೋಡ್ಗೆ ವೆಚ್ಚವು ನೋಡ್ ಮತ್ತು ಗುರಿಯ ನಡುವಿನ ಅಂತರದ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಂದಾಜು ಪ್ರಸ್ತುತ ಹುಡುಕಾಟ ದಿಕ್ಕನ್ನು (ಕೆಲವೊಮ್ಮೆ, ಕಾರ್ಯದೊಂದಿಗೆ ಗೊಂದಲಕ್ಕೀಡಾಗಬಾರದು) ಸೂಚಿಸುತ್ತದೆ. ಸಂಪ್ರದಾಯದ ಪ್ರಕಾರ, ಮುಂದೆ ದಿಕ್ಕಿನಲ್ಲಿ 1 ಮತ್ತು ಹಿಂದಕ್ಕೆ ದಿಕ್ಕಿನಲ್ಲಿ 2 (ಕ್ವಾ 1989) ವಿರುದ್ಧ ಹುಡುಕಾಟ ದಿಕ್ಕಿನಲ್ಲಿ (ಅಂದರೆ) ಸಮಾನವಾಗಿರುತ್ತದೆ. ಡಿ ದಿಕ್ಕಿನಲ್ಲಿರುವ ಶೋಧ ಮರವು, ಒಂದು ವೇಳೆ, ಮೂಲವು ಎಲೆಗಳಾಗಿದ್ದರೆ (ಕೆಲವೊಮ್ಮೆ ಎಂದು ಉಲ್ಲೇಖಿಸಲಾಗುತ್ತದೆ). ಈ ಗುಂಪಿನಿಂದಲೇ ವಿಸ್ತರಣೆಗೆ ನೋಡ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ. ದ್ವಿಮುಖ ಹುಡುಕಾಟದಲ್ಲಿ, ಇವುಗಳನ್ನು ಕೆಲವೊಮ್ಮೆ ಹುಡುಕಾಟ 'ಗಡಿಗಳು' ಅಥವಾ 'ತರಂಗಮುಖಗಳು' ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಇದು ಹುಡುಕಾಟವನ್ನು ಚಿತ್ರಾತ್ಮಕವಾಗಿ ಪ್ರತಿನಿಧಿಸಿದಾಗ ಅವು ಹೇಗೆ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತವೆ ಎಂಬುದನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಈ ರೂಪಕದಲ್ಲಿ, ವಿಸ್ತರಣೆಯ ಹಂತದಲ್ಲಿ, ಒಂದು ತರಂಗಮುಖದ ನೋಡ್ ಎದುರಾಳಿ ತರಂಗಮುಖದಲ್ಲಿ ಉತ್ತರಾಧಿಕಾರಿಗಳನ್ನು ಹೊಂದಿರುವಾಗ 'ಘರ್ಷಣೆ' ಸಂಭವಿಸುತ್ತದೆ. ಲೀಫ್ ಅಲ್ಲದ ನೋಡ್ಗಳು. ಈ ಸೆಟ್ ಈಗಾಗಲೇ ಹುಡುಕಾಟ ವಿಧಾನಗಳು ಭೇಟಿ ನೀಡಿದ ನೋಡ್ಗಳನ್ನು ಒಳಗೊಂಡಿದೆ, ಎರಡೂ ದಿಕ್ಕಿನ ಕ್ರಮಾವಳಿಗಳನ್ನು ವಿಶಾಲವಾಗಿ ಮೂರು ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದುಃ ಫ್ರಂಟ್-ಟು-ಫ್ರಂಟ್, ಫ್ರಂಟ್-ಟು-ಬ್ಯಾಕ್ (ಅಥವಾ ಫ್ರಂಟ್-ಟು-ಎಂಡ್), ಮತ್ತು ಪೆರಿಮೀಟರ್ ಸರ್ಚ್ (ಕೈಂಡ್ಲ್ ಕೈನ್ಜ್ 1997). ಇವು ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅನ್ನು ಲೆಕ್ಕ ಹಾಕಲು ಬಳಸುವ ಕಾರ್ಯದಿಂದ ಭಿನ್ನವಾಗಿರುತ್ತವೆ. ಫ್ರಂಟ್-ಟು-ಬ್ಯಾಕ್ ಅಲ್ಗಾರಿದಮ್ಗಳು ನೋಡ್ನ ಮೌಲ್ಯವನ್ನು ವಿರುದ್ಧ ಹುಡುಕಾಟ ವೃಕ್ಷದ ಮೂಲ ಮತ್ತು ನಡುವೆ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಂದಾಜನ್ನು ಬಳಸಿಕೊಂಡು ಲೆಕ್ಕ ಹಾಕುತ್ತವೆ. ಫ್ರಂಟ್-ಟು-ಬ್ಯಾಕ್ ಮೂರು ವಿಭಾಗಗಳಲ್ಲಿ ಅತ್ಯಂತ ಸಕ್ರಿಯವಾಗಿ ಸಂಶೋಧಿಸಲ್ಪಟ್ಟಿದೆ. ಪ್ರಸ್ತುತ ಅತ್ಯುತ್ತಮ ಅಲ್ಗಾರಿದಮ್ (ಕನಿಷ್ಠ ಹದಿನೈದು ಪಝಲ್ ಡೊಮೇನ್ನಲ್ಲಿ) ಬಯೋಮ್ಯಾಕ್ಸ್-ಬಿಎಸ್ * ಎಫ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ, ಇದನ್ನು ಔರ್ ಮತ್ತು ಕೈಂಡ್ಲ್ (ಔರ್, ಕೈಂಡ್ಲ್ 2004) ರಚಿಸಿದ್ದಾರೆ. ಮುಂಭಾಗದಿಂದ ಮುಂಭಾಗಕ್ಕೆ ಕ್ರಮಾವಳಿಗಳು ನೋಡ್ನ ಮೌಲ್ಯವನ್ನು ಮತ್ತು ಅದರ ಕೆಲವು ಉಪಗುಂಪುಗಳ ನಡುವಿನ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಂದಾಜನ್ನು ಬಳಸಿಕೊಂಡು ಲೆಕ್ಕ ಹಾಕುತ್ತವೆ. ಅಂಗೀಕೃತ ಉದಾಹರಣೆಯೆಂದರೆ ಬಿ. ಎಚ್. ಎಫ್. ಎಫ್. ಎ (ಬೈಡೈರೆಕ್ಷನಲ್ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಫ್ರಂಟ್-ಟು-ಫ್ರಂಟ್ ಅಲ್ಗಾರಿದಮ್), ಅಲ್ಲಿ ಕಾರ್ಯವನ್ನು ಪ್ರಸ್ತುತ ನೋಡ್ ಮತ್ತು ಎದುರಾಳಿ ಮುಂಭಾಗದಲ್ಲಿರುವ ನೋಡ್ಗಳ ನಡುವಿನ ಎಲ್ಲಾ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಂದಾಜುಗಳ ಕನಿಷ್ಠ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಅಥವಾ, ಔಪಚಾರಿಕವಾಗಿಃ ಎಲ್ಲಿ ಸ್ವೀಕಾರಾರ್ಹವಾದದ್ದನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ (ಅಂದರೆ. ನೋಡ್ಗಳು ಮತ್ತು ನೋಡ್ಗಳ ನಡುವಿನ ಅಂತರದ) ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಂದಾಜು. ಮುಂಭಾಗದಿಂದ ಮುಂದಕ್ಕೆ ಗಣನೆಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಅತಿಯಾದ ಬೇಡಿಕೆಯಿಂದ ಬಳಲುತ್ತದೆ. ಪ್ರತಿ ಬಾರಿ ಒಂದು ನೋಡ್ ಅನ್ನು ತೆರೆದ ಪಟ್ಟಿಯಲ್ಲಿ ಸೇರಿಸಿದಾಗ, ಅದರ ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕ ಹಾಕಬೇಕು. ಇದು ಮೇಲೆ ವಿವರಿಸಿದಂತೆ, ಎದುರಾಳಿ ಗುಂಪಿನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ನೋಡ್ನಿಂದ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಂದಾಜನ್ನು ಲೆಕ್ಕ ಹಾಕುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಎಲ್ಲಾ ಡೊಮೇನ್ಗಳಿಗೆ ಸೆಟ್ಗಳು ಗಾತ್ರದಲ್ಲಿ ಘಾತೀಯವಾಗಿ ಹೆಚ್ಚಾಗುತ್ತವೆ. ಉಲ್ಲೇಖಗಳು. .. .. .. ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳು ಹುಡುಕಾಟ ಕ್ರಮಾವಳಿಗಳು