B*
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಬಿ * ("ಬಿ ಸ್ಟಾರ್" ಎಂದು ಉಚ್ಚರಿಸಲಾಗುತ್ತದೆ) ಒಂದು ಅತ್ಯುತ್ತಮ-ಮೊದಲ ಗ್ರಾಫ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು, ಇದು ನಿರ್ದಿಷ್ಟ ಆರಂಭಿಕ ನೋಡ್ನಿಂದ ಯಾವುದೇ ಗೋಲ್ ನೋಡ್ಗೆ (ಒಂದು ಅಥವಾ ಹೆಚ್ಚಿನ ಸಂಭವನೀಯ ಗುರಿಗಳಲ್ಲಿ) ಕನಿಷ್ಠ-ವೆಚ್ಚದ ಮಾರ್ಗವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಇದನ್ನು ಮೊದಲು ಹ್ಯಾನ್ಸ್ ಬರ್ಲಿನರ್ 1979ರಲ್ಲಿ ಪ್ರಕಟಿಸಿದರು, ಇದು ಎ * ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ಗೆ ಸಂಬಂಧಿಸಿದೆ. ಸಾರಾಂಶ ಅಲ್ಗಾರಿದಮ್ ಒಂದೇ ಬಿಂದು-ಮೌಲ್ಯದ ಅಂದಾಜುಗಳಿಗೆ ವಿರುದ್ಧವಾಗಿ ಮರದ ನೋಡ್ಗಳಿಗೆ ಮಧ್ಯಂತರಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ನಂತರ, ಮರದ ಎಲೆಯ ನೋಡ್ಗಳನ್ನು ಉನ್ನತ ಮಟ್ಟದ ನೋಡ್ಗಳಲ್ಲಿ ಒಂದು ಸ್ಪಷ್ಟವಾಗಿ "ಅತ್ಯುತ್ತಮ" ಮಧ್ಯಂತರವನ್ನು ಹೊಂದುವವರೆಗೆ ಹುಡುಕಬಹುದು. ವಿವರಗಳು ಅಂದಾಜುಗಳ ಬದಲಿಗೆ ಮಧ್ಯಂತರ ಮೌಲ್ಯಮಾಪನಗಳನ್ನು ಬಿ *-ಮರದ ಲೀಫ್ ನೋಡ್ಗಳಿಗೆ ಏಕ ಸಂಖ್ಯೆಗಳ ಬದಲಿಗೆ ಮಧ್ಯಂತರಗಳ ಮೌಲ್ಯಮಾಪನಗಳನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ಮಧ್ಯಂತರವು ಆ ನೋಡ್ನ ನಿಜವಾದ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರಬೇಕು. ಲೀಫ್ ನೋಡ್ಗಳಿಗೆ ಜೋಡಿಸಲಾದ ಎಲ್ಲಾ ಮಧ್ಯಂತರಗಳು ಈ ಗುಣವನ್ನು ತೃಪ್ತಿಪಡಿಸಿದರೆ, B * ಗೋಲು ಸ್ಥಿತಿಗೆ ಸೂಕ್ತವಾದ ಮಾರ್ಗವನ್ನು ಗುರುತಿಸುತ್ತದೆ. ಬ್ಯಾಕಪ್ ಪ್ರಕ್ರಿಯೆಯು ಮರದೊಳಗಿನ ಮಧ್ಯಂತರಗಳನ್ನು ಬ್ಯಾಕಪ್ ಮಾಡಲು, ಪೋಷಕರ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಮಕ್ಕಳ ಮೇಲಿನ ಗರಿಷ್ಠ ಮಿತಿಗಳಿಗೆ ಹೊಂದಿಸಲಾಗಿದೆ. ಪೋಷಕರ ಕೆಳಗಿನ ಮಿತಿಯನ್ನು ಮಕ್ಕಳ ಕೆಳಗಿನ ಮಿತಿಯ ಗರಿಷ್ಠ ಮಟ್ಟಕ್ಕೆ ನಿಗದಿಪಡಿಸಲಾಗಿದೆ. ವಿವಿಧ ಮಕ್ಕಳು ಈ ಮಿತಿಗಳನ್ನು ಪೂರೈಸಬಹುದು ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಹುಡುಕಾಟ ಬಿ * ಅನ್ನು ಕೊನೆಗೊಳಿಸುವುದರಿಂದ "ಸೆಪರೇಷನ್" ಅನ್ನು ರಚಿಸುವ ಸಲುವಾಗಿ ನೋಡ್ಗಳನ್ನು ವ್ಯವಸ್ಥಿತವಾಗಿ ವಿಸ್ತರಿಸುತ್ತದೆ, ಇದು ಮೂಲದ ನೇರ ಚೈಲ್ಡ್ನ ಕೆಳಗಿನ ಬೌಂಡ್ ಕನಿಷ್ಠ ಬೇರಾವುದೇ ನೇರ ಚೈಲ್ಡ್ನ ಮೇಲಿನ ಬೌಂಡ್ನಷ್ಟು ದೊಡ್ಡದಾಗಿದ್ದಾಗ ಸಂಭವಿಸುತ್ತದೆ. ಬೇರುಗಳಲ್ಲಿ ಪ್ರತ್ಯೇಕತೆಯನ್ನು ಸೃಷ್ಟಿಸುವ ಮರವು ಅತ್ಯುತ್ತಮ ಮಗು ಇತರ ಯಾವುದೇ ಮಗುವಿನಷ್ಟೇ ಉತ್ತಮವಾಗಿದೆ ಎಂಬುದಕ್ಕೆ ಪುರಾವೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪ್ರಾಯೋಗಿಕವಾಗಿ, ಸಂಕೀರ್ಣ ಹುಡುಕಾಟಗಳು ಪ್ರಾಯೋಗಿಕ ಸಂಪನ್ಮೂಲ ಮಿತಿಯೊಳಗೆ ಕೊನೆಗೊಳ್ಳದಿರಬಹುದು. ಆದ್ದರಿಂದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಸಮಯ ಅಥವಾ ಮೆಮೊರಿ ಮಿತಿಗಳಂತಹ ಕೃತಕ ಮುಕ್ತಾಯ ಮಾನದಂಡಗಳೊಂದಿಗೆ ಹೆಚ್ಚಿಸಲಾಗುತ್ತದೆ. ಕೃತಕ ಮಿತಿಯನ್ನು ಮುಟ್ಟಿದಾಗ, ಯಾವ ಕ್ರಮವನ್ನು ಆಯ್ಕೆ ಮಾಡಬೇಕೆಂಬುದರ ಬಗ್ಗೆ ನೀವು ಹ್ಯೂರಿಸ್ಟಿಕ್ ತೀರ್ಮಾನವನ್ನು ಮಾಡಬೇಕು. ಸಾಮಾನ್ಯವಾಗಿ, ಮರವು ನಿಮಗೆ ಮೂಲ ಗ್ರಂಥಿಗಳ ಮಧ್ಯಂತರಗಳಂತಹ ವ್ಯಾಪಕವಾದ ಪುರಾವೆಗಳನ್ನು ಒದಗಿಸುತ್ತದೆ. ಬಿ * ವಿಸ್ತರಣೆಯು ಅತ್ಯುತ್ತಮವಾದ ಮೊದಲ ಪ್ರಕ್ರಿಯೆಯಾಗಿದೆ, ಇದರರ್ಥ ಮರವನ್ನು ಹಾದುಹೋಗುವುದು ಬಹಳ ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ, ವಿಸ್ತರಿಸಲು ಎಲೆಯನ್ನು ಹುಡುಕಲು ಪದೇ ಪದೇ ಇಳಿಯುತ್ತದೆ. ವಿಸ್ತರಿಸಲು ನೋಡ್ ಅನ್ನು ಹೇಗೆ ಆಯ್ಕೆ ಮಾಡುವುದು ಎಂಬುದನ್ನು ಈ ವಿಭಾಗವು ವಿವರಿಸುತ್ತದೆ. (ಗಮನಿಸಿಃ ಮರವು ಮೆಮೊರಿ-ರೆಸಿಡೆಂಟ್ ಆಗಿರಲಿ ಅಥವಾ ಇಲ್ಲದಿರಲಿ, ಇದು ನೈಜ ಅಥವಾ ವರ್ಚುವಲ್ ಮೆಮೊರಿಯ ಮೂಲಕ ಅದನ್ನು ಹೇಗೆ ಮ್ಯಾಪ್ ಮಾಡಬಹುದು ಮತ್ತು/ಅಥವಾ ನಿರ್ವಹಿಸಬಹುದು ಎಂಬುದನ್ನು ಒಳಗೊಂಡಂತೆ ಒಟ್ಟಾರೆ ಅನುಷ್ಠಾನ ದಕ್ಷತೆಯ ಕಾರ್ಯವಾಗಿದೆ.) ಮರದ ಮೂಲದಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ ಎರಡು ತಂತ್ರಗಳಲ್ಲಿ ಒಂದನ್ನು ಅನ್ವಯಿಸುತ್ತದೆ, ಇದನ್ನು ಸಾಬೀತು-ಅತ್ಯುತ್ತಮ ಮತ್ತು ನಿರಾಕರಿಸು-ವಿಶ್ರಾಂತಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಪ್ರೂಫ್-ಬೆಸ್ಟ್ ಕಾರ್ಯತಂತ್ರದಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ ಅತ್ಯುನ್ನತ ಮೇಲಿನ ಬೌಂಡಿಗೆ ಸಂಬಂಧಿಸಿದ ನೋಡ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಆ ನೋಡ್ ಅನ್ನು ವಿಸ್ತರಿಸುವುದರಿಂದ ಅದರ ಕೆಳ ಮಿತಿಯು ಬೇರೆ ಯಾವುದೇ ನೋಡ್ನ ಮೇಲಿನ ಮಿತಿಗಿಂತ ಹೆಚ್ಚಾಗುತ್ತದೆ ಎಂಬ ಭರವಸೆ ಇದೆ. ನಿರಾಕರಿಸು-ವಿಶ್ರಾಂತಿ ತಂತ್ರವು ಎರಡನೇ ಅತಿ ಎತ್ತರದ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಹೊಂದಿರುವ ಮೂಲವನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಆ ನೋಡ್ ಅನ್ನು ವಿಸ್ತರಿಸುವ ಮೂಲಕ ನೀವು ಮೇಲಿನ ಮಿತಿಯನ್ನು ಅತ್ಯುತ್ತಮ ಚೈಲ್ಡ್ನ ಕೆಳ ಮಿತಿಗಿಂತ ಕಡಿಮೆ ಮಾಡಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ ಎಂಬ ಭರವಸೆ ಇದೆ. ಕಾರ್ಯತಂತ್ರದ ಆಯ್ಕೆ ಗಮನಿಸಿ, ಎಲ್ಲಾ ಕೆಳಗಿನ ಮಿತಿಗಳಲ್ಲಿ ಅತಿ ಹೆಚ್ಚಿನ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಹೊಂದಿರುವ ಚೈಲ್ಡ್ ನೋಡ್ನ ಕೆಳಗಿನ ಮಿತಿಯು ಅತ್ಯಧಿಕವಾಗುವವರೆಗೆ ನಿರಾಕರಿಸುವ-ವಿಶ್ರಾಂತಿ ತಂತ್ರವನ್ನು ಅನ್ವಯಿಸುವುದು ಅರ್ಥಹೀನವಾಗಿದೆ. ಮೂಲ ಅಲ್ಗಾರಿದಮ್ ವಿವರಣೆಯು ಯಾವ ಕಾರ್ಯತಂತ್ರವನ್ನು ಆಯ್ಕೆ ಮಾಡಬೇಕೆಂಬುದರ ಬಗ್ಗೆ ಹೆಚ್ಚಿನ ಮಾರ್ಗದರ್ಶನವನ್ನು ನೀಡಲಿಲ್ಲ. ಸಣ್ಣ ಮರವನ್ನು ಹೊಂದಿರುವ ಆಯ್ಕೆಯನ್ನು ವಿಸ್ತರಿಸುವಂತಹ ಹಲವಾರು ಸಮಂಜಸವಾದ ಪರ್ಯಾಯಗಳಿವೆ. ರೂಟ್-ಅಲ್ಲದ ನೋಡ್ಗಳಲ್ಲಿ ಕಾರ್ಯತಂತ್ರದ ಆಯ್ಕೆ ಒಮ್ಮೆ ಬೇರಿನ ಚೈಲ್ಡ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿದ ನಂತರ (ಪ್ರೂಫ್-ಬೆಸ್ಟ್ ಅಥವಾ ಡಿಸ್ಪ್ರೋವ್-ರೆಸ್ಟ್ ಬಳಸಿ) ನಂತರ ಅಲ್ಗಾರಿದಮ್ ಅತಿ ಹೆಚ್ಚು ಮೇಲಿನ ಮಿತಿಯನ್ನು ಹೊಂದಿರುವ ಚೈಲ್ಡ್ ಅನ್ನು ಪದೇ ಪದೇ ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ ಲೀಫ್ ನೋಡ್ಗೆ ಇಳಿಯುತ್ತದೆ. ಲೀಫ್ ನೋಡ್ ಅನ್ನು ತಲುಪಿದಾಗ, ಅಲ್ಗಾರಿದಮ್ ಎಲ್ಲಾ ಉತ್ತರಾಧಿಕಾರಿ ನೋಡ್ಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ ಮತ್ತು ಮೌಲ್ಯಮಾಪನ ಕಾರ್ಯವನ್ನು ಬಳಸಿಕೊಂಡು ಅವುಗಳಿಗೆ ಮಧ್ಯಂತರಗಳನ್ನು ನಿಯೋಜಿಸುತ್ತದೆ. ನಂತರ ಎಲ್ಲಾ ನೋಡ್ಗಳ ಮಧ್ಯಂತರಗಳನ್ನು ಬ್ಯಾಕಪ್ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಬ್ಯಾಕಪ್ ಮಾಡಬೇಕಾಗುತ್ತದೆ. ವರ್ಗಾವಣೆಗಳು ಸಾಧ್ಯವಾದಾಗ, ಬ್ಯಾಕ್-ಅಪ್ ಕಾರ್ಯಾಚರಣೆಯು ಆಯ್ಕೆ ಮಾರ್ಗದಲ್ಲಿ ಇಲ್ಲದ ನೋಡ್ಗಳ ಮೌಲ್ಯಗಳನ್ನು ಬದಲಾಯಿಸಬೇಕಾಗಬಹುದು. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ಗೆ ಮಕ್ಕಳಿಂದ ಎಲ್ಲಾ ಪೋಷಕರಿಗೆ ಪಾಯಿಂಟರ್ಗಳು ಬೇಕಾಗುತ್ತವೆ, ಇದರಿಂದಾಗಿ ಬದಲಾವಣೆಗಳನ್ನು ಪ್ರಚಾರ ಮಾಡಬಹುದು. ಬ್ಯಾಕಪ್ ಕಾರ್ಯಾಚರಣೆಯು ನೋಡ್ಗೆ ಸಂಬಂಧಿಸಿದ ಮಧ್ಯಂತರವನ್ನು ಬದಲಾಯಿಸದಿದ್ದಾಗ ಪ್ರಸರಣವು ನಿಲ್ಲಬಹುದು ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಮಧ್ಯಂತರಗಳು ತಪ್ಪಾಗಿದ್ದರೆ (ನೋಡ್ನ ಆಟದ-ಸೈದ್ಧಾಂತಿಕ ಮೌಲ್ಯವು ಮಧ್ಯಂತರದಲ್ಲಿ ಒಳಗೊಂಡಿಲ್ಲ ಎಂಬ ಅರ್ಥದಲ್ಲಿ), ಆಗ ಬಿ * ಗೆ ಸರಿಯಾದ ಮಾರ್ಗವನ್ನು ಗುರುತಿಸಲು ಸಾಧ್ಯವಾಗದಿರಬಹುದು. ಆದಾಗ್ಯೂ, ಅಲ್ಗಾರಿದಮ್ ಆಚರಣೆಯಲ್ಲಿ ದೋಷಗಳಿಗೆ ಸಾಕಷ್ಟು ದೃಢವಾಗಿದೆ. ಮಾವೆನ್ (ಸ್ಕ್ರ್ಯಾಬಲ್) ಪ್ರೋಗ್ರಾಂ ಮೌಲ್ಯಮಾಪನ ದೋಷಗಳು ಸಾಧ್ಯವಾದಾಗ ಬಿ * ನ ದೃಢತೆಯನ್ನು ಸುಧಾರಿಸುವ ನಾವೀನ್ಯತೆಯನ್ನು ಹೊಂದಿದೆ. ಬೇರ್ಪಡಿಸುವಿಕೆಯಿಂದಾಗಿ ಹುಡುಕಾಟವು ಕೊನೆಗೊಂಡರೆ, ಎಲ್ಲಾ ಮೌಲ್ಯಮಾಪನ ಮಧ್ಯಂತರಗಳನ್ನು ಸಣ್ಣ ಪ್ರಮಾಣದಲ್ಲಿ ವಿಸ್ತರಿಸಿದ ನಂತರ ಮಾವೆನ್ ಹುಡುಕಾಟವನ್ನು ಪುನರಾರಂಭಿಸುತ್ತಾನೆ. ಈ ನೀತಿಯು ಕ್ರಮೇಣ ಮರವನ್ನು ವಿಸ್ತರಿಸುತ್ತದೆ, ಅಂತಿಮವಾಗಿ ಎಲ್ಲಾ ದೋಷಗಳನ್ನು ಅಳಿಸಿಹಾಕುತ್ತದೆ. ಎರಡು ಆಟಗಾರರ ಆಟಗಳಿಗೆ ವಿಸ್ತರಣೆ ಬಿ * ಅಲ್ಗಾರಿದಮ್ ಎರಡು ಆಟಗಾರರ ನಿರ್ಣಾಯಕ ಶೂನ್ಯ-ಮೊತ್ತದ ಆಟಗಳಿಗೆ ಅನ್ವಯಿಸುತ್ತದೆ. ವಾಸ್ತವವಾಗಿ, ಆ ನೋಡ್ನಲ್ಲಿ ಚಲಿಸುವ ಬದಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ "ಅತ್ಯುತ್ತಮ" ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸುವುದು ಒಂದೇ ಬದಲಾವಣೆಯಾಗಿದೆ. ಆದ್ದರಿಂದ ನಿಮ್ಮ ಬದಿಯು ಚಲಿಸುತ್ತಿದ್ದರೆ ನೀವು ಗರಿಷ್ಠವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೀರಿ, ಮತ್ತು ಎದುರಾಳಿಯು ಚಲಿಸುತ್ತಿದ್ದರೆ ಕನಿಷ್ಠವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೀರಿ. ಸಮಾನವಾಗಿ, ನೀವು ಚಲಿಸುವ ಬದಿಯ ದೃಷ್ಟಿಕೋನದಿಂದ ಎಲ್ಲಾ ಮಧ್ಯಂತರಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಬಹುದು, ಮತ್ತು ನಂತರ ಬ್ಯಾಕ್-ಅಪ್ ಕಾರ್ಯಾಚರಣೆಯ ಸಮಯದಲ್ಲಿ ಮೌಲ್ಯಗಳನ್ನು ನಿರಾಕರಿಸಬಹುದು. ಅಪ್ಲಿಕೇಶನ್ಗಳು ಆಂಡ್ರ್ಯೂ ಪ್ಯಾಲೆ ಚೆಸ್ಗೆ ಬಿ * ಅನ್ನು ಅನ್ವಯಿಸಿದರು. ಶೂನ್ಯ-ಚಲನೆ ಹುಡುಕಾಟಗಳನ್ನು ಮಾಡುವ ಮೂಲಕ ಅಂತಿಮ ಬಿಂದುವಿನ ಮೌಲ್ಯಮಾಪನಗಳನ್ನು ನಿಯೋಜಿಸಲಾಗಿದೆ. ಒಂದೇ ಯಂತ್ರಾಂಶದಲ್ಲಿ ಚಾಲನೆಯಲ್ಲಿರುವ ಆಲ್ಫಾ-ಬೀಟಾ ಸಮರುವಿಕೆಯ ಸರ್ಚ್ ಇಂಜಿನ್ಗಳಿಗೆ ಹೋಲಿಸಿದರೆ ಈ ವ್ಯವಸ್ಥೆಯು ಎಷ್ಟು ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸಿದೆ ಎಂಬುದರ ಬಗ್ಗೆ ಯಾವುದೇ ವರದಿಗಳಿಲ್ಲ. ಮಾವೆನ್ (ಸ್ಕ್ರ್ಯಾಬಲ್) ಪ್ರೋಗ್ರಾಂ ಅಂತಿಮ ಆಟಗಳಿಗೆ ಬಿ * ಹುಡುಕಾಟವನ್ನು ಅನ್ವಯಿಸಿತು. ಹ್ಯೂರಿಸ್ಟಿಕ್ ಯೋಜನಾ ವ್ಯವಸ್ಥೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಅಂತಿಮ ಹಂತದ ಮೌಲ್ಯಮಾಪನಗಳನ್ನು ನಿಯೋಜಿಸಲಾಗಿದೆ. ಸಂಯೋಜಿತ ಆಟಗಳ ಗುಂಪಿನ ಮೊತ್ತದ ಆಟದಲ್ಲಿ ಅತ್ಯುತ್ತಮ ತಂತ್ರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಬಿ * ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಲಾಗಿದೆ. ಶಾಖೆ ಮತ್ತು ಬದ್ಧ ಉಲ್ಲೇಖಗಳನ್ನು ಸಹ ನೋಡಿ ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳು ರೂಟಿಂಗ್ ಕ್ರಮಾವಳಿಗಳು ಹುಡುಕಾಟ ಕ್ರಮಾವಳಿಗಳು ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಆಟ ಕೃತಕ ಬುದ್ಧಿಮತ್ತೆ