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

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

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

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

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

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

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

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

ಹಂತ 1: ಆರಂಭಿಸಿ

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

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

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

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

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

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

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

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