ਕ੍ਰਸਕਲ ਦਾ ਐਲਗੋਰਿਦਮ ਮੇਜ਼ ਜਨਰੇਟਰ

ਕ੍ਰਸਕਲ ਦਾ ਐਲਗੋਰਿਦਮ ਇੱਕ ਘੱਟੋ-ਘੱਟ ਸਪੈਨਿੰਗ ਟ੍ਰੀ ਐਲਗੋਰਿਦਮ ਹੈ ਜਿਸਨੂੰ ਮੇਜ਼ ਜਨਰੇਸ਼ਨ ਲਈ ਅਨੁਕੂਲ ਬਣਾਇਆ ਜਾ ਸਕਦਾ ਹੈ। ਇਹ ਸੰਪੂਰਨ ਮੇਜ਼ ਬਣਾਉਣ ਲਈ ਖਾਸ ਤੌਰ 'ਤੇ ਪ੍ਰਭਾਵਸ਼ਾਲੀ ਹੈ। ਕ੍ਰਸਕਲ ਦੇ ਐਲਗੋਰਿਦਮ ਦਾ ਇੱਕ ਵਿਕਲਪ ਪ੍ਰਾਈਮ ਦਾ ਐਲਗੋਰਿਦਮ ਹੈ, ਜੋ ਕਿ ਇੱਕ ਘੱਟੋ-ਘੱਟ ਸਪੈਨਿੰਗ ਟ੍ਰੀ ਐਲਗੋਰਿਦਮ ਵੀ ਹੈ, ਪਰ ਕਿਉਂਕਿ ਉਹ ਇੱਕੋ ਜਿਹੇ ਮੇਜ਼ ਪੈਦਾ ਕਰਦੇ ਹਨ ਅਤੇ ਕ੍ਰਸਕਲ ਤੇਜ਼ੀ ਨਾਲ ਚੱਲਦਾ ਹੈ, ਮੈਂ ਪ੍ਰਾਈਮ ਨੂੰ ਲਾਗੂ ਕਰਨ ਦੀ ਖੇਚਲ ਨਹੀਂ ਕੀਤੀ।

ਇੱਕ ਸੰਪੂਰਨ ਭੁਲੇਖਾ ਇੱਕ ਭੁਲੇਖਾ ਹੁੰਦਾ ਹੈ ਜਿਸ ਵਿੱਚ ਭੁਲੇਖੇ ਦੇ ਕਿਸੇ ਵੀ ਬਿੰਦੂ ਤੋਂ ਕਿਸੇ ਹੋਰ ਬਿੰਦੂ ਤੱਕ ਬਿਲਕੁਲ ਇੱਕ ਰਸਤਾ ਹੁੰਦਾ ਹੈ। ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਤੁਸੀਂ ਚੱਕਰਾਂ ਵਿੱਚ ਘੁੰਮ ਨਹੀਂ ਸਕਦੇ, ਪਰ ਤੁਸੀਂ ਅਕਸਰ ਮੁਰਦਾ ਸਿਰਿਆਂ ਦਾ ਸਾਹਮਣਾ ਕਰੋਗੇ, ਜਿਸ ਨਾਲ ਤੁਹਾਨੂੰ ਪਿੱਛੇ ਮੁੜਨ ਅਤੇ ਵਾਪਸ ਜਾਣ ਲਈ ਮਜਬੂਰ ਹੋਣਾ ਪਵੇਗਾ।

ਇੱਥੇ ਤਿਆਰ ਕੀਤੇ ਗਏ ਮੇਜ਼ ਨਕਸ਼ਿਆਂ ਵਿੱਚ ਬਿਨਾਂ ਕਿਸੇ ਸ਼ੁਰੂਆਤੀ ਅਤੇ ਸਮਾਪਤੀ ਸਥਿਤੀ ਦੇ ਇੱਕ ਡਿਫੌਲਟ ਸੰਸਕਰਣ ਸ਼ਾਮਲ ਹੈ, ਇਸ ਲਈ ਤੁਸੀਂ ਉਹਨਾਂ ਦਾ ਫੈਸਲਾ ਆਪਣੇ ਲਈ ਕਰ ਸਕਦੇ ਹੋ: ਮੇਜ਼ ਦੇ ਕਿਸੇ ਵੀ ਬਿੰਦੂ ਤੋਂ ਕਿਸੇ ਹੋਰ ਬਿੰਦੂ ਤੱਕ ਇੱਕ ਹੱਲ ਹੋਵੇਗਾ। ਜੇਕਰ ਤੁਸੀਂ ਪ੍ਰੇਰਨਾ ਚਾਹੁੰਦੇ ਹੋ, ਤਾਂ ਤੁਸੀਂ ਇੱਕ ਸੁਝਾਈ ਗਈ ਸ਼ੁਰੂਆਤ ਅਤੇ ਸਮਾਪਤੀ ਸਥਿਤੀ ਨੂੰ ਸਮਰੱਥ ਬਣਾ ਸਕਦੇ ਹੋ - ਅਤੇ ਦੋਵਾਂ ਵਿਚਕਾਰ ਹੱਲ ਵੀ ਦੇਖ ਸਕਦੇ ਹੋ।

ਕ੍ਰੁਸਕਲ ਦੇ ਅਲਗੋਰੀਥਮ ਬਾਰੇ

ਕ੍ਰੁਸਕਲ ਦਾ ਅਲਗੋਰੀਥਮ ਜੋਸਫ ਬਰਨਾਰਡ ਕ੍ਰੁਸਕਲ ਜੂਨੀਅਰ ਦੁਆਰਾ ਬਣਾਇਆ ਗਿਆ ਸੀ, ਜੋ ਕਿ ਇੱਕ ਅਮਰੀਕੀ ਗਣਿਤ ਵਿਗਿਆਨੀ, ਅੰਕੜੇ ਵਿਗਿਆਨੀ ਅਤੇ ਕੰਪਿਊਟਰ ਵਿਗਿਆਨੀ ਸਨ। ਉਸਨੇ ਪਹਿਲੀ ਵਾਰੀ 1956 ਵਿੱਚ ਆਪਣੇ ਪੇਪਰ "ਗ੍ਰਾਫ ਦੇ ਸਭ ਤੋਂ ਛੋਟੇ ਸਪੈਨਿੰਗ ਸਬਟ੍ਰੀ ਅਤੇ ਯਾਤਰਾ ਕਰਨ ਵਾਲੇ ਵਿਕਰੇਤਾ ਸਮੱਸਿਆ" ਵਿੱਚ ਅਲਗੋਰੀਥਮ ਦਾ ਵਰਣਨ ਕੀਤਾ ਸੀ।

ਇਹ ਅਲਗੋਰੀਥਮ ਗ੍ਰਾਫ ਦਾ ਘੱਟੋ-ਘੱਟ ਸਪੈਨਿੰਗ ਟ੍ਰੀ (MST) ਲੱਭਣ ਲਈ ਬਣਾਇਆ ਗਿਆ ਹੈ, ਜਿਸ ਨਾਲ ਇਹ ਸੁਨਿਸ਼ਚਿਤ ਕਰਦਾ ਹੈ ਕਿ ਸਾਰੇ ਕੋਣ ਘੱਟੋ-ਘੱਟ ਸੰਭਵ ਕੁੱਲ ਕਿਨਾਰਾ ਭਾਰ ਨਾਲ ਜੁੜੇ ਹੋਏ ਹਨ, ਜਦੋਂ ਕਿ ਚੱਕਰਾਂ ਤੋਂ ਬਚਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕੀਤੀ ਜਾਂਦੀ ਹੈ।

ਕ੍ਰੁਸਕਲ ਦੇ ਅਲਗੋਰੀਥਮ ਦਾ ਮੈਜ਼ ਜਨਰੇਸ਼ਨ ਲਈ ਕਿਵੇਂ ਕੰਮ ਕਰਦਾ ਹੈ

ਕਦਮ 1: ਪ੍ਰਾਰੰਭਿਕੀ

• ਮੈਜ਼ ਵਿੱਚ ਹਰ ਇੱਕ ਕੋਸ਼ਿਕਾ ਨੂੰ ਇੱਕ ਵੱਖਰੇ ਸੈਟ (ਇੱਕ ਵਿਲੱਖਣ ਘਟਕਾ) ਵਾਂਗੁ ਤਰਜੀਹ ਦਿਓ।
• ਪੜੋਸੀ ਕੋਸ਼ਿਕਾਵਾਂ ਦੇ ਵਿਚਕਾਰ ਸਾਰੇ ਕੰਧਾਂ ਨੂੰ ਸੰਭਾਵਿਤ ਕਿਨਾਰਿਆਂ ਵਜੋਂ ਸੂਚੀਬੱਧ ਕਰੋ।

ਕਦਮ 2: ਕੰਧਾਂ ਨੂੰ ਛਾਂਟੋ

• ਕੰਧਾਂ ਨੂੰ ਸ਼ਫਲ ਜਾਂ ਯਾਦ੍ਰਿਤ ਕ੍ਰਮ ਵਿੱਚ ਠੇਲੋ। ਜੇ ਇਸਨੂੰ ਇੱਕ ਅਸਲੀ ਕ੍ਰੁਸਕਲ ਦਾ ਅਲਗੋਰੀਥਮ ਲਾਗੂ ਕੀਤਾ ਜਾ ਰਿਹਾ ਹੈ, ਤਾਂ ਕੰਧਾਂ ਨੂੰ ਇੱਕ ਯਾਦ੍ਰਿਤ ਕ੍ਰਮ ਵਿੱਚ ਛਾਂਟੋ (ਕਿਉਂਕਿ ਮੈਜ਼ ਜਨਰੇਸ਼ਨ ਨੂੰ ਭਾਰ ਦੀ ਲੋੜ ਨਹੀਂ ਹੁੰਦੀ)।

ਕਦਮ 3: ਕੰਧਾਂ ਦੀ ਪ੍ਰਕਿਰਿਆ

• ਸ਼ਫਲ ਕੀਤੀਆਂ ਗਈਆਂ ਕੰਧਾਂ ਵਿੱਚੋਂ ਗੁਜ਼ਰੋ।
• ਜੇਕਰ ਕੰਧ ਦੇ ਨਾਲ ਵੰਡੀਆਂ ਗਈਆਂ ਦੋਹਾਂ ਕੋਸ਼ਿਕਾਵਾਂ ਵੱਖ-ਵੱਖ ਸੈਟਾਂ ਵਿੱਚ ਸ਼ਾਮਲ ਹਨ (ਜਾਂ ਇਹ ਮੈਜ਼ ਵਿੱਚ ਹਜੇ ਤੱਕ ਜੁੜੀਆਂ ਨਹੀਂ ਹਨ), ਤਾਂ ਕੰਧ ਨੂੰ ਹਟਾ ਦਿਓ ਅਤੇ ਸੈਟਾਂ ਨੂੰ ਜੋੜੋ।
• ਜੇ ਉਹ ਪਹਿਲਾਂ ਹੀ ਇੱਕੋ ਸੈਟ ਵਿੱਚ ਹਨ, ਤਾਂ ਕੰਧ ਨੂੰ ਛੱਡ ਦਿਓ (ਚੱਕਰਾਂ ਤੋਂ ਬਚਣ ਲਈ)।

ਕਦਮ 4: ਮੁਕੰਮਲ ਹੋਣ ਤੱਕ ਜਾਰੀ ਰੱਖੋ

• ਇਹ ਪ੍ਰਕਿਰਿਆ ਇਸ ਸਮੇਂ ਤੱਕ ਦੁਹਰਾਓ ਜਦ ਤੱਕ ਸਾਰੀ ਕੋਸ਼ਿਕਾਵਾਂ ਜੁੜ ਨਹੀਂ ਜਾਂਦੀਆਂ ਅਤੇ ਇੱਕੋ ਸਪੈਨਿੰਗ ਟ੍ਰੀ ਬਣ ਜਾਂਦਾ ਹੈ।
• ਅੰਤ ਵਿੱਚ, ਹਰ ਕੋਸ਼ਿਕਾ ਬਿਨਾ ਚੱਕਰਾਂ ਜਾਂ ਇਕੱਲੇ ਹਿੱਸਿਆਂ ਦੇ ਦੂਜਿਆਂ ਨਾਲ ਜੁੜੀ ਹੋਈ ਹੈ।

ਚੁੰਕਿ ਕ੍ਰੁਸਕਲ ਦੇ ਅਲਗੋਰੀਥਮ ਨੂੰ ਸੈਟਾਂ ਨੂੰ ਜੋੜਨ ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ, ਇਸਨੂੰ ਯੂਨੀਅਨ-ਫਾਈਂਡ ਅਲਗੋਰੀਥਮ ਦੀ ਵਰਤੋਂ ਨਾਲ ਅਪਟਿਮਾਈਜ਼ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਜੋ ਮੈਜ਼ ਜਨਰੇਸ਼ਨ ਦੌਰਾਨ ਜੁੜੀਆਂ ਹੋਈਆਂ ਕੋਸ਼ਿਕਾਵਾਂ ਨੂੰ ਟ੍ਰੈਕ ਕਰਨ ਦਾ ਇੱਕ ਪ੍ਰਭਾਵਸ਼ਾਲੀ ਤਰੀਕਾ ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ। ਤੁਸੀਂ ਮੇਰੇ PHP ਵਿਚਾਰਣ ਦੀ ਅਮਲ ਕਰਨ ਨੂੰ ਇੱਥੇ ਦੇਖ ਸਕਦੇ ਹੋ: PHP ਵਿੱਚ ਡਿਸਜੋਇੰਟ ਸੈੱਟ (ਯੂਨੀਅਨ-ਫਾਈਂਡ ਐਲਗੋਰਿਦਮ)