ಕ್ರುಸ್ಕಲ್ ನ ಅಲ್ಗಾರಿದಮ್ ಮೇಜ್ ಜನರೇಟರ್

ಕ್ರುಸ್ಕಲ್‌ನ ಅಲ್ಗಾರಿದಮ್ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು ಅದನ್ನು ಜಟಿಲ ಉತ್ಪಾದನೆಗೆ ಅಳವಡಿಸಿಕೊಳ್ಳಬಹುದು. ಇದು ಪರಿಪೂರ್ಣ ಜಟಿಲಗಳನ್ನು ರಚಿಸಲು ವಿಶೇಷವಾಗಿ ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ. ಕ್ರುಸ್ಕಲ್‌ನ ಅಲ್ಗಾರಿದಮ್‌ಗೆ ಪರ್ಯಾಯವೆಂದರೆ ಪ್ರಿಮ್‌ನ ಅಲ್ಗಾರಿದಮ್, ಇದು ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅಲ್ಗಾರಿದಮ್ ಕೂಡ ಆಗಿದೆ, ಆದರೆ ಅವು ಒಂದೇ ರೀತಿಯ ಮೇಜ್‌ಗಳನ್ನು ಉತ್ಪಾದಿಸುವುದರಿಂದ ಮತ್ತು ಕ್ರುಸ್ಕಲ್‌ನ ರನ್‌ಗಳನ್ನು ವೇಗವಾಗಿ ಮಾಡುವುದರಿಂದ, ನಾನು ಪ್ರೈಮ್‌ಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಚಿಂತಿಸಿಲ್ಲ.

ಪರಿಪೂರ್ಣ ಜಟಿಲ ಎಂದರೆ ಜಟಿಲದಲ್ಲಿ ಯಾವುದೇ ಬಿಂದುವಿನಿಂದ ಇನ್ನೊಂದು ಬಿಂದುವಿಗೆ ನಿಖರವಾಗಿ ಒಂದೇ ಮಾರ್ಗವಿರುತ್ತದೆ. ಅಂದರೆ ನೀವು ವೃತ್ತಗಳಲ್ಲಿ ಸುತ್ತಲು ಸಾಧ್ಯವಿಲ್ಲ, ಆದರೆ ನೀವು ಆಗಾಗ್ಗೆ ಡೆಡ್ ಎಂಡ್‌ಗಳನ್ನು ಎದುರಿಸುತ್ತೀರಿ, ಅದು ನಿಮ್ಮನ್ನು ತಿರುಗಿ ಹಿಂತಿರುಗುವಂತೆ ಮಾಡುತ್ತದೆ.

ಇಲ್ಲಿ ರಚಿಸಲಾದ ಜಟಿಲ ನಕ್ಷೆಗಳು ಯಾವುದೇ ಆರಂಭ ಮತ್ತು ಮುಕ್ತಾಯ ಸ್ಥಾನಗಳಿಲ್ಲದೆ ಡೀಫಾಲ್ಟ್ ಆವೃತ್ತಿಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತವೆ, ಆದ್ದರಿಂದ ನೀವು ಅವುಗಳನ್ನು ನೀವೇ ನಿರ್ಧರಿಸಬಹುದು: ಜಟಿಲದಲ್ಲಿನ ಯಾವುದೇ ಬಿಂದುವಿನಿಂದ ಬೇರೆ ಯಾವುದೇ ಬಿಂದುವಿಗೆ ಪರಿಹಾರವಿರುತ್ತದೆ. ನೀವು ಸ್ಫೂರ್ತಿ ಬಯಸಿದರೆ, ನೀವು ಸೂಚಿಸಲಾದ ಪ್ರಾರಂಭ ಮತ್ತು ಮುಕ್ತಾಯ ಸ್ಥಾನವನ್ನು ಸಕ್ರಿಯಗೊಳಿಸಬಹುದು - ಮತ್ತು ಎರಡರ ನಡುವಿನ ಪರಿಹಾರವನ್ನು ಸಹ ನೋಡಬಹುದು.

