Next-fit-decreasing bin packing
ನೆಕ್ಸ್ಟ್-ಫಿಟ್-ಡಿಕ್ರೀಸಿಂಗ್ (ಎನ್ಎಫ್ಡಿ) ಎಂಬುದು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ಗೆ ಒಂದು ಕ್ರಮಾವಳಿ. ಇದರ ಇನ್ಪುಟ್ ವಿವಿಧ ಗಾತ್ರದ ವಸ್ತುಗಳ ಪಟ್ಟಿಯಾಗಿದೆ. ಇದರ ಉತ್ಪಾದನೆಯು ಒಂದು ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ-ಪ್ರತಿ ಡಬ್ಬಿಯಲ್ಲಿನ ವಸ್ತುಗಳ ಗಾತ್ರಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದುವಂತಹ ಸ್ಥಿರ ಸಾಮರ್ಥ್ಯದ ಡಬ್ಬಿಗಳಾಗಿ ವಸ್ತುಗಳನ್ನು ವಿಭಜಿಸುವುದು. ಆದರ್ಶಪ್ರಾಯವಾಗಿ, ನಾವು ಸಾಧ್ಯವಾದಷ್ಟು ಕಡಿಮೆ ತೊಟ್ಟಿಗಳನ್ನು ಬಳಸಲು ಬಯಸುತ್ತೇವೆ, ಆದರೆ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಎನ್ಪಿ-ಕಠಿಣ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಎನ್. ಎಫ್. ಡಿ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅನ್ನು ಬಳಸುತ್ತದೆಃ ವಸ್ತುಗಳನ್ನು ದೊಡ್ಡದರಿಂದ ಚಿಕ್ಕದಕ್ಕೆ ಆರ್ಡರ್ ಮಾಡಿ. ಖಾಲಿ ಬಿನ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ ಮತ್ತು ಅದನ್ನು "ತೆರೆದ ಬಿನ್" ಎಂದು ಕರೆಯಿರಿ. ಪ್ರತಿ ವಸ್ತುವಿಗೆ, ಅದು ತೆರೆದ ಡಬ್ಬಿಯಲ್ಲಿ ಹೊಂದಿಕೊಳ್ಳುತ್ತದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿಃ ಅದು ಸರಿಹೊಂದುತ್ತಿದ್ದರೆ, ಹೊಸ ವಸ್ತುವನ್ನು ಅದರಲ್ಲಿ ಇರಿಸಿ. ಇಲ್ಲದಿದ್ದರೆ, ಪ್ರಸ್ತುತ ಬಿನ್ ಅನ್ನು ಮುಚ್ಚಿ, ಹೊಸ ಬಿನ್ ಅನ್ನು ತೆರೆಯಿರಿ ಮತ್ತು ಪ್ರಸ್ತುತ ವಸ್ತುವನ್ನು ಅದರೊಳಗೆ ಇರಿಸಿ. ಸಂಕ್ಷಿಪ್ತವಾಗಿ ಹೇಳುವುದಾದರೆಃ ಎನ್. ಎಫ್. ಡಿ. ಕೆಳಗಿಳಿಯುವ ಗಾತ್ರದ ಮೂಲಕ ವಸ್ತುಗಳನ್ನು ಆದೇಶಿಸುತ್ತದೆ, ಮತ್ತು ನಂತರ ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ಗೆ ಕರೆ ಮಾಡುತ್ತದೆ. ಕಾರ್ಯಕ್ಷಮತೆ ಮೇಲಿನ ಬೌಂಡ್ ಬೇಕರ್ ಮತ್ತು ಕಾಫ್ಮನ್, ಪ್ರತಿ ಪೂರ್ಣಾಂಕ r ಗೆ, ಎಲ್ಲಾ ವಸ್ತುಗಳ ಗಾತ್ರವು ಗರಿಷ್ಠ 1/r ಆಗಿರುವಾಗ, RFD ಯ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಅಂದಾಜು ಅನುಪಾತವು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸಿದರು, ಅಲ್ಲಿ ಮೊದಲ ಅಂಶಗಳು ಸರಿಸುಮಾರು 1.69103,1.42312,1.30238 ಆಗಿರುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, r = 1 ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದು ಅದನ್ನು ಸೂಚಿಸುತ್ತದೆ. ನಂತರ, ಎನ್. ಎಫ್. ಡಿ. ಯನ್ನು ಸಹ ಸಂಭಾವ್ಯವಾಗಿ ವಿಶ್ಲೇಷಿಸಲಾಗಿದೆ. ರೂಪಾಂತರಗಳು ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಒಂದು ಪಟ್ಟಿಯನ್ನು ಮತ್ತು ಅದರ ವಿಲೋಮವನ್ನು ಅದೇ ಸಂಖ್ಯೆಯ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಪ್ಯಾಕ್ ಮಾಡುತ್ತದೆ. ಆದ್ದರಿಂದ, ನೆಕ್ಸ್ಟ್-ಫಿಟ್-ಇಂಕ್ರೀಸಿಂಗ್ ನೆಕ್ಸ್ಟ್-ಫಿಟ್-ಡಿಕ್ರೀಸಿಂಗ್ನಂತೆಯೇ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಹೊಂದಿದೆ. ಆದಾಗ್ಯೂ, ಸಾಮಾನ್ಯ ವೆಚ್ಚದ ರಚನೆಗಳು ಇದ್ದಾಗ ನೆಕ್ಸ್ಟ್-ಫಿಟ್-ಇಂಕ್ರೀಸಿಂಗ್ ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್