Next-fit bin packing
ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಎಂಬುದು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ಗಾಗಿ ಆನ್ಲೈನ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಇದರ ಇನ್ಪುಟ್ ವಿವಿಧ ಗಾತ್ರದ ವಸ್ತುಗಳ ಪಟ್ಟಿಯಾಗಿದೆ. ಇದರ ಉತ್ಪಾದನೆಯು ಒಂದು ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ-ಪ್ರತಿ ಡಬ್ಬಿಯಲ್ಲಿನ ವಸ್ತುಗಳ ಗಾತ್ರಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದಿರುವಂತೆ, ವಸ್ತುಗಳನ್ನು ನಿಗದಿತ ಸಾಮರ್ಥ್ಯದ ಡಬ್ಬಿಗಳಾಗಿ ವಿಭಜಿಸುವುದು. ಆದರ್ಶಪ್ರಾಯವಾಗಿ, ನಾವು ಸಾಧ್ಯವಾದಷ್ಟು ಕಡಿಮೆ ತೊಟ್ಟಿಗಳನ್ನು ಬಳಸಲು ಬಯಸುತ್ತೇವೆ, ಆದರೆ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಎನ್ಪಿ-ಕಠಿಣ ಸಮಸ್ಯೆಯಾಗಿದೆ. ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅನ್ನು ಬಳಸುತ್ತದೆಃ ಇದು ಪ್ರಸ್ತುತ ಬಿನ್ ಅನ್ನು ಇರಿಸುತ್ತದೆ, ಅದು ಆರಂಭದಲ್ಲಿ ಖಾಲಿಯಾಗಿರುತ್ತದೆ. ಒಂದು ವಸ್ತುವು ಬಂದಾಗ, ಅದು ಪ್ರಸ್ತುತ ಡಬ್ಬಿಯಲ್ಲಿ ಸರಿಹೊಂದುತ್ತದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತದೆ. ಅದು ಸರಿಹೊಂದಿದರೆ, ಅದನ್ನು ಅದರೊಳಗೆ ಇರಿಸಲಾಗುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಪ್ರಸ್ತುತ ಬಿನ್ ಅನ್ನು ಮುಚ್ಚಲಾಗುತ್ತದೆ, ಹೊಸ ಬಿನ್ ಅನ್ನು ತೆರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಬರುವ ವಸ್ತುವನ್ನು ಈ ಹೊಸ ಬಿನ್ ಒಳಗೆ ಇರಿಸಲಾಗುತ್ತದೆ. ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಎನ್ನುವುದು ಒಂದು ಸೀಮಿತ ಜಾಗದ ಕ್ರಮಾವಳಿ-ಯಾವುದೇ ಸಮಯದಲ್ಲಿ ತೆರೆಯಲು ಕೇವಲ ಒಂದು ಭಾಗಶಃ ತುಂಬಿದ ಬಿನ್ ಮಾತ್ರ ಬೇಕಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಡೇವಿಡ್ ಎಸ್. ಜಾನ್ಸನ್ ಅವರು 1973 ರಲ್ಲಿ ತಮ್ಮ ಡಾಕ್ಟರೇಟ್ ಪ್ರಬಂಧದಲ್ಲಿ ಅಧ್ಯಯನ ಮಾಡಿದರು. ರನ್ ಟೈಮ್ ನೆಕ್ಸ್ಟ್ಫಿಟ್ನ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು ಈ ಮೂಲಕ ಸೀಮಿತಗೊಳಿಸಬಹುದು, ಪಟ್ಟಿಯಲ್ಲಿರುವ ಐಟಂಗಳ ಸಂಖ್ಯೆ ಎಲ್ಲಿದೆ. ಅಂದಾಜು ಅನುಪಾತವು ಎನ್ಎಫ್ (ಎಲ್) ನಿಂದ ನೆಕ್ಸ್ಟ್ಫಿಟ್ ಬಳಸುವ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ ಮತ್ತು ಒಪಿಟಿ (ಎಲ್) ನಿಂದ ಪಟ್ಟಿಗೆ ಸಾಧ್ಯವಾದಷ್ಟು ಅತ್ಯುತ್ತಮ ಸಂಖ್ಯೆಯ ತೊಟ್ಟಿಗಳನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಪುರಾವೆಯ ಒಳನೋಟವು ಈ ಕೆಳಗಿನಂತಿದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ಬಳಸುವ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಅತ್ಯುತ್ತಮ ಸಂಖ್ಯೆಯ ತೊಟ್ಟಿಗಳಿಗಿಂತ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚಾಗಿರುವುದಿಲ್ಲ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, 2 ತೊಟ್ಟಿಗಳು ಗರಿಷ್ಠ ಅರ್ಧ ತುಂಬಿರುವುದು ಅಸಾಧ್ಯ ಏಕೆಂದರೆ ಅಂತಹ ಸಾಧ್ಯತೆಯು ಸೂಚಿಸುವುದೇನೆಂದರೆ, ಒಂದು ಹಂತದಲ್ಲಿ, ನಿಖರವಾಗಿ ಒಂದು ತೊಟ್ಟಿ ಗರಿಷ್ಠ ಅರ್ಧ ತುಂಬಿತ್ತು ಮತ್ತು ಗರಿಷ್ಠ ಗಾತ್ರದ ವಸ್ತುವಿಗೆ ಸರಿಹೊಂದುವಂತೆ ಹೊಸದನ್ನು ತೆರೆಯಲಾಯಿತು. ಆದರೆ ಮೊದಲನೆಯದು ಕನಿಷ್ಠ ಒಂದು ಜಾಗವನ್ನು ಹೊಂದಿರುವುದರಿಂದ, ಅಲ್ಗಾರಿದಮ್ ಗರಿಷ್ಠ ಗಾತ್ರದ ಯಾವುದೇ ವಸ್ತುವಿಗೆ ಹೊಸ ಬಿನ್ ಅನ್ನು ತೆರೆಯುವುದಿಲ್ಲ. ಬಿನ್ ಅನ್ನು ಅದಕ್ಕಿಂತ ಹೆಚ್ಚು ತುಂಬಿದ ನಂತರ ಅಥವಾ ಅದಕ್ಕಿಂತ ದೊಡ್ಡ ಗಾತ್ರದ ವಸ್ತುವು ಬಂದರೆ, ಅಲ್ಗಾರಿದಮ್ ಹೊಸ ಬಿನ್ ಅನ್ನು ತೆರೆಯಬಹುದು. ಹೀಗಾಗಿ ನಮ್ಮಲ್ಲಿ ತೊಟ್ಟಿಗಳಿದ್ದರೆ, ಕನಿಷ್ಠ ತೊಟ್ಟಿಗಳು ಅರ್ಧಕ್ಕಿಂತ ಹೆಚ್ಚು ತುಂಬಿರುತ್ತವೆ. ಆದ್ದರಿಂದ,. ಇದು ಆಪ್ಟಿಮಮ್ ಮೌಲ್ಯದ ಕಡಿಮೆ ಮಿತಿಯಾಗಿರುವುದರಿಂದ, ನಾವು ಅದನ್ನು ಪಡೆಯುತ್ತೇವೆ. ಲೋವರ್ ಬೌಂಡ್ ಪ್ರತಿಯೊಂದಕ್ಕೂ, ಮತ್ತು ಅಂತಹ ಒಂದು ಪಟ್ಟಿ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ಅದು ಹೊಂದಿರುವ ಪಟ್ಟಿಗಳ ಕುಟುಂಬವನ್ನು ಅದರೊಂದಿಗೆ ನೀಡಲಾಗಿದೆ. ಈ ಪಟ್ಟಿಗೆ ಸೂಕ್ತವಾದ ಪರಿಹಾರವು ಗಾತ್ರದ ಎರಡು ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುವ ತೊಟ್ಟಿಗಳನ್ನು ಮತ್ತು ಗಾತ್ರದ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುವ ಒಂದು ತೊಟ್ಟಿಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ (ಅಂದರೆ, ಒಟ್ಟು ತೊಟ್ಟಿಗಳು), ಆದರೆ ಎನ್ಎಫ್ನಿಂದ ಉತ್ಪತ್ತಿಯಾಗುವ ದ್ರಾವಣವು ಒಂದು ಗಾತ್ರದ ವಸ್ತು ಮತ್ತು ಒಂದು ಗಾತ್ರದ ವಸ್ತುವನ್ನು ಹೊಂದಿರುವ ತೊಟ್ಟಿಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು ವಸ್ತುವಿನ ಗರಿಷ್ಠ ಗಾತ್ರವು ಇದ್ದರೆ, ಅಸಿಂಪ್ಟೋಟಿಕ್ ಅಂದಾಜು ಅನುಪಾತವು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆಃ ಎಲ್ಲರಿಗೂ; ಎಲ್ಲರಿಗೂ. ಇತರ ಗುಣಲಕ್ಷಣಗಳು ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಒಂದು ಪಟ್ಟಿಯನ್ನು ಮತ್ತು ಅದರ ವಿಲೋಮವನ್ನು ಅದೇ ಸಂಖ್ಯೆಯ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಜೋಡಿಸುತ್ತದೆ. ನೆಕ್ಸ್ಟ್-ಕೆ-ಫಿಟ್ (ಎನ್. ಕೆ. ಎಫ್) ನೆಕ್ಸ್ಟ್-ಕೆ-ಫಿಟ್ ನೆಕ್ಸ್ಟ್-ಫಿಟ್ನ ಒಂದು ರೂಪಾಂತರವಾಗಿದೆ, ಆದರೆ ಕೇವಲ ಒಂದು ಬಿನ್ ಅನ್ನು ತೆರೆದಿಡುವ ಬದಲು, ಅಲ್ಗಾರಿದಮ್ ಕೊನೆಯ ಬಿನ್ಗಳನ್ನು ತೆರೆದಿಡುತ್ತದೆ ಮತ್ತು ವಸ್ತುವು ಸರಿಹೊಂದುವ ಮೊದಲ ಬಿನ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಏಕೆಂದರೆ, ಎನ್. ಎಫ್. ನ ಫಲಿತಾಂಶಗಳಿಗೆ ಹೋಲಿಸಿದರೆ ಎನ್. ಕೆ. ಎಫ್. ಉತ್ತಮವಾದ ಫಲಿತಾಂಶಗಳನ್ನು ನೀಡುತ್ತದೆ, ಆದಾಗ್ಯೂ, ಸ್ಥಿರವಾದ ಮೌಲ್ಯಗಳನ್ನು ದೊಡ್ಡದಾಗಿ ಹೆಚ್ಚಿಸುವುದರಿಂದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅದರ ಕೆಟ್ಟ-ಪರಿಸ್ಥಿತಿಯ ನಡವಳಿಕೆಯಲ್ಲಿ ಸುಧಾರಿಸುವುದಿಲ್ಲ. ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಆಲ್ಮೋಸ್ಟ್ಎನಿಫಿಟ್-ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದರೆ ಮತ್ತು ನಂತರ. ನೆಕ್ಸ್ಟ್-ಫಿಟ್-ಡಿಕ್ರೀಸಿಂಗ್ (ಎನ್ಎಫ್ಡಿ) ನೆಕ್ಸ್ಟ್-ಫಿಟ್ನ ಆಫ್ಲೈನ್ ರೂಪಾಂತರವಾಗಿದೆಃ ಇದು ಎಲ್ಲಾ ಇನ್ಪುಟ್ ವಸ್ತುಗಳನ್ನು ಸ್ವೀಕರಿಸುತ್ತದೆ, ಅವರೋಹಣ ಗಾತ್ರದ ಮೂಲಕ ಆದೇಶಿಸುತ್ತದೆ ಮತ್ತು ನೆಕ್ಸ್ಟ್-ಫಿಟ್ಗೆ ಕರೆ ಮಾಡುತ್ತದೆ. ಇದರ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಅಂದಾಜು ಅನುಪಾತವು ತುಂಬಾ ಉತ್ತಮವಾಗಿದೆಃ 2ರ ಬದಲಿಗೆ 1.7ಕ್ಕಿಂತ ಕಡಿಮೆ. ಉಲ್ಲೇಖಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್