ಕ್ರುಸ್ಕಲ್ ಅವರ ಅಲ್ಗಾರಿದಮ್ ಬಗ್ಗೆ

ಕ್ರುಸ್ಕಲ್ ಅವರ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅಮೇರಿಕನ್ ಗಣಿತಜ್ಞ, ಸಂಖ್ಯಾಶಾಸ್ತ್ರಜ್ಞ ಮತ್ತು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನಿ ಜೋಸೆಫ್ ಬರ್ನಾರ್ಡ್ ಕ್ರುಸ್ಕಲ್ ಜೂನಿಯರ್ ರಚಿಸಿದ್ದಾರೆ. ಅವರು ಮೊದಲು 1956 ರಲ್ಲಿ ತಮ್ಮ "ಆನ್ ದಿ ಶಾರ್ಟೆಸ್ಟ್ ಸ್ಪ್ಯಾನಿಂಗ್ ಸಬ್‌ಟ್ರೀ ಆಫ್ ಎ ಗ್ರಾಫ್ ಅಂಡ್ ದಿ ಟ್ರಾವೆಲಿಂಗ್ ಸೇಲ್ಸ್‌ಮ್ಯಾನ್ ಪ್ರಾಬ್ಲಮ್" ಎಂಬ ಪ್ರಬಂಧದಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ವಿವರಿಸಿದರು.

ಈ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಗ್ರಾಫ್‌ನ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ (MST) ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ವಿನ್ಯಾಸಗೊಳಿಸಲಾಗಿದೆ, ಎಲ್ಲಾ ಶೃಂಗಗಳು ಚಕ್ರಗಳನ್ನು ತಪ್ಪಿಸುವಾಗ ಕನಿಷ್ಠ ಸಂಭಾವ್ಯ ಒಟ್ಟು ಅಂಚಿನ ತೂಕದೊಂದಿಗೆ ಸಂಪರ್ಕಗೊಂಡಿವೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ.

ಮೇಜ್ ಜನರೇಷನ್‌ಗೆ ಕ್ರುಸ್ಕಲ್‌ನ ಅಲ್ಗಾರಿದಮ್ ಹೇಗೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ

ಹಂತ 1: ಪ್ರಾರಂಭಿಸಿ

• ಜಟಿಲದಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಕೋಶವನ್ನು ಪ್ರತ್ಯೇಕ ಗುಂಪಾಗಿ (ಒಂದು ವಿಶಿಷ್ಟ ಘಟಕ) ಪರಿಗಣಿಸಿ.
• ಪಕ್ಕದ ಕೋಶಗಳ ನಡುವಿನ ಎಲ್ಲಾ ಗೋಡೆಗಳನ್ನು ಸಂಭಾವ್ಯ ಅಂಚುಗಳಾಗಿ ಪಟ್ಟಿ ಮಾಡಿ.

ಹಂತ 2: ಗೋಡೆಗಳನ್ನು ವಿಂಗಡಿಸಿ

• ಗೋಡೆಗಳನ್ನು ಷಫಲ್ ಮಾಡಿ ಅಥವಾ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಕ್ರಮಗೊಳಿಸಿ. ನಿಜವಾದ ಕ್ರುಸ್ಕಲ್‌ನ ಅಲ್ಗಾರಿದಮ್‌ನಂತೆ ಇದನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುತ್ತಿದ್ದರೆ, ಗೋಡೆಗಳನ್ನು ಯಾದೃಚ್ಛಿಕ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಿ (ಏಕೆಂದರೆ ಮೇಜ್ ಉತ್ಪಾದನೆಗೆ ತೂಕದ ಅಗತ್ಯವಿಲ್ಲ).

ಹಂತ 3: ಪ್ರಕ್ರಿಯೆ ಗೋಡೆಗಳು

• ಜೋಡಿಸಲಾದ ಗೋಡೆಗಳ ಮೂಲಕ ಪುನರಾವರ್ತಿಸಿ.
• ಗೋಡೆಯಿಂದ ಭಾಗಿಸಲಾದ ಎರಡು ಕೋಶಗಳು ವಿಭಿನ್ನ ಸೆಟ್‌ಗಳಿಗೆ ಸೇರಿದ್ದರೆ (ಅಂದರೆ, ಅವು ಇನ್ನೂ ಜಟಿಲದಲ್ಲಿ ಸಂಪರ್ಕಗೊಂಡಿಲ್ಲ), ಗೋಡೆಯನ್ನು ತೆಗೆದುಹಾಕಿ ಮತ್ತು ಸೆಟ್‌ಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಿ.
• ಅವರು ಈಗಾಗಲೇ ಒಂದೇ ಸೆಟ್‌ನಲ್ಲಿದ್ದರೆ, ಗೋಡೆಯನ್ನು ಬಿಟ್ಟುಬಿಡಿ (ಚಕ್ರಗಳನ್ನು ತಪ್ಪಿಸಲು).

ಹಂತ 4: ಪೂರ್ಣಗೊಳ್ಳುವವರೆಗೆ ಮುಂದುವರಿಸಿ

• ಎಲ್ಲಾ ಕೋಶಗಳು ಸಂಪರ್ಕಗೊಳ್ಳುವವರೆಗೆ ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸಿ, ಒಂದೇ ಸ್ಪ್ಯಾನಿಂಗ್ ಮರವನ್ನು ರೂಪಿಸಿ.
• ಕೊನೆಯಲ್ಲಿ, ಪ್ರತಿಯೊಂದು ಕೋಶವು ಕುಣಿಕೆಗಳು ಅಥವಾ ಪ್ರತ್ಯೇಕ ವಿಭಾಗಗಳಿಲ್ಲದೆ ಇತರರೊಂದಿಗೆ ಸಂಪರ್ಕ ಹೊಂದಿದೆ.

ಕ್ರುಸ್ಕಲ್‌ನ ಅಲ್ಗಾರಿದಮ್ ಸೆಟ್‌ಗಳನ್ನು ವಿಲೀನಗೊಳಿಸುವುದರ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿರುವುದರಿಂದ, ಯೂನಿಯನ್-ಫೈಂಡ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಅದನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸಬಹುದು, ಇದು ಮೇಜ್ ಉತ್ಪಾದನೆಯ ಸಮಯದಲ್ಲಿ ಸಂಪರ್ಕಿತ ಕೋಶಗಳನ್ನು ಟ್ರ್ಯಾಕ್ ಮಾಡಲು ಪರಿಣಾಮಕಾರಿ ಮಾರ್ಗವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಯೂನಿಯನ್-ಫೈಂಡ್ ಅಲ್ಗಾರಿದಮ್‌ನ ನನ್ನ PHP ಅನುಷ್ಠಾನವನ್ನು ನೀವು ಇಲ್ಲಿ ನೋಡಬಹುದು: ಲಿಂಕ್

ಹೆಚ್ಚಿನ ಓದಿಗೆ

ನೀವು ಈ ಪೋಸ್ಟ್ ಅನ್ನು ಆನಂದಿಸಿದ್ದರೆ, ನೀವು ಈ ಸಲಹೆಗಳನ್ನು ಸಹ ಇಷ್ಟಪಡಬಹುದು:

• ಎಲ್ಲೆರ್'ಸ್ ಅಲ್ಗಾರಿದಮ್ ಮೇಜ್ ಜನರೇಟರ್
• ಮೇಜ್ ಜನರೇಟರ್ ಅನ್ನು ಬೇಟೆಯಾಡಿ ಮತ್ತು ಕೊಲ್ಲಿರಿ
• ವಿಲ್ಸನ್ ಅಲ್ಗಾರಿದಮ್ ಮೇಜ್ ಜನರೇಟರ್