Randomized rounding
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನ ಮತ್ತು ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಶೋಧನೆಯಲ್ಲಿ, ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕವು ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಲು ಮತ್ತು ವಿಶ್ಲೇಷಿಸಲು ವ್ಯಾಪಕವಾಗಿ ಬಳಸಲಾಗುವ ವಿಧಾನವಾಗಿದೆ. ಅನೇಕ ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳು ನಿಖರವಾಗಿ (ಆಪ್ಟಿಮಾಲಿಟಿಗೆ) ಪರಿಹರಿಸಲು ಗಣನೆಗೆ ಒಳಗಾಗುವುದಿಲ್ಲ. ಅಂತಹ ಸಮಸ್ಯೆಗಳಿಗೆ, ಯಾದೃಚ್ಛಿಕ ರೌಂಡಿಂಗ್ ಅನ್ನು ವೇಗದ (ಬಹುಪದೀಯ ಸಮಯ) ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಲು ಬಳಸಬಹುದು-ಅಂದರೆ, ಯಾವುದೇ ಇನ್ಪುಟ್ ಅನ್ನು ನೀಡಿದರೆ ಸರಿಸುಮಾರು ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವನ್ನು ನೀಡಲು ಖಾತರಿಪಡಿಸುವ ಕ್ರಮಾವಳಿಗಳು. ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕದ ಮೂಲ ಕಲ್ಪನೆಯೆಂದರೆ, ಸಮಸ್ಯೆಯ ವಿಶ್ರಾಂತಿಯ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವನ್ನು ಮೂಲ ಸಮಸ್ಯೆಗೆ ಸರಿಸುಮಾರು ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವಾಗಿ ಪರಿವರ್ತಿಸುವುದು. ಪರಿಣಾಮವಾಗಿ ಬರುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಸಂಭವನೀಯ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ವಿಶ್ಲೇಷಿಸಲಾಗುತ್ತದೆ. ಮೂಲಭೂತ ವಿಧಾನವು ಮೂರು ಹಂತಗಳನ್ನು ಹೊಂದಿದೆಃ ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ (ಐಎಲ್ಪಿ) ಆಗಿ ಪರಿಹರಿಸಬೇಕಾದ ಸಮಸ್ಯೆಯನ್ನು ರೂಪಿಸಿ. ಐಎಲ್ಪಿಯ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ವಿಶ್ರಾಂತಿ (ಎಲ್ಪಿ) ಗೆ ಸೂಕ್ತವಾದ ಭಾಗಶಃ ಪರಿಹಾರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಎಲ್. ಪಿ. ಯ ಭಾಗಶಃ ದ್ರಾವಣವನ್ನು ಐ. ಎಲ್. ಪಿ. ಯ ಪೂರ್ಣಾಂಕ ದ್ರಾವಣಕ್ಕೆ ಸುತ್ತಿಕೊಳ್ಳಿ. (ಈ ವಿಧಾನವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ರೇಖೀಯ ಕಾರ್ಯಕ್ರಮಗಳೊಂದಿಗೆ ಅನ್ವಯಿಸಲಾಗುತ್ತದೆಯಾದರೂ, ಇತರ ರೀತಿಯ ಸಡಿಲಿಕೆಗಳನ್ನು ಕೆಲವೊಮ್ಮೆ ಬಳಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಗೋಯೆಮನ್ಸ್ ಮತ್ತು ವಿಲಿಯಮ್ಸನ್ ಅವರ ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್-ಆಧಾರಿತ ಮ್ಯಾಕ್ಸ್-ಕಟ್ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೋಡಿ. ಮೊದಲ ಹಂತದಲ್ಲಿ, ಸೂಕ್ತವಾದ ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಕ್ರಮಾವಳಿಯನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು ಸವಾಲಾಗಿದೆ. ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್, ನಿರ್ದಿಷ್ಟವಾಗಿ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂಗಳು ಮತ್ತು ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂಗಳನ್ನು ಬಳಸುವ ಮಾಡೆಲಿಂಗ್ನೊಂದಿಗೆ ಪರಿಚಯದ ಅಗತ್ಯವಿದೆ. ಅನೇಕ ಸಮಸ್ಯೆಗಳಿಗೆ, ಕೆಳಗಿನ ಸೆಟ್ ಕವರ್ ಉದಾಹರಣೆಯಲ್ಲಿರುವಂತೆ, ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ನೈಸರ್ಗಿಕ ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಇದೆ. (ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಕ್ರಮಾವಳಿಯು ಒಂದು ಸಣ್ಣ ಸಮಗ್ರತೆಯ ಅಂತರವನ್ನು ಹೊಂದಿರಬೇಕು; ವಾಸ್ತವವಾಗಿ ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಸಮಗ್ರತೆಯ ಅಂತರಗಳ ಮೇಲೆ ಮಿತಿಯನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ. ಎರಡನೇ ಹಂತದಲ್ಲಿ, ಯಾವುದೇ ಪ್ರಮಾಣಿತ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಆಪ್ಟಿಮಲ್ ಫ್ರ್ಯಾಕ್ಷನಲ್ ಪರಿಹಾರವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಮೂರನೇ ಹಂತದಲ್ಲಿ, ಭಾಗಶಃ ಪರಿಹಾರವನ್ನು ಪೂರ್ಣಾಂಕ ಪರಿಹಾರವಾಗಿ ಪರಿವರ್ತಿಸಬೇಕು (ಹೀಗಾಗಿ ಮೂಲ ಸಮಸ್ಯೆಗೆ ಪರಿಹಾರ). ಇದನ್ನು ಭಾಗಶಃ ಪರಿಹಾರವನ್ನು ಪೂರ್ಣಗೊಳಿಸುವುದು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಪರಿಣಾಮವಾಗಿ ಬರುವ ಪೂರ್ಣಾಂಕದ ದ್ರಾವಣವು (ಸಾಬೀತಾಗಿರುವಂತೆ) ಭಾಗಶಃ ದ್ರಾವಣದ ವೆಚ್ಚಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ವೆಚ್ಚವನ್ನು ಹೊಂದಿರಬಾರದು. ಇದು ಪೂರ್ಣಾಂಕ ದ್ರಾವಣದ ವೆಚ್ಚವು ಅತ್ಯುತ್ತಮ ಪೂರ್ಣಾಂಕ ದ್ರಾವಣದ ವೆಚ್ಚಕ್ಕಿಂತ ಹೆಚ್ಚು ದೊಡ್ಡದಾಗಿರುವುದಿಲ್ಲ ಎಂಬುದನ್ನು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಮೂರನೇ ಹಂತವನ್ನು (ರೌಂಡಿಂಗ್) ಮಾಡಲು ಬಳಸುವ ಮುಖ್ಯ ತಂತ್ರವೆಂದರೆ ಯಾದೃಚ್ಛಿಕತೆಯನ್ನು ಬಳಸುವುದು, ಮತ್ತು ನಂತರ ರೌಂಡಿಂಗ್ನಿಂದಾಗಿ ವೆಚ್ಚದಲ್ಲಿನ ಹೆಚ್ಚಳವನ್ನು ಬಂಧಿಸಲು ಸಂಭವನೀಯ ವಾದಗಳನ್ನು ಬಳಸುವುದು (ಕಾಂಬಿನೇಟರಿಕ್ಸ್ನಿಂದ ಸಂಭವನೀಯ ವಿಧಾನವನ್ನು ಅನುಸರಿಸುವುದು). ಅದರಲ್ಲಿ, ಬಯಸಿದ ಗುಣಲಕ್ಷಣಗಳೊಂದಿಗೆ ಪ್ರತ್ಯೇಕ ರಚನೆಗಳ ಅಸ್ತಿತ್ವವನ್ನು ತೋರಿಸಲು ಸಂಭವನೀಯ ವಾದಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಈ ಕೆಳಗಿನವುಗಳನ್ನು ತೋರಿಸಲು ಅಂತಹ ವಾದಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆಃ ಎಲ್ಪಿಯ ಯಾವುದೇ ಭಾಗಶಃ ಪರಿಹಾರವನ್ನು ನೀಡಿದರೆ, ಧನಾತ್ಮಕ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕ ಪ್ರಕ್ರಿಯೆಯು ಕೆಲವು ಅಪೇಕ್ಷಿತ ಮಾನದಂಡಗಳ ಪ್ರಕಾರ ಅಂದಾಜು ಮಾಡುವ ಪೂರ್ಣಾಂಕ ಪರಿಹಾರವನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಅಂತಿಮವಾಗಿ, ಮೂರನೇ ಹಂತವನ್ನು ಗಣನೆಗೆ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡಲು, ಒಂದು ಹಂತವು ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಅಂದಾಜು ಮಾಡುತ್ತದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ (ಇದರಿಂದಾಗಿ ಹಂತವು ಯಾದೃಚ್ಛಿಕವಾಗಿ ಉಳಿಯಬಹುದು) ಅಥವಾ ಸಾಮಾನ್ಯವಾಗಿ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಗಳ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ರೌಂಡಿಂಗ್ ಹಂತವನ್ನು ಬೇರ್ಪಡಿಸುತ್ತದೆ. ನಂತರದ ವಿಧಾನವು ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕದ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪರಿಣಾಮಕಾರಿ ನಿರ್ಣಾಯಕ ಪ್ರಕ್ರಿಯೆಯಾಗಿ ಪರಿವರ್ತಿಸುತ್ತದೆ, ಅದು ಉತ್ತಮ ಫಲಿತಾಂಶವನ್ನು ತಲುಪುತ್ತದೆ. ಉದಾಹರಣೆಃ ಸೆಟ್ ಕವರ್ ಸಮಸ್ಯೆ ಸೆಟ್ ಕವರ್ ಸಮಸ್ಯೆಗೆ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಲು ಯಾದೃಚ್ಛಿಕ ರೌಂಡಿಂಗ್ ಅನ್ನು ಹೇಗೆ ಬಳಸಬಹುದು ಎಂಬುದನ್ನು ಈ ಕೆಳಗಿನ ಉದಾಹರಣೆಯು ವಿವರಿಸುತ್ತದೆ. ಬ್ರಹ್ಮಾಂಡದ ಮೇಲೆ ಸೆಟ್ ಕವರ್ನ ಯಾವುದೇ ನಿದರ್ಶನವನ್ನು ಸರಿಪಡಿಸಿ. ಭಾಗಶಃ ಪರಿಹಾರವನ್ನು ಗಣನೆ ಮಾಡುವುದು ಹಂತ 1 ಕ್ಕೆ, ಈ ನಿದರ್ಶನಕ್ಕಾಗಿ ಸೆಟ್ ಕವರ್ಗಾಗಿ ಐಪಿ ಪ್ರಮಾಣಿತ ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಆಗಿರಲಿ. ಹಂತ 2 ಕ್ಕೆ, ಎಲ್ಪಿ ಐಪಿ ಯ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ವಿಶ್ರಾಂತಿ ಆಗಿರಲಿ, ಮತ್ತು ಯಾವುದೇ ಪ್ರಮಾಣಿತ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಎಲ್ಪಿಗೆ ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಇದು ಇನ್ಪುಟ್ ಗಾತ್ರದಲ್ಲಿ ಬಹುಪದಕ್ಕೆ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಎಲ್ಪಿಗೆ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರಗಳು ಪ್ರತಿ ಸೆಟ್ಗೆ ಋಣಾತ್ಮಕವಲ್ಲದ ತೂಕವನ್ನು ನಿಗದಿಪಡಿಸುವ ವಾಹಕಗಳಾಗಿವೆ, ಅಂದರೆ, ಪ್ರತಿ ಅಂಶಕ್ಕೆ, ಕವರ್ಗಳು-ಹೊಂದಿರುವ ಸೆಟ್ಗಳಿಗೆ ನಿಗದಿಪಡಿಸಿದ ಒಟ್ಟು ತೂಕ ಕನಿಷ್ಠ 1, ಅಂದರೆ, ಆಪ್ಟಿಮಲ್ ಪರಿಹಾರವು ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರವಾಗಿದೆ, ಅದರ ವೆಚ್ಚವು ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕದಾಗಿದೆ. ಯಾವುದೇ ಸೆಟ್ ಕವರ್ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರವನ್ನು ನೀಡುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ (ಎಲ್ಲಿಗಾಗಿ, ಇಲ್ಲದಿದ್ದರೆ). ಇದರ ವೆಚ್ಚವು ವೆಚ್ಚಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ, ಅಂದರೆ, ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಎಲ್ಪಿ ನಿರ್ದಿಷ್ಟ ಸೆಟ್-ಕವರ್ ಸಮಸ್ಯೆಯ ಸಡಿಲಿಕೆಯಾಗಿದೆ. ಎಲ್ಪಿಗೆ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರಗಳಲ್ಲಿ ಕನಿಷ್ಠ ವೆಚ್ಚವನ್ನು ಹೊಂದಿರುವುದರಿಂದ, ವೆಚ್ಚವು ಸೂಕ್ತವಾದ ಸೆಟ್ ಕವರ್ನ ವೆಚ್ಚದ ಮೇಲೆ ಕಡಿಮೆ ಮಿತಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕದ ಹಂತ 3ನೇ ಹಂತದಲ್ಲಿ, ನಾವು ಕನಿಷ್ಠ-ವೆಚ್ಚದ ಭಾಗಶಃ ಸೆಟ್ ಕವರ್ ಅನ್ನು ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪೂರ್ಣಾಂಕ ಪರಿಹಾರವಾಗಿ ಪರಿವರ್ತಿಸಬೇಕು (ನಿಜವಾದ ಸೆಟ್ ಕವರ್ಗೆ ಅನುಗುಣವಾಗಿ). ರೌಂಡಿಂಗ್ ಹಂತವು ಧನಾತ್ಮಕ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ, ವೆಚ್ಚದ ಒಂದು ಸಣ್ಣ ಅಂಶದೊಳಗೆ ವೆಚ್ಚವನ್ನು ಹೊಂದಿರಬೇಕು. ನಂತರ (ವೆಚ್ಚವು ಅತ್ಯುತ್ತಮ ಸೆಟ್ ಕವರ್ನ ವೆಚ್ಚದ ಮೇಲೆ ಕಡಿಮೆ ಮಿತಿಯಾಗಿರುವುದರಿಂದ), ವೆಚ್ಚವು ಅತ್ಯುತ್ತಮ ವೆಚ್ಚದ ಒಂದು ಸಣ್ಣ ಅಂಶದೊಳಗೆ ಇರುತ್ತದೆ. ಪ್ರಾರಂಭದ ಹಂತವಾಗಿ, ಅತ್ಯಂತ ನೈಸರ್ಗಿಕ ರೌಂಡಿಂಗ್ ಯೋಜನೆಯನ್ನು ಪರಿಗಣಿಸಿಃ ಪ್ರತಿಯೊಂದೂ ಸೆಟ್ಗೆ, ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ತೆಗೆದುಕೊಳ್ಳಿ, ಇಲ್ಲದಿದ್ದರೆ ತೆಗೆದುಕೊಳ್ಳಿ. ಈ ರೌಂಡಿಂಗ್ ಸ್ಕೀಮ್ನೊಂದಿಗೆ, ಆಯ್ದ ಸೆಟ್ಗಳ ನಿರೀಕ್ಷಿತ ವೆಚ್ಚವು ಗರಿಷ್ಠವಾಗಿದೆ, ಇದು ಫ್ರ್ಯಾಕ್ಷನಲ್ ಕವರ್ನ ವೆಚ್ಚವಾಗಿದೆ. ಇದು ಒಳ್ಳೆಯದು. ದುರದೃಷ್ಟವಶಾತ್, ವ್ಯಾಪ್ತಿ ಉತ್ತಮವಾಗಿಲ್ಲ. ಅಸ್ಥಿರಗಳು ಚಿಕ್ಕದಾಗಿದ್ದಾಗ, ಒಂದು ಅಂಶವು ಒಳಗೊಳ್ಳದಿರುವ ಸಂಭವನೀಯತೆಯು ಸುಮಾರು ಆದ್ದರಿಂದ ಅಂಶಗಳ ಒಂದು ಸ್ಥಿರ ಭಾಗವನ್ನು ಮಾತ್ರ ನಿರೀಕ್ಷೆಯಲ್ಲಿ ಒಳಗೊಳ್ಳಲಾಗುತ್ತದೆ. ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಒಳಗೊಳ್ಳಲು, ಪ್ರಮಾಣಿತ ರೌಂಡಿಂಗ್ ಯೋಜನೆಯು ಮೊದಲು ಸೂಕ್ತ ಅಂಶದಿಂದ ರೌಂಡಿಂಗ್ ಸಂಭವನೀಯತೆಗಳನ್ನು ಅಳೆಯುತ್ತದೆ. ಸ್ಟ್ಯಾಂಡರ್ಡ್ ರೌಂಡಿಂಗ್ ಸ್ಕೀಮ್ ಹೀಗಿದೆಃ ಒಂದು ನಿಯತಾಂಕವನ್ನು ಸರಿಪಡಿಸಿ. ಪ್ರತಿ ಸೆಟ್ಗೆ, ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ತೆಗೆದುಕೊಳ್ಳಿ, ಇಲ್ಲದಿದ್ದರೆ ತೆಗೆದುಕೊಳ್ಳಿ. ಸಂಭವನೀಯತೆಗಳನ್ನು ಹೆಚ್ಚಿಸುವುದರಿಂದ ನಿರೀಕ್ಷಿತ ವೆಚ್ಚವು ಹೆಚ್ಚಾಗುತ್ತದೆ, ಆದರೆ ಎಲ್ಲಾ ಅಂಶಗಳ ವ್ಯಾಪ್ತಿಯನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ. ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕದನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು ಇದರ ಉದ್ದೇಶವಾಗಿದೆ, ಇದರಿಂದಾಗಿ ಎಲ್ಲಾ ಅಂಶಗಳು ಶೂನ್ಯವಲ್ಲದ ಸಂಭವನೀಯತೆಯಿಂದ ಪ್ರಮಾಣೀಕರಿಸಲ್ಪಡುತ್ತವೆ. ಇಲ್ಲಿ ವಿವರವಾದ ವಿಶ್ಲೇಷಣೆ ಇದೆ. ಲೆಮ್ಮಾ (ರೌಂಡಿಂಗ್ ಯೋಜನೆಗೆ ಅಂದಾಜು ಗ್ಯಾರಂಟಿ) ಫಿಕ್ಸ್. ಸಕಾರಾತ್ಮಕ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ, ರೌಂಡಿಂಗ್ ಯೋಜನೆಯು ಗರಿಷ್ಠ ವೆಚ್ಚದ ಒಂದು ಸೆಟ್ ಕವರ್ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ (ಮತ್ತು ಆದ್ದರಿಂದ ವೆಚ್ಚವು ಅತ್ಯುತ್ತಮ ಸೆಟ್ ಕವರ್ನ ವೆಚ್ಚವನ್ನು ಮೀರಿಸುತ್ತದೆ). (ಗಮನಿಸಿಃ ಎಚ್ಚರಿಕೆಯಿಂದ ಇದನ್ನು ಕಡಿಮೆ ಮಾಡಬಹುದು.) ಈ ಕೆಳಗಿನ ಯಾವುದೇ "ಕೆಟ್ಟ" ಘಟನೆಗಳು ಸಂಭವಿಸದಿರುವವರೆಗೆ ಯಾದೃಚ್ಛಿಕ ರೌಂಡಿಂಗ್ ಯೋಜನೆಯ ಔಟ್ಪುಟ್ ಅಪೇಕ್ಷಿತ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿದೆಃ ಮಿತಿಮೀರಿದ ವೆಚ್ಚ, ಅಥವಾ ಕೆಲವು ಅಂಶಗಳಿಗೆ, ಒಳಗೊಳ್ಳಲು ವಿಫಲವಾಗುತ್ತದೆ. ಪ್ರತಿಯೊಬ್ಬರ ನಿರೀಕ್ಷೆಯೂ ಹೆಚ್ಚುಕಡಿಮೆ ಇರುತ್ತದೆ. ನಿರೀಕ್ಷೆಯ ರೇಖೀಯತೆಯಿಂದ, ನಿರೀಕ್ಷೆಯು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಹೀಗಾಗಿ, ಮಾರ್ಕೋವ್ನ ಅಸಮಾನತೆಯಿಂದ, ಮೇಲಿನ ಮೊದಲ ಕೆಟ್ಟ ಘಟನೆಯ ಸಂಭವನೀಯತೆಯು ಗರಿಷ್ಠವಾಗಿದೆ. ಉಳಿದ ಕೆಟ್ಟ ಘಟನೆಗಳಿಗೆ (ಪ್ರತಿ ಅಂಶಕ್ಕೆ ಒಂದು), ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ಅಂಶಕ್ಕೆ, ಒಳಗೊಳ್ಳದ ಸಂಭವನೀಯತೆಯು (ಇದು ಅಸಮಾನತೆಯನ್ನು ಬಳಸುತ್ತದೆ, ಇದು ಕಟ್ಟುನಿಟ್ಟಾಗಿದೆ) ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಹೀಗಾಗಿ, ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ, ಅಂಶವು ಆವರಿಸದಿರುವ ಸಂಭವನೀಯತೆ ಇದಕ್ಕಿಂತ ಕಡಿಮೆಯಿರುತ್ತದೆ. ಯೂನಿಯನ್ ಬೌಂಡ್ ಮೂಲಕ, ಕೆಟ್ಟ ಘಟನೆಗಳಲ್ಲಿ ಒಂದು ಸಂಭವಿಸುವ ಸಂಭವನೀಯತೆಯು ಅದಕ್ಕಿಂತ ಕಡಿಮೆಯಾಗಿದೆ. ಹೀಗಾಗಿ, ಧನಾತ್ಮಕ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಯಾವುದೇ ಕೆಟ್ಟ ಘಟನೆಗಳಿಲ್ಲ ಮತ್ತು ಇದು ಗರಿಷ್ಠ ವೆಚ್ಚದ ಒಂದು ಸೆಟ್ ಕವರ್ ಆಗಿದೆ. ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಗಳ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಕ್ಯೂಇಡಿ ಡೀರಾಂಡಮೈಸೇಶನ್ ಮೇಲಿನ ಲೆಮ್ಮಾವು ವೆಚ್ಚದ ಒಂದು ಸೆಟ್ ಕವರ್ನ ಅಸ್ತಿತ್ವವನ್ನು ತೋರಿಸುತ್ತದೆ). ಈ ಸಂದರ್ಭದಲ್ಲಿ ನಮ್ಮ ಗುರಿಯು ಸಮರ್ಥ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ, ಕೇವಲ ಅಸ್ತಿತ್ವದ ಪುರಾವೆಯಲ್ಲ, ಆದ್ದರಿಂದ ನಾವು ಪೂರ್ಣಗೊಳಿಸಿಲ್ಲ. ಒಂದು ವಿಧಾನವೆಂದರೆ ಸ್ವಲ್ಪ ಹೆಚ್ಚಿಸುವುದು, ನಂತರ ಯಶಸ್ಸಿನ ಸಂಭವನೀಯತೆಯು ಕನಿಷ್ಠ 1/4 ಎಂದು ತೋರಿಸಿ. ಈ ಮಾರ್ಪಾಡಿನೊಂದಿಗೆ, ಯಾದೃಚ್ಛಿಕ ರೌಂಡಿಂಗ್ ಹಂತವನ್ನು ಕೆಲವು ಬಾರಿ ಪುನರಾವರ್ತಿಸುವುದರಿಂದ ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಯಶಸ್ವಿ ಫಲಿತಾಂಶವನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಸಾಕು. ಆ ವಿಧಾನವು ಅಂದಾಜು ಅನುಪಾತವನ್ನು ದುರ್ಬಲಗೊಳಿಸುತ್ತದೆ. ಮೇಲಿನ ಅಸ್ತಿತ್ವದ ಪುರಾವೆಯ ಅಂದಾಜು ಅನುಪಾತಕ್ಕೆ ಹೊಂದಿಕೆಯಾಗುವಂತೆ ಖಾತರಿಪಡಿಸುವ ನಿರ್ಣಾಯಕ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುವ ವಿಭಿನ್ನ ವಿಧಾನವನ್ನು ನಾವು ಮುಂದೆ ವಿವರಿಸುತ್ತೇವೆ. ಈ ವಿಧಾನವನ್ನು ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಗಳ ವಿಧಾನ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ನಿರ್ಣಾಯಕ ಅಲ್ಗಾರಿದಮ್ ಯಾದೃಚ್ಛಿಕ ರೌಂಡಿಂಗ್ ಯೋಜನೆಯನ್ನು ಅನುಕರಿಸುತ್ತದೆಃ ಇದು ಪ್ರತಿ ಸೆಟ್ ಅನ್ನು ಪ್ರತಿಯಾಗಿ ಪರಿಗಣಿಸುತ್ತದೆ ಮತ್ತು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಆದರೆ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಪ್ರತಿ ಆಯ್ಕೆಯನ್ನು ಮಾಡುವ ಬದಲು, ಇದು ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯನ್ನು ಉಳಿಸಿಕೊಳ್ಳಲು ನಿರ್ಧಾರಕವಾಗಿ ಆಯ್ಕೆಯನ್ನು ಮಾಡುತ್ತದೆ, ಇಲ್ಲಿಯವರೆಗಿನ ಆಯ್ಕೆಗಳನ್ನು 1ಕ್ಕಿಂತ ಕಡಿಮೆ ನೀಡಲಾಗಿದೆ. ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯನ್ನು ಸರಿಹೊಂದಿಸುವುದು ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯನ್ನು 1 ಕ್ಕಿಂತ ಕಡಿಮೆ ಇಡಲು ನಾವು ಪ್ರತಿ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಅನುಕ್ರಮವಾಗಿ ಹೊಂದಿಸಲು ಬಯಸುತ್ತೇವೆ. ಇದನ್ನು ಮಾಡಲು, ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯ ಮೇಲೆ ನಮಗೆ ಉತ್ತಮ ಮಿತಿಯ ಅಗತ್ಯವಿದೆ. ಮೂಲ ಅಸ್ತಿತ್ವದ ಪುರಾವೆಯನ್ನು ಪರಿಷ್ಕರಿಸುವ ಮೂಲಕ ಬಂಧವು ಬರುತ್ತದೆ. ಆ ಪುರಾವೆಯು ಯಾದೃಚ್ಛಿಕ ವೇರಿಯೇಬಲ್ನ ನಿರೀಕ್ಷೆಯಿಂದ ವೈಫಲ್ಯದ ಸಂಭವನೀಯತೆಯನ್ನು ಸೂಚ್ಯವಾಗಿ ಬಂಧಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಕೊನೆಯಲ್ಲಿ ಬಹಿರಂಗಪಡಿಸದ ಅಂಶಗಳ ಗುಂಪು ಇರುತ್ತದೆ. ಯಾದೃಚ್ಛಿಕ ವೇರಿಯೇಬಲ್ ಸ್ವಲ್ಪ ನಿಗೂಢವಾಗಿ ಕಾಣಿಸಬಹುದು, ಆದರೆ ಇದು ಸಂಭವನೀಯ ಪುರಾವೆಯನ್ನು ವ್ಯವಸ್ಥಿತ ರೀತಿಯಲ್ಲಿ ಪ್ರತಿಬಿಂಬಿಸುತ್ತದೆ. ಮೊದಲ ಕೆಟ್ಟ ಘಟನೆಯ ಸಂಭವನೀಯತೆಯನ್ನು ಬಂಧಿಸಲು ಮಾರ್ಕೋವ್ನ ಅಸಮಾನತೆಯನ್ನು ಅನ್ವಯಿಸುವುದರಿಂದ ಮೊದಲ ಪದವು ಬರುತ್ತದೆ (ವೆಚ್ಚವು ತುಂಬಾ ಹೆಚ್ಚಾಗಿದೆ). ವೆಚ್ಚವು ತುಂಬಾ ಹೆಚ್ಚಿದ್ದರೆ ಅದು ಕನಿಷ್ಠ 1ಕ್ಕೆ ಕೊಡುಗೆ ನೀಡುತ್ತದೆ. ಎರಡನೇ ಪದವು ಎರಡನೇ ರೀತಿಯ ಕೆಟ್ಟ ಘಟನೆಗಳ ಸಂಖ್ಯೆಯನ್ನು (ಬಹಿರಂಗಪಡಿಸದ ಅಂಶಗಳು) ಎಣಿಸುತ್ತದೆ. ಯಾವುದೇ ಅಂಶವನ್ನು ತೆರೆದಿಟ್ಟರೆ ಅದು ಕನಿಷ್ಠ 1ಕ್ಕೆ ಕೊಡುಗೆ ನೀಡುತ್ತದೆ. ಹೀಗಾಗಿ, 1ಕ್ಕಿಂತ ಕಡಿಮೆ ಇರುವ ಯಾವುದೇ ಫಲಿತಾಂಶದಲ್ಲಿ, ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಒಳಗೊಂಡಿರಬೇಕು ಮತ್ತು ಲೆಮ್ಮಾದಿಂದ ಅಪೇಕ್ಷಿತ ಮಿತಿಯನ್ನು ಪೂರೈಸುವ ವೆಚ್ಚವನ್ನು ಹೊಂದಿರಬೇಕು. ಸಂಕ್ಷಿಪ್ತವಾಗಿ ಹೇಳುವುದಾದರೆ, ರೌಂಡಿಂಗ್ ಹಂತವು ವಿಫಲವಾದರೆ. ಇದು (ಮಾರ್ಕೋವ್ನ ಅಸಮಾನತೆಯಿಂದ) ವೈಫಲ್ಯದ ಸಂಭವನೀಯತೆಯ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಮೇಲಿನ ವಾದವು ಈಗಾಗಲೇ ಲೆಮ್ಮಾದ ಪುರಾವೆಯಲ್ಲಿ ಸೂಚ್ಯವಾಗಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಇದು ಲೆಕ್ಕಾಚಾರದ ಮೂಲಕವೂ ಸಹ ತೋರಿಸುತ್ತದೆ. ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಗಳ ವಿಧಾನವನ್ನು ಅನ್ವಯಿಸಲು, ರೌಂಡಿಂಗ್ ಹಂತವು ಮುಂದುವರೆದಂತೆ ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯನ್ನು ಬಂಧಿಸಲು ನಾವು ವಾದವನ್ನು ವಿಸ್ತರಿಸಬೇಕಾಗಿದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಇದನ್ನು ವ್ಯವಸ್ಥಿತ ರೀತಿಯಲ್ಲಿ ಮಾಡಬಹುದು, ಆದಾಗ್ಯೂ ಇದು ತಾಂತ್ರಿಕವಾಗಿ ಬೇಸರದ ಸಂಗತಿಯಾಗಿರಬಹುದು. ಆದ್ದರಿಂದ, ರೌಂಡಿಂಗ್ ಹಂತವು ಸೆಟ್ಗಳ ಮೂಲಕ ಪುನರಾವರ್ತನೆಯಾಗುವುದರಿಂದ ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯ ಬಗ್ಗೆ ಏನು? ಮಾರ್ಕೋವ್ ಅವರ ಅಸಮಾನತೆಯಿಂದ, ಯಾವುದೇ ಫಲಿತಾಂಶದಲ್ಲಿ ರೌಂಡಿಂಗ್ ಹಂತವು ವಿಫಲವಾದಾಗ, ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯು ಅದರ ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯಾಗಿರುತ್ತದೆ. ಮುಂದೆ ನಾವು ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯನ್ನು ಲೆಕ್ಕ ಹಾಕುತ್ತೇವೆ, ನಾವು ಮೂಲ ಪುರಾವೆಯಲ್ಲಿ ಷರತ್ತು ರಹಿತ ನಿರೀಕ್ಷೆಯನ್ನು ಲೆಕ್ಕ ಹಾಕಿದಂತೆಯೇ. ಕೆಲವು ಪುನರಾವರ್ತನೆಯ ಕೊನೆಯಲ್ಲಿ ರೌಂಡಿಂಗ್ ಪ್ರಕ್ರಿಯೆಯ ಸ್ಥಿತಿಯನ್ನು ಪರಿಗಣಿಸಿ. ಇಲ್ಲಿಯವರೆಗೆ ಪರಿಗಣಿಸಲಾದ ಸೆಟ್ಗಳನ್ನು ಸೂಚಿಸೋಣ (ಮೊದಲ ಸೆಟ್ಗಳು). (ಭಾಗಶಃ ನಿಯೋಜಿಸಲಾದ) ವಾಹಕವನ್ನು ಸೂಚಿಸೋಣ (ಆದ್ದರಿಂದ ಇದನ್ನು ನಿರ್ಧರಿಸಿದರೆ ಮಾತ್ರ). ಪ್ರತಿ ಸೆಟ್ಗೆ, 1 ಎಂದು ಹೊಂದಿಸಲಾಗುವ ಸಂಭವನೀಯತೆಯನ್ನು ಸೂಚಿಸೋಣ. ಇನ್ನೂ ಮುಚ್ಚಿರದ ಅಂಶಗಳನ್ನು ಒಳಗೊಂಡಿರಲಿ. ನಂತರ, ಇಲ್ಲಿಯವರೆಗೆ ಮಾಡಿದ ಆಯ್ಕೆಗಳನ್ನು ನೀಡಿದರೆ, ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯನ್ನು ನೀಡಲಾಗುತ್ತದೆ, ಅಂದರೆ, ಟಿಪ್ಪಣಿ, ಇದನ್ನು ಪುನರಾವರ್ತನೆಯ ನಂತರ ಮಾತ್ರ ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆ. ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯನ್ನು 1ಕ್ಕಿಂತ ಕಡಿಮೆ ಇಡುವುದು ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯನ್ನು 1ಕ್ಕಿಂತ ಕಡಿಮೆ ಇಡಲು, ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯನ್ನು 1ಕ್ಕಿಂತ ಕಡಿಮೆ ಇಡಲು ಸಾಕು. ಇದನ್ನು ಮಾಡಲು, ಹೆಚ್ಚಾಗುವ ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯನ್ನು ಉಳಿಸಿಕೊಳ್ಳಲು ಇದು ಸಾಕಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಇದನ್ನೇ ಮಾಡುತ್ತದೆ. ಅದನ್ನು (ಎಲ್ಲಿ) ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಇದು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ಹೊಂದಿಸಲ್ಪಡುತ್ತದೆ. ಮೂರನೇ ಪುನರಾವರ್ತನೆಯಲ್ಲಿ, ಅದನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಹೇಗೆ ಹೊಂದಿಸಬಹುದು? ಇದರ ಫಲಿತಾಂಶದ ಮೌಲ್ಯವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಇದನ್ನು ಸರಳವಾಗಿ ಹೊಂದಿಸಬಹುದು ಎಂದು ಅದು ತಿರುಗುತ್ತದೆ. ಏಕೆ ಎಂದು ನೋಡಲು, ಪುನರಾವರ್ತನೆ ಪ್ರಾರಂಭವಾಗುವ ಸಮಯದ ಬಿಂದುವಿನ ಮೇಲೆ ಕೇಂದ್ರೀಕರಿಸಿ. ಆ ಸಮಯದಲ್ಲಿ, ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆ, ಆದರೆ ಇನ್ನೂ ನಿರ್ಧರಿಸಲಾಗಿಲ್ಲ---ಇದು ಪುನರಾವರ್ತನೆಯಲ್ಲಿ ಹೇಗೆ ಹೊಂದಿಸಲಾಗಿದೆ ಎಂಬುದರ ಆಧಾರದ ಮೇಲೆ ಎರಡು ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಇದರ ಮೌಲ್ಯವನ್ನು ಸೂಚಿಸೋಣ. ಅನುಕ್ರಮವಾಗಿ 0 ಅಥವಾ 1ಕ್ಕೆ ಹೊಂದಿಸಲಾಗಿದೆಯೇ ಎಂಬುದರ ಆಧಾರದ ಮೇಲೆ ಎರಡು ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳನ್ನು ಸೂಚಿಸೋಣ ಮತ್ತು ಸೂಚಿಸೋಣ. ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯ ವ್ಯಾಖ್ಯಾನದ ಪ್ರಕಾರ, ಎರಡು ಪ್ರಮಾಣಗಳ ತೂಕದ ಸರಾಸರಿಯು ಯಾವಾಗಲೂ ಆ ಎರಡು ಪ್ರಮಾಣಗಳ ಕನಿಷ್ಠ ಪ್ರಮಾಣವಾಗಿರುವುದರಿಂದ, ಅದು ಅನುಸರಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಇದನ್ನೇ ಮಾಡುತ್ತದೆ. ವಿವರವಾಗಿ, ಇದರ ಅರ್ಥವೇನು? (ಎಲ್ಲಾ ಇತರ ಪ್ರಮಾಣಗಳು ಸ್ಥಿರವಾಗಿರುವಂತೆ) ಒಂದು ಕಾರ್ಯವೆಂದು ಪರಿಗಣಿಸಲಾಗುವ ಕಾರ್ಯವು ಒಂದು ರೇಖೀಯ ಕಾರ್ಯವಾಗಿದೆ, ಮತ್ತು ಆ ಕಾರ್ಯದಲ್ಲಿನ ಗುಣಾಂಕವು ಆದ್ದರಿಂದ, ಈ ಅಭಿವ್ಯಕ್ತಿಯು ಧನಾತ್ಮಕವಾಗಿದ್ದರೆ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು 0 ಗೆ ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ 1 ಗೆ ಹೊಂದಿಸಬೇಕು. ಇದು ಈ ಕೆಳಗಿನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುತ್ತದೆ. ಸೆಟ್ ಕವರ್ ಇನ್ಪುಟ್ಗಾಗಿ ಯಾದೃಚ್ಛಿಕ-ರೌಂಡಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಃ ಸೆಟ್ ಸಿಸ್ಟಮ್, ಯೂನಿವರ್ಸ್, ಕಾಸ್ಟ್ ವೆಕ್ಟರ್ ಔಟ್ಪುಟ್ಃ ಸೆಟ್ ಕವರ್ (ಸೆಟ್ ಕವರ್ಗಾಗಿ ಪ್ರಮಾಣಿತ ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂಗೆ ಪರಿಹಾರ) ಕನಿಷ್ಠ-ವೆಚ್ಚದ ಭಾಗಶಃ ಸೆಟ್ ಕವರ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ (ಎಲ್ಪಿ ವಿಶ್ರಾಂತಿಗೆ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರ). ಅವಕಾಶ ಮಾಡಿಕೊಡಿ. ಪ್ರತಿಯೊಂದಕ್ಕೂ ಬಿಡಿ. ಪ್ರತಿಯೊಂದಕ್ಕೂಃ ಮಾಡೋಣ. (ಇನ್ನೂ ನಿರ್ಧರಿಸದ ಸೆಟ್ಗಳನ್ನು ಒಳಗೊಂಡಿದೆ.) ನಂತರ ಹೊಂದಿಸಿದರೆ, ಇಲ್ಲದಿದ್ದರೆ ಹೊಂದಿಸಿ ಮತ್ತು. (ಇನ್ನೂ ಮುಚ್ಚಿರದ ಅಂಶಗಳನ್ನು ಒಳಗೊಂಡಿದೆ.) ಹಿಂತಿರುಗಿ. ಲೆಮ್ಮಾ (ಅಲ್ಗಾರಿದಮ್ಗೆ ಅಂದಾಜು ಗ್ಯಾರಂಟಿ) ಮೇಲಿನ ಅಲ್ಗಾರಿದಮ್ ಯಾವುದೇ (ಭಾಗಶಃ) ಸೆಟ್ ಕವರ್ನ ಕನಿಷ್ಠ ವೆಚ್ಚದ ಹೆಚ್ಚಿನ ಸಮಯಗಳಲ್ಲಿ ವೆಚ್ಚದ ಒಂದು ಸೆಟ್ ಕವರ್ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯು ಹೆಚ್ಚಾಗುವುದಿಲ್ಲ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಈ ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯು ಆರಂಭದಲ್ಲಿ 1ಕ್ಕಿಂತ ಕಡಿಮೆಯಾಗಿರುವುದರಿಂದ (ಹಿಂದೆ ತೋರಿಸಿರುವಂತೆ), ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯು 1ಕ್ಕಿಂತ ಕೆಳಗಿರುತ್ತದೆ ಎಂಬುದನ್ನು ಅಲ್ಗಾರಿದಮ್ ಖಚಿತಪಡಿಸುತ್ತದೆ. ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯು ಗರಿಷ್ಠ ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯಾಗಿರುವುದರಿಂದ, ಈ ರೀತಿಯಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ ವೈಫಲ್ಯದ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಯು 1ಕ್ಕಿಂತ ಕೆಳಗಿರುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಹೀಗಾಗಿ, ಕೊನೆಯಲ್ಲಿ, ಎಲ್ಲಾ ಆಯ್ಕೆಗಳನ್ನು ನಿರ್ಧರಿಸಿದಾಗ, ಅಲ್ಗಾರಿದಮ್ ಯಶಸ್ವಿ ಫಲಿತಾಂಶವನ್ನು ತಲುಪುತ್ತದೆ. ಅಂದರೆ, ಮೇಲಿನ ಅಲ್ಗಾರಿದಮ್ ಯಾವುದೇ (ಭಾಗಶಃ) ಸೆಟ್ ಕವರ್ನ ಕನಿಷ್ಠ ವೆಚ್ಚದ ಹೆಚ್ಚಿನ ಸಮಯಗಳಲ್ಲಿ ವೆಚ್ಚದ ಒಂದು ಸೆಟ್ ಕವರ್ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಟಿಪ್ಪಣಿಗಳು ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ ಯಾದೃಚ್ಛಿಕ ವೇರಿಯೇಬಲ್ನ ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯಿಂದ ಮಾರ್ಗದರ್ಶಿಸಲ್ಪಟ್ಟಿದೆ. ಕೆಲವು ಸಂದರ್ಭಗಳಲ್ಲಿ, ನಿಖರವಾದ ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯ ಬದಲಿಗೆ, ಕೆಲವು ಷರತ್ತುಬದ್ಧ ನಿರೀಕ್ಷೆಯ ಮೇಲೆ ಮೇಲಿನ ಮಿತಿಯನ್ನು (ಅಥವಾ ಕೆಲವೊಮ್ಮೆ ಕಡಿಮೆ ಮಿತಿಯನ್ನು) ಬಳಸಲಾಗುತ್ತದೆ. ಇದನ್ನು ನಿರಾಶಾವಾದಿ ಅಂದಾಜುಗಾರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಸಂಭವನೀಯ ವಿಧಾನದ ಇತರ ಅನ್ವಯಗಳಿಗೆ ಹೋಲಿಕೆ ಯಾದೃಚ್ಛಿಕ ರೌಂಡಿಂಗ್ ಹಂತವು ಸಂಭವನೀಯ ವಿಧಾನದ ಹೆಚ್ಚಿನ ಅನ್ವಯಗಳಿಗಿಂತ ಎರಡು ವಿಷಯಗಳಲ್ಲಿ ಭಿನ್ನವಾಗಿದೆಃ ರೌಂಡಿಂಗ್ ಹಂತದ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯು ಮುಖ್ಯವಾಗಿದೆ. ಇದನ್ನು ಉಪವಾಸದ ಮೂಲಕ ಕಾರ್ಯಗತಗೊಳಿಸಬೇಕು (ಉದಾಹರಣೆಗೆ. ಬಹುಪದ ಸಮಯ) ಕ್ರಮಾವಳಿ. ಯಾದೃಚ್ಛಿಕ ಪ್ರಯೋಗದ ಆಧಾರವಾಗಿರುವ ಸಂಭವನೀಯತೆಯ ವಿತರಣೆಯು ಸಮಸ್ಯೆಯ ನಿದರ್ಶನದ ವಿಶ್ರಾಂತಿಯ ಪರಿಹಾರದ ಕಾರ್ಯವಾಗಿದೆ. ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ನ ಕಾರ್ಯಕ್ಷಮತೆಯ ಖಾತರಿಯನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಈ ಸತ್ಯವು ನಿರ್ಣಾಯಕವಾಗಿದೆ---ಅಂದರೆ, ಯಾವುದೇ ಸಮಸ್ಯೆಯ ನಿದರ್ಶನಕ್ಕೆ, ಅಲ್ಗಾರಿದಮ್ ಆ ನಿರ್ದಿಷ್ಟ ನಿದರ್ಶನಕ್ಕೆ ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಅಂದಾಜು ಮಾಡುವ ಪರಿಹಾರವನ್ನು ನೀಡುತ್ತದೆ. ಹೋಲಿಸಿದರೆ, ಸಂಯೋಜನೆಯಲ್ಲಿ ಸಂಭವನೀಯ ವಿಧಾನದ ಅನ್ವಯಗಳು ಸಾಮಾನ್ಯವಾಗಿ ರಚನೆಗಳ ಅಸ್ತಿತ್ವವನ್ನು ತೋರಿಸುತ್ತವೆ, ಅದರ ವೈಶಿಷ್ಟ್ಯಗಳು ಇನ್ಪುಟ್ನ ಇತರ ನಿಯತಾಂಕಗಳನ್ನು ಅವಲಂಬಿಸಿವೆ. ಉದಾಹರಣೆಗೆ, ಟುರಾನ್ನ ಪ್ರಮೇಯವನ್ನು ಪರಿಗಣಿಸಿ, ಇದನ್ನು "ಸರಾಸರಿ ಹಂತದ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಯಾವುದೇ ಗ್ರಾಫ್ ಕನಿಷ್ಠ ಸ್ವತಂತ್ರ ಗಾತ್ರದ ಗುಂಪನ್ನು ಹೊಂದಿರಬೇಕು" ಎಂದು ಹೇಳಬಹುದು. (ಟುರಾನ್ನ ಪ್ರಮೇಯದ ಸಂಭವನೀಯ ಪುರಾವೆಗಾಗಿ ಇದನ್ನು ನೋಡಿ.) ಈ ಮಿತಿಯು ಬಿಗಿಯಾಗಿರುವ ಗ್ರಾಫ್ಗಳಿದ್ದರೂ, ಅದಕ್ಕಿಂತ ದೊಡ್ಡದಾದ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳೂ ಇವೆ. ಹೀಗಾಗಿ, ಗ್ರಾಫ್ನಲ್ಲಿ ಟುರಾನ್ನ ಪ್ರಮೇಯದಿಂದ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಎಂದು ತೋರಿಸಲಾದ ಸ್ವತಂತ್ರ ಗುಂಪಿನ ಗಾತ್ರವು, ಸಾಮಾನ್ಯವಾಗಿ, ಆ ಗ್ರಾಫ್ನ ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಿಂತ ಚಿಕ್ಕದಾಗಿರಬಹುದು. ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಪರಿಹರಿಸದೆ ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಗಳ ಯಾದೃಚ್ಛಿಕ ರೌಂಡಿಂಗ್ ವಿಧಾನವನ್ನು ಸಹ ನೋಡಿ. ಉಲ್ಲೇಖಗಳು. ಹೆಚ್ಚಿನ ಓದುವಿಕೆ ಕ್ರಮಾವಳಿಗಳು ಸಂಭವನೀಯ ವಾದಗಳು