Mixed Chinese postman problem
ಮಿಶ್ರ ಚೀನೀ ಪೋಸ್ಟ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯು (ಎಂ. ಸಿ. ಪಿ. ಪಿ. ಅಥವಾ ಎಂ. ಸಿ. ಪಿ.) V ಶೃಂಗಗಳ ಗುಂಪಿನೊಂದಿಗೆ ರೇಖಾಚಿತ್ರದ ಚಿಕ್ಕದಾದ ಪ್ರಯಾಣದ ಹುಡುಕಾಟವಾಗಿದೆ, ಧನಾತ್ಮಕ ತರ್ಕಬದ್ಧ ತೂಕಗಳೊಂದಿಗೆ ನಿರ್ದೇಶಿಸದ ಅಂಚುಗಳ ಒಂದು ಸೆಟ್, ಮತ್ತು ಧನಾತ್ಮಕ ತರ್ಕಬದ್ಧ ತೂಕಗಳೊಂದಿಗೆ ನಿರ್ದೇಶಿತ ಚಾಪಗಳ ಒಂದು ಸೆಟ್, ಇದು ಕನಿಷ್ಠ ವೆಚ್ಚದಲ್ಲಿ ಕನಿಷ್ಠ ಒಮ್ಮೆಯಾದರೂ ಪ್ರತಿ ಅಂಚು ಅಥವಾ ಚಾಪವನ್ನು ಆವರಿಸುತ್ತದೆ. ಈ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ-ಕಂಪ್ಲೀಟ್ ಎಂದು ಪಾಪಾಡಿಮಿಟ್ರಿಯು ಸಾಬೀತುಪಡಿಸಿದ್ದಾರೆ. ಮಿಶ್ರ ಚೀನೀ ಪೋಸ್ಟ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯು ಸಾಮಾನ್ಯವಾಗಿ ಹಿಮ ಉಳುಮೆ ಮುಂತಾದ ಆರ್ಕ್ ರೂಟಿಂಗ್ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಉದ್ಭವಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಕೆಲವು ರಸ್ತೆಗಳು ಎರಡೂ ದಿಕ್ಕುಗಳಲ್ಲಿ ಹಾದುಹೋಗಲು ತುಂಬಾ ಕಿರಿದಾಗಿರುತ್ತವೆ, ಆದರೆ ಇತರ ರಸ್ತೆಗಳು ಎರಡು ದಿಕ್ಕುಗಳಾಗಿರುತ್ತವೆ ಮತ್ತು ಎರಡೂ ದಿಕ್ಕುಗಳಲ್ಲಿ ಉಳುಮೆ ಮಾಡಬಹುದು. ಗ್ರಾಫ್ ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ಮಿಶ್ರ ಗ್ರಾಫ್ ಯಾವುದೇ ಗಾತ್ರದ ಪೋಸ್ಟ್ಮ್ಯಾನ್ ಪ್ರವಾಸವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವುದು ಸುಲಭ. ಜರಾಗೋಜಾ ಮಾರ್ಟಿನೆಜ್ ಸಾಬೀತುಪಡಿಸಿದಂತೆ, ನಾವು ಪೋಸ್ಟ್ಮ್ಯಾನ್ ಪ್ರವಾಸವನ್ನು ಪ್ರತಿ ಚಾಪವನ್ನು ನಿಖರವಾಗಿ ಒಮ್ಮೆ ಹಾದುಹೋಗಲು ನಿರ್ಬಂಧಿಸಿದರೆ ಅಥವಾ ಪ್ರತಿ ಅಂಚನ್ನು ನಿಖರವಾಗಿ ಒಮ್ಮೆ ಹಾದುಹೋಗಲು ನಿರ್ಬಂಧಿಸಿದರೆ ಸಮಸ್ಯೆ ಎನ್. ಪಿ. ಕಠಿಣವಾಗಿದೆ. ಗಣಿತದ ವ್ಯಾಖ್ಯಾನ ಗಣಿತದ ವ್ಯಾಖ್ಯಾನವೆಂದರೆಃ ಇನ್ಪುಟ್ಃ ಪ್ರತಿ ಅಂಚಿನ ವೆಚ್ಚ ಮತ್ತು ಗರಿಷ್ಠ ವೆಚ್ಚದೊಂದಿಗೆ ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದ, ಮಿಶ್ರ ಗ್ರಾಫ್. ಪ್ರಶ್ನೆಃ ಪ್ರತಿಯೊಂದು ತುದಿಯನ್ನು ಕನಿಷ್ಠ ಒಮ್ಮೆಯಾದರೂ ಹಾದುಹೋಗುವ ಮತ್ತು ಗರಿಷ್ಠ ವೆಚ್ಚವನ್ನು ಹೊಂದಿರುವ (ನಿರ್ದೇಶಿತ) ಪ್ರವಾಸವಿದೆಯೇ? ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಮಿಶ್ರ ಚೀನೀ ಪೋಸ್ಟ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವಲ್ಲಿ ಮುಖ್ಯ ತೊಂದರೆ ಎಂದರೆ ನಮ್ಮ ಪ್ರವಾಸಕ್ಕೆ ಬಿಗಿಯಾದ ಬಜೆಟ್ ನೀಡಿದಾಗ ಮತ್ತು ಪ್ರತಿ ಅಂಚನ್ನು ಒಮ್ಮೆ ಮಾತ್ರ ಹಾದುಹೋಗಲು ಶಕ್ತರಾದಾಗ (ನಿರ್ದೇಶಿಸದ) ಅಂಚುಗಳಿಗೆ ದೃಷ್ಟಿಕೋನಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು. ನಂತರ ನಾವು ಅಂಚುಗಳನ್ನು ಓರಿಯಂಟ್ ಮಾಡಬೇಕು ಮತ್ತು ನಿರ್ದೇಶಿತ ಯೂಲೆರಿಯನ್ ಗ್ರಾಫ್ ಅನ್ನು ಪಡೆಯಲು ಕೆಲವು ಹೆಚ್ಚುವರಿ ಆರ್ಕ್ಗಳನ್ನು ಸೇರಿಸಬೇಕು, ಅಂದರೆ, ಪ್ರತಿ ಶೃಂಗವನ್ನು ಸಮತೋಲನಗೊಳಿಸಬೇಕು. ಒಂದು ಶೃಂಗಕ್ಕೆ ಅನೇಕ ಅಂಚುಗಳಿದ್ದರೆ, ಪ್ರತಿ ಅಂಚಿನ ಸರಿಯಾದ ದಿಕ್ಕನ್ನು ನಿರ್ಧರಿಸುವುದು ಸುಲಭದ ಕೆಲಸವಲ್ಲ. ಗಣಿತಶಾಸ್ತ್ರಜ್ಞ ಪಾಪಡಿಮಿಟ್ರಿಯು ಈ ಸಮಸ್ಯೆಯನ್ನು ಹೆಚ್ಚಿನ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ವಿಶ್ಲೇಷಿಸಿದ್ದಾರೆ; "ಮಿಶ್ರ ಚೀನೀ ಪೋಸ್ಟ್ ಮ್ಯಾನ್ ಎನ್. ಪಿ-ಪೂರ್ಣವಾಗಿದೆ, ಇನ್ಪುಟ್ ಗ್ರಾಫ್ ಸಮತಟ್ಟಾಗಿದ್ದರೂ ಸಹ, ಪ್ರತಿ ಶೃಂಗವು ಗರಿಷ್ಠ ಮೂರು ಡಿಗ್ರಿಗಳನ್ನು ಹೊಂದಿದೆ, ಮತ್ತು ಪ್ರತಿ ಅಂಚು ಮತ್ತು ಚಾಪಕ್ಕೆ ಒಂದು ವೆಚ್ಚವಿದೆ". ಮಿಶ್ರ ಗ್ರಾಫ್ ಯೂಲೆರಿಯನ್ ಆಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವ ಪ್ರಕ್ರಿಯೆಯು ಮಿಶ್ರ ಚೀನೀ ಪೋಸ್ಟ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ರಚಿಸಲು ಮುಖ್ಯವಾಗಿದೆ. ಯೂಲೆರಿಯನ್ ಚಕ್ರವನ್ನು ಹೊಂದಲು ಮಿಶ್ರ ಗ್ರಾಫ್ ಜಿ ಯ ಡಿಗ್ರಿಗಳು ಸಮನಾಗಿರಬೇಕು, ಆದರೆ ಇದು ಸಾಕಾಗುವುದಿಲ್ಲ. ಅಂದಾಜು ಮಿಶ್ರ ಚೀನೀ ಪೋಸ್ಟ್ಮ್ಯಾನ್ ಎನ್. ಪಿ-ಹಾರ್ಡ್ ಎಂಬ ಅಂಶವು ಬಹುಪದೀಯ ಸಮಯದ ಕ್ರಮಾವಳಿಗಳ ಹುಡುಕಾಟಕ್ಕೆ ಕಾರಣವಾಗಿದೆ, ಅದು ಸಮಂಜಸವಾದ ಮಿತಿಗೆ ಗರಿಷ್ಠ ಪರಿಹಾರವನ್ನು ತಲುಪುತ್ತದೆ. ಫ್ರೆಡೆರಿಕ್ಸನ್ ಸಮತಟ್ಟಾದ ನಕ್ಷೆಗಳಿಗೆ ಅನ್ವಯಿಸಬಹುದಾದ 3/2 ಅಂಶದೊಂದಿಗೆ ಒಂದು ವಿಧಾನವನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಿದರು, ಮತ್ತು ರಾಘವಚಾರಿ ಮತ್ತು ವೀರಸ್ವಾಮಿ ಸಮತಟ್ಟಾಗಿರಬೇಕಾದ ವಿಧಾನವನ್ನು ಕಂಡುಕೊಂಡರು. ಆದಾಗ್ಯೂ, ಬಹುಪದೀಯ ಸಮಯವು ಶಿರಚ್ಛೇದನದ ವೆಚ್ಚವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಿಲ್ಲ, ಅದು ಬೀದಿಗಳನ್ನು ತಲುಪಲು ಹಿಮದ ನೇಗಿಲು ತೆಗೆದುಕೊಳ್ಳುವ ಸಮಯವನ್ನು ಉಳುಮೆ ಮಾಡುತ್ತದೆ ಅಥವಾ ಬೀದಿಗಳನ್ನು ತಲುಪಲು ಬೀದಿ ಸ್ವಚ್ಛಗೊಳಿಸುವವನು ಅದನ್ನು ಗುಡಿಸುತ್ತಾನೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಒಂದು ಶೃಂಗದ ಗುಂಪಿನೊಂದಿಗೆ ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದ ಮಿಶ್ರ ಗ್ರಾಫ್, ಮತ್ತು ಅಂಚಿನ ಸೆಟ್, ಒಂದು ಆರ್ಕ್ ಸೆಟ್ ಮತ್ತು ಪ್ರತಿಯೊಂದಕ್ಕೂ ಋಣಾತ್ಮಕವಲ್ಲದ ವೆಚ್ಚವನ್ನು ನೀಡಿದರೆ, ಎಂ. ಸಿ. ಪಿ. ಪಿ. ಯು ಕನಿಷ್ಠ ಒಮ್ಮೆಯಾದರೂ ಪ್ರತಿ ಲಿಂಕ್ ಮೂಲಕ ಹಾದುಹೋಗುವ ಕನಿಷ್ಠ-ವೆಚ್ಚದ ಪ್ರವಾಸವನ್ನು ಕಂಡುಹಿಡಿಯುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಕೊಟ್ಟಿರುವ,,, ನಿಖರವಾಗಿ ಒಂದು ಅಂತಿಮ ಬಿಂದುವನ್ನು ಹೊಂದಿರುವ ಅಂಚುಗಳ ಗುಂಪನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಮತ್ತು. ಒಂದು ಶೃಂಗವನ್ನು ನೀಡಿದರೆ, (ಇಂಡೆಗ್ರೀ) ಪ್ರವೇಶಿಸುವ ಚಾಪಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ, (ಔಟ್ ಡಿಗ್ರಿ) ಹೊರಹೋಗುವ ಚಾಪಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಮತ್ತು (ಡಿಗ್ರಿ) ಸಂಪರ್ಕಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಅದನ್ನು ಗಮನಿಸಿ. ಅದರ ಎಲ್ಲಾ ಶೃಂಗಗಳು ಸಮ ಡಿಗ್ರಿ ಹೊಂದಿದ್ದರೂ ಸಹ ಮಿಶ್ರ ಗ್ರಾಫ್ ಅನ್ನು ಕರೆಯಲಾಗುತ್ತದೆ, ಪ್ರತಿ ಶೃಂಗಕ್ಕೂ ಇದನ್ನು ಸಮ್ಮಿತೀಯ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಮತ್ತು ಯಾವುದೇ ಶೃಂಗಗಳ ಉಪವಿಭಾಗವನ್ನು ನೀಡಿದರೆ, ಆರ್ಕ್ಗಳ ಸಂಖ್ಯೆ ಮತ್ತು ಆರ್ಕ್ಗಳ ಸಂಖ್ಯೆಯ ನಡುವಿನ ವ್ಯತ್ಯಾಸವು ಸೇರುವ ಮತ್ತು ನಿರ್ದೇಶಿಸದ ಅಂಚುಗಳ ಸಂಖ್ಯೆಗಿಂತ ಹೆಚ್ಚಾಗಿರುವುದಿಲ್ಲ. ಸಮ ಮತ್ತು ಸಮತೋಲಿತವಾಗಿದ್ದರೆ ಮಾತ್ರ ಮಿಶ್ರ ಗ್ರಾಫ್ ಯೂಲೆರಿಯನ್ ಆಗಿರುತ್ತದೆ ಎಂಬುದು ಎಲ್ಲರಿಗೂ ತಿಳಿದಿರುವ ಸಂಗತಿಯಾಗಿದೆ. ಸಮ ಮತ್ತು ಸಮ್ಮಿತೀಯವಾಗಿದ್ದರೆ, G ಸಹ ಸಮತೋಲಿತವಾಗಿರುತ್ತದೆ (ಮತ್ತು ಯೂಲೆರಿಯನ್) ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಇದಲ್ಲದೆ, ಸಮವಾಗಿದ್ದರೆ, ಅದನ್ನು ನಿಖರವಾಗಿ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಎಂ. ಸಿ. ಪಿ. ಪಿ ಅಲ್ಗಾರಿದಮ್ ಸಹ ಸಮ ಮತ್ತು ಬಲವಾಗಿ ಸಂಪರ್ಕಿತವಾದ ಮಿಶ್ರ ಗ್ರಾಫ್ ಅನ್ನು ನೀಡಿದರೆ, ಅದೇ ವೆಚ್ಚಗಳೊಂದಿಗೆ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಅಂಚುಗಳಿಗೆ ದಿಕ್ಕನ್ನು ನಿಯೋಜಿಸುವ ಮೂಲಕ ಪಡೆದ ಆರ್ಕ್ಗಳ ಗುಂಪಾಗಿರಲಿ. ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರದಲ್ಲಿರುವ ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ i ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಒಂದು ಶೃಂಗವನ್ನು ಪೂರೈಕೆಯ ಬೇಡಿಕೆಯೊಂದಿಗೆ ಮೂಲ (ಸಿಂಕ್) ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಸಮ ನಕ್ಷೆಯಂತೆ, ಎಲ್ಲಾ ಸರಬರಾಜುಗಳು ಮತ್ತು ಬೇಡಿಕೆಗಳು ಸಮ ಸಂಖ್ಯೆಗಳಾಗಿವೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ (ಶೂನ್ಯವನ್ನು ಸಮ ಸಂಖ್ಯೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ). ಆ ಅನುಗುಣವಾದ ಅಂಚುಗಳ ವೆಚ್ಚಗಳೊಂದಿಗೆ ಮತ್ತು ಅದರೊಂದಿಗೆ ವಿರುದ್ಧ ದಿಕ್ಕಿನಲ್ಲಿ ಆರ್ಕ್ಗಳ ಸೆಟ್ ಆಗಿರಲಿ ಮತ್ತು ಶೂನ್ಯ ವೆಚ್ಚದಲ್ಲಿ ಸಮಾನಾಂತರವಾದ ಆರ್ಕ್ಗಳ ಸೆಟ್ ಆಗಿರಲಿ. ಎಲ್ಲಾ ಶೃಂಗಗಳ ಬೇಡಿಕೆಗಳನ್ನು ಪೂರೈಸಲು, ಗ್ರಾಫ್ನಲ್ಲಿ ಕನಿಷ್ಠ ವೆಚ್ಚದ ಹರಿವಿನ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಿ, ಇದರಲ್ಲಿ ಪ್ರತಿ ಚಾಪವು ಅನಂತ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಚಾಪವು ಸಾಮರ್ಥ್ಯ 2 ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಅತ್ಯುತ್ತಮ ಹರಿವು ಆಗಿರಲಿ. ಡು ನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಆರ್ಕ್ಗೆಃ ಒಂದು ವೇಳೆ, ನಂತರ ಅನುಗುಣವಾದ ಅಂಚನ್ನು ಒಂದರಿಂದ ಇನ್ನೊಂದಕ್ಕೆ ತಿರುಗಿಸಿ (ಹಂತ 1 ರಲ್ಲಿ ಸಂಬಂಧಿತ ಅಂಚಿಗೆ ನಿಗದಿಪಡಿಸಲಾದ ದಿಕ್ಕು "ತಪ್ಪು"); ಒಂದು ವೇಳೆ, G ಯಲ್ಲಿ ಅನುಗುಣವಾದ ಅಂಚನ್ನು ಒಂದರಿಂದ ಇನ್ನೊಂದಕ್ಕೆ ತಿರುಗಿಸಿ (ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಹಂತ 1 ರಲ್ಲಿನ ದೃಷ್ಟಿಕೋನವು "ಸರಿ" ಆಗಿತ್ತು). ಈ ಪ್ರಕರಣವು ಅಸಾಧ್ಯವಾಗಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಏಕೆಂದರೆ ಆರ್ಕ್ಗಳ ಮೂಲಕ ಹರಿಯುವ ಎಲ್ಲಾ ಹರಿವಿನ ಮೌಲ್ಯಗಳು ಸಮ ಸಂಖ್ಯೆಗಳಾಗಿವೆ. ಪ್ರತಿ ಕಮಾನಿನ ಪ್ರತಿಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ವರ್ಧನೆ. ಪರಿಣಾಮವಾಗಿ ಬರುವ ರೇಖಾಚಿತ್ರವು ಸಮ ಮತ್ತು ಸಮ್ಮಿತೀಯವಾಗಿರುತ್ತದೆ. ಮಿಶ್ರ ಗ್ರಾಫ್ ಸಮವಾಗಿರದಿದ್ದಾಗ ಮತ್ತು ಎಲ್ಲಾ ನೋಡ್ಗಳು ಸಮ ಡಿಗ್ರಿ ಹೊಂದಿರದಿದ್ದಾಗ, ಗ್ರಾಫ್ ಅನ್ನು ಸಮ ಗ್ರಾಫ್ ಆಗಿ ಪರಿವರ್ತಿಸಬಹುದು. ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದ ಮಿಶ್ರ ಗ್ರಾಫ್ ಆಗಿರಲಿ. ಆರ್ಕ್ ನಿರ್ದೇಶನಗಳನ್ನು ನಿರ್ಲಕ್ಷಿಸುವ ಮೂಲಕ ಬೆಸ ಡಿಗ್ರಿ ನೋಡ್ಗಳನ್ನು ಹುಡುಕಿ ಮತ್ತು ಕನಿಷ್ಠ-ವೆಚ್ಚದ ಹೊಂದಾಣಿಕೆಯನ್ನು ಪಡೆಯಿರಿ. ಸಮ ರೇಖಾಚಿತ್ರವನ್ನು ರಚಿಸಲು ಕನಿಷ್ಠ ವೆಚ್ಚದ ಹೊಂದಾಣಿಕೆಯಿಂದ ಅಂಚುಗಳೊಂದಿಗೆ ರೇಖಾಚಿತ್ರವನ್ನು ಹೆಚ್ಚಿಸಿ. ರೇಖಾಚಿತ್ರವು ಸಮವಾಗಿದೆ ಆದರೆ ಸಮ್ಮಿತೀಯವಾಗಿಲ್ಲ ಮತ್ತು ಯೂಲೇರಿಯನ್ ಮಿಶ್ರ ರೇಖಾಚಿತ್ರವು ಸಮ ಮತ್ತು ಸಮ್ಮಿತೀಯವಾಗಿದೆ. ಸಮವಾಗಿರದ ಸಮ್ಮಿತೀಯ ರೇಖಾಚಿತ್ರವನ್ನು ಪಡೆಯಲು ಕನಿಷ್ಠ ವೆಚ್ಚದ ಹರಿವಿನ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಿ. ಕೊನೆಯ ಹಂತವು ಸಮ್ಮಿತೀಯ ರೇಖಾಚಿತ್ರವನ್ನು ಸಮವಾಗಿಸುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಬೆಸ ಡಿಗ್ರಿ ನೋಡ್ಗಳನ್ನು ಲೇಬಲ್ ಮಾಡಿ. ಆರ್ಕ್ ಸೆಟ್ನಲ್ಲಿ ರೇಖೆಗಳು ಮತ್ತು ಅಂಚಿನ ಸೆಟ್ನಲ್ಲಿ ರೇಖೆಗಳ ನಡುವೆ ಪರ್ಯಾಯವಾಗಿರುವ ಚಕ್ರಗಳನ್ನು ಹುಡುಕಿ, ಅದು ಬಿಂದುಗಳಲ್ಲಿ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಒಳಗೆ ಇರುವ ಕಮಾನುಗಳನ್ನು ದಿಕ್ಕಿಲ್ಲದ ಅಂಚುಗಳೆಂದು ಪರಿಗಣಿಸಬೇಕೇ ಹೊರತು ದಿಕ್ಕಿನಲ್ಲಿರುವ ಕಮಾನುಗಳೆಂದು ಪರಿಗಣಿಸಬಾರದು. ಜೆನೆಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ ಹುವಾ ಜಿಯಾಂಗ್ ಮತ್ತು ಇತರರು ಪ್ರಕಟಿಸಿದ ಒಂದು ಪ್ರಬಂಧ. ಜನಸಂಖ್ಯೆಯ ಮೇಲೆ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ಮೂಲಕ ಮಿಶ್ರ ಚೀನೀ ಪೋಸ್ಟ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಜೆನೆಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ರೂಪಿಸಿದರು. ಎಂ. ಸಿ. ಪಿ. ಪಿ. ಯ ಇತರ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳಿಗೆ ಹೋಲಿಸಿದರೆ ಕ್ರಮಾವಳಿಯು ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸಿತು. ಕೆಪಾಸಿಟೆಡ್ ಆರ್ಕ್ ರೂಟಿಂಗ್ ಸಮಸ್ಯೆಯನ್ನು ಸಹ ನೋಡಿ ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳು