Harmonic bin packing
ಹಾರ್ಮೋನಿಕ್ ಬಿನ್-ಪ್ಯಾಕಿಂಗ್ ಎಂಬುದು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ಗಾಗಿ ಆನ್ಲೈನ್ ಕ್ರಮಾವಳಿಗಳ ಒಂದು ಕುಟುಂಬವಾಗಿದೆ. ಅಂತಹ ಅಲ್ಗಾರಿದಮ್ಗೆ ಇನ್ಪುಟ್ ವಿವಿಧ ಗಾತ್ರಗಳ ವಸ್ತುಗಳ ಪಟ್ಟಿಯಾಗಿದೆ. ಔಟ್ಪುಟ್ ಒಂದು ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ-ವಸ್ತುಗಳನ್ನು ನಿಗದಿತ ಸಾಮರ್ಥ್ಯದ ಡಬ್ಬಿಗಳಾಗಿ ವಿಭಜಿಸುವುದು, ಅಂದರೆ ಪ್ರತಿ ಡಬ್ಬಿಯಲ್ಲಿನ ವಸ್ತುಗಳ ಗಾತ್ರಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆದರ್ಶಪ್ರಾಯವಾಗಿ, ನಾವು ಸಾಧ್ಯವಾದಷ್ಟು ಕಡಿಮೆ ತೊಟ್ಟಿಗಳನ್ನು ಬಳಸಲು ಬಯಸುತ್ತೇವೆ, ಆದರೆ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಎನ್ಪಿ-ಕಠಿಣ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಹಾರ್ಮೋನಿಕ್ ಬಿನ್-ಪ್ಯಾಕಿಂಗ್ ಕ್ರಮಾವಳಿಗಳು ಹಾರ್ಮೋನಿಕ್ ಪ್ರಗತಿಯನ್ನು ಅನುಸರಿಸಿ ವಸ್ತುಗಳನ್ನು ಅವುಗಳ ಗಾತ್ರಗಳ ಆಧಾರದ ಮೇಲೆ ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸುವುದನ್ನು ಅವಲಂಬಿಸಿವೆ. ಈ ಕಲ್ಪನೆಯ ಹಲವಾರು ರೂಪಾಂತರಗಳಿವೆ. ಹಾರ್ಮೋನಿಕ್-ಕೆ ಅಲ್ಗಾರಿದಮ್ ಗಾತ್ರಗಳ ಮಧ್ಯಂತರವನ್ನು ಸಾಮರಸ್ಯದಿಂದ ಮತ್ತು ಅಂತಹ ತುಂಡುಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ. ಒಂದು ವಸ್ತುವನ್ನು-ಐಟಂ, ಇಫ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಖಾಲಿ ತೊಟ್ಟಿಗಳ ಗುಂಪನ್ನು ಪ್ರತಿ ಐಟಂ ಪ್ರಕಾರಕ್ಕೆ ಒಂದು ಬಿನ್ ಪ್ರಕಾರಕ್ಕಾಗಿ ಅನಂತ ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸುತ್ತದೆ. ರೀತಿಯ ವಸ್ತುಗಳನ್ನು ಪ್ಯಾಕ್ ಮಾಡಲು ಡಬ್ಬಿಗಳಿಗೆ ಮಾತ್ರ ಒಂದು ರೀತಿಯ ಡಬ್ಬಿಯನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಫಾರ್ ಪ್ರಕಾರದ ಪ್ರತಿಯೊಂದು ಬಿನ್ ನಿಖರವಾಗಿ-ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರಬಹುದು. ಅಲ್ಗಾರಿದಮ್ ಈಗ ಈ ಕೆಳಗಿನಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಃ ಮುಂದಿನ ಐಟಂ-ಐಟಂ ಆಗಿದ್ದರೆ, ಐಟಂ ಅನ್ನು ಮೊದಲ (ಕೇವಲ ತೆರೆದ) ಬಿನ್ನಲ್ಲಿ ಇರಿಸಲಾಗುತ್ತದೆ, ಅದು ಕಡಿಮೆ ತುಣುಕುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಅಥವಾ ಅಂತಹ ಬಿನ್ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲದಿದ್ದರೆ ಹೊಸದನ್ನು ತೆರೆಯುತ್ತದೆ. ಮುಂದಿನ ಐಟಂ-ಐಟಂ ಆಗಿದ್ದರೆ, ಅಲ್ಗಾರಿದಮ್ ಅದನ್ನು ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ರೀತಿಯ ಡಬ್ಬಿಗಳಲ್ಲಿ ಇರಿಸುತ್ತದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಮೊದಲು ಲೀ ಮತ್ತು ಲೀ ಅವರು ವಿವರಿಸಿದ್ದಾರೆ. ಇದು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆ, ಅಲ್ಲಿ n ಎಂಬುದು ಇನ್ಪುಟ್ ಐಟಂಗಳ ಸಂಖ್ಯೆ. ಪ್ರತಿ ಹಂತದಲ್ಲೂ, ವಸ್ತುಗಳನ್ನು ಇರಿಸಲು ಸಮರ್ಥವಾಗಿ ಬಳಸಬಹುದಾದ ಹೆಚ್ಚಿನ ತೆರೆದ ತೊಟ್ಟಿಗಳಿವೆ, ಅಂದರೆ, ಇದು ಕೆ-ಬೌಂಡೆಡ್ ಸ್ಪೇಸ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಲೀ ಮತ್ತು ಲೀ ಸಹ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಅಧ್ಯಯನ ಮಾಡಿದರು. ಅವರು ಒಂದು ಅನುಕ್ರಮವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿದರು, ಮತ್ತು ಅದು ಅದನ್ನು ಹೊಂದಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸಿದರು. ಏಕೆಂದರೆ ಅದು ಅದನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುತ್ತದೆ. ಹೆಚ್ಚುವರಿಯಾಗಿ, ಅವರು ಸಂಸ್ಕರಿಸಿದ-ಹಾರ್ಮೋನಿಕ್ (ಆರ್ಎಚ್) ಗೆ ಕೆಟ್ಟ ಉದಾಹರಣೆಗಳ ಕುಟುಂಬವನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು, ಸಂಸ್ಕರಿಸಿದ-ಹಾರ್ಮೋನಿಕ್ ಹಾರ್ಮೋನಿಕ್-ಕೆ ಅಲ್ಗಾರಿದಮ್ನ ಕಲ್ಪನೆಗಳನ್ನು ಸಂಸ್ಕರಿಸಿದ-ಮೊದಲ-ಫಿಟ್ನ ಕಲ್ಪನೆಗಳೊಂದಿಗೆ ಸಂಯೋಜಿಸುತ್ತದೆ. ಇದು ರಿಫೈನ್ಡ್-ಫಸ್ಟ್-ಫಿಟ್ನಲ್ಲಿರುವಂತೆ ದೊಡ್ಡದಾದ ವಸ್ತುಗಳನ್ನು ಇರಿಸುತ್ತದೆ, ಆದರೆ ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಹಾರ್ಮೋನಿಕ್-ಕೆ ಬಳಸಿ ಇರಿಸಲಾಗುತ್ತದೆ. ಈ ಕಾರ್ಯತಂತ್ರದ ಅಂತಃಪ್ರಜ್ಞೆಯು ಕೇವಲ ಅದಕ್ಕಿಂತ ದೊಡ್ಡದಾದ ತುಂಡುಗಳನ್ನು ಹೊಂದಿರುವ ಡಬ್ಬಿಗಳಿಗೆ ದೊಡ್ಡ ತ್ಯಾಜ್ಯವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು. ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಮಧ್ಯಂತರಗಳಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ವಸ್ತುಗಳನ್ನು ವರ್ಗೀಕರಿಸುತ್ತದೆಃ,,,, ಫಾರ್, ಮತ್ತು. ಅಲ್ಗಾರಿದಮ್-ಐಟಂಗಳನ್ನು ಹಾರ್ಮೋನಿಕ್-ಕೆ ನಲ್ಲಿರುವಂತೆ ಇರಿಸುತ್ತದೆ, ಆದರೆ ಇದು ಮತ್ತು ವಸ್ತುಗಳಿಗೆ ವಿಭಿನ್ನ ತಂತ್ರವನ್ನು ಅನುಸರಿಸುತ್ತದೆ. ವಸ್ತುಗಳು ಮತ್ತು ವಸ್ತುಗಳನ್ನು ಡಬ್ಬಿಗಳಲ್ಲಿ ಕಟ್ಟಲು ನಾಲ್ಕು ಸಾಧ್ಯತೆಗಳಿವೆ. ಒಂದು-ಬಿನ್ ಕೇವಲ ಒಂದು ವಸ್ತುವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು-ಬಿನ್ ಕೇವಲ ಒಂದು ವಸ್ತುವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು ಬಿನ್ ಒಂದು ಐಟಂ ಮತ್ತು ಒಂದು ಐಟಂ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು-ಬಿನ್ ಎರಡು-ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು-ಬಿನ್ ಎರಡನೇ ವಸ್ತುವನ್ನು ಹೊಂದಲು ಗೊತ್ತುಪಡಿಸಿದ ಬಿನ್ ಅನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಪರಿಹಾರದಲ್ಲಿನ ಅನುಗುಣವಾದ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಗಳನ್ನು ಎಣಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಎನ್ಎ, ಎನ್ಬಿ, ಎನ್ಎಬಿ, ಎನ್ಬಿಬಿ ಮತ್ತು ಎನ್ಬಿ 'ಸಂಖ್ಯೆಗಳನ್ನು ಬಳಸುತ್ತದೆ. ಇದಲ್ಲದೆ, ಒಂದು ಪಟ್ಟಿಗೆ N _ c = N _ b + N _ ab ಅಲ್ಗಾರಿದಮ್ ರಿಫೈನ್ಡ್-ಹಾರ್ಮೋನಿಕ್-k L = (i _ 1, \dot i _ n): 1. ಎನ್. ಎ. = ಎನ್. ಬಿ. = ಎನ್. ಬಿ. ಬಿ. = ಎನ್. ಬಿ. '= ಎನ್. ಸಿ. = 02. i _ j ಒಂದು I _ k-ಪೀಸ್ ಆಗಿದ್ದರೆ ಅದನ್ನು ಪ್ಯಾಕ್ ಮಾಡಲು ಅಲ್ಗಾರಿದಮ್ ಹಾರ್ಮೋನಿಕ್-k ಅನ್ನು ಬಳಸಿ. ಇಲ್ಲದಿದ್ದರೆ i _ j ಒಂದು I _ a-ಐಟಂ ಆಗಿದ್ದರೆ, N _ b! = 1 ಆಗಿದ್ದರೆ, ಯಾವುದೇ J _ b-ಬಿನ್ ಆಗಿ i _ j ಅನ್ನು ಪ್ಯಾಕ್ ಮಾಡಿ; N _ b--; N _ ab + +; ಇಲ್ಲದಿದ್ದರೆ i _ j ಅನ್ನು ಹೊಸ (ಖಾಲಿ) ಬಿನ್ನಲ್ಲಿ ಇರಿಸಿ; N _ a + +; 4. ಇಲ್ಲದಿದ್ದರೆ i _ j ಒಂದು I _ b-ಐಟಂ ಆಗಿದ್ದರೆ ನಂತರ N _ b '= 1 ಆಗಿದ್ದರೆ i _ j ಅನ್ನು I _ b'-ಬಿನ್ನಲ್ಲಿ ಇರಿಸಿ; N _ b '= 0; N _ bb + +; 5. ಇಲ್ಲದಿದ್ದರೆ N _ bb <= 3N _ c ಆಗಿದ್ದರೆ ನಂತರ i _ b ಅನ್ನು ಇರಿಸಿ. ಅವರು ಅದನ್ನು ಸಮರ್ಥಿಸಿಕೊಂಡಿದ್ದಾರೆ ಎಂಬುದನ್ನು ಸಾಬೀತುಪಡಿಸಿದರು. ಇತರ ರೂಪಾಂತರಗಳಾದ ಮಾರ್ಪಡಿಸಿದ ಹಾರ್ಮೋನಿಕ್ (ಎಮ್ಎಚ್) ಲಕ್ಷಣರಹಿತ ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ. ಮಾರ್ಪಡಿಸಿದ ಹಾರ್ಮೋನಿಕ್ 2 (MH2) ಲಕ್ಷಣರಹಿತ ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ. ಹಾರ್ಮೋನಿಕ್ + 1 (ಎಚ್ + 1) ಲಕ್ಷಣರಹಿತ ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ. ಹಾರ್ಮೋನಿಕ್ + + (H + +) ಲಕ್ಷಣರಹಿತ ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ. ಉಲ್ಲೇಖಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್