ਪੈਰਾਮੀਟਰਾਈਜ਼ਡ ਐਲਗੋਰਿਦਮ ਨਾਲ ਐਨਪੀ-ਹਾਰਡ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਕਿਵੇਂ ਹੱਲ ਕਰਨਾ ਹੈ

ਖੋਜ ਕਾਰਜ ਸ਼ਾਇਦ ਸਾਡੀ ਸਿਖਲਾਈ ਦਾ ਸਭ ਤੋਂ ਦਿਲਚਸਪ ਹਿੱਸਾ ਹੈ। ਵਿਚਾਰ ਇਹ ਹੈ ਕਿ ਯੂਨੀਵਰਸਿਟੀ ਵਿਚ ਰਹਿੰਦੇ ਹੋਏ ਵੀ ਆਪਣੀ ਚੁਣੀ ਹੋਈ ਦਿਸ਼ਾ ਵਿਚ ਆਪਣੇ ਆਪ ਨੂੰ ਅਜ਼ਮਾਉਣਾ ਹੈ। ਉਦਾਹਰਨ ਲਈ, ਸਾਫਟਵੇਅਰ ਇੰਜੀਨੀਅਰਿੰਗ ਅਤੇ ਮਸ਼ੀਨ ਲਰਨਿੰਗ ਦੇ ਖੇਤਰਾਂ ਦੇ ਵਿਦਿਆਰਥੀ ਅਕਸਰ ਕੰਪਨੀਆਂ ਵਿੱਚ ਖੋਜ ਕਰਨ ਜਾਂਦੇ ਹਨ (ਮੁੱਖ ਤੌਰ 'ਤੇ JetBrains ਜਾਂ Yandex, ਪਰ ਸਿਰਫ਼ ਨਹੀਂ)।

ਇਸ ਪੋਸਟ ਵਿੱਚ ਮੈਂ ਕੰਪਿਊਟਰ ਸਾਇੰਸ ਵਿੱਚ ਆਪਣੇ ਪ੍ਰੋਜੈਕਟ ਬਾਰੇ ਗੱਲ ਕਰਾਂਗਾ। ਮੇਰੇ ਕੰਮ ਦੇ ਹਿੱਸੇ ਵਜੋਂ, ਮੈਂ ਸਭ ਤੋਂ ਮਸ਼ਹੂਰ NP-ਸਖਤ ਸਮੱਸਿਆਵਾਂ ਵਿੱਚੋਂ ਇੱਕ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਅਧਿਐਨ ਕੀਤਾ ਅਤੇ ਅਮਲ ਵਿੱਚ ਲਿਆਇਆ: ਸਿਰਲੇਖ ਨੂੰ ਕਵਰ ਕਰਨ ਦੀ ਸਮੱਸਿਆ.

ਅੱਜ ਕੱਲ੍ਹ, NP- ਹਾਰਡ ਸਮੱਸਿਆਵਾਂ ਲਈ ਇੱਕ ਦਿਲਚਸਪ ਪਹੁੰਚ ਬਹੁਤ ਤੇਜ਼ੀ ਨਾਲ ਵਿਕਸਤ ਹੋ ਰਹੀ ਹੈ - ਪੈਰਾਮੀਟਰਾਈਜ਼ਡ ਐਲਗੋਰਿਦਮ. ਮੈਂ ਤੁਹਾਨੂੰ ਗਤੀ ਵਧਾਉਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰਾਂਗਾ, ਤੁਹਾਨੂੰ ਕੁਝ ਸਧਾਰਨ ਪੈਰਾਮੀਟਰਾਈਜ਼ਡ ਐਲਗੋਰਿਦਮ ਦੱਸਾਂਗਾ ਅਤੇ ਇੱਕ ਸ਼ਕਤੀਸ਼ਾਲੀ ਵਿਧੀ ਦਾ ਵਰਣਨ ਕਰਾਂਗਾ ਜਿਸ ਨੇ ਮੇਰੀ ਬਹੁਤ ਮਦਦ ਕੀਤੀ ਹੈ। ਮੈਂ PACE ਚੈਲੇਂਜ ਮੁਕਾਬਲੇ ਵਿੱਚ ਆਪਣੇ ਨਤੀਜੇ ਪੇਸ਼ ਕੀਤੇ: ਓਪਨ ਟੈਸਟਾਂ ਦੇ ਨਤੀਜਿਆਂ ਦੇ ਅਨੁਸਾਰ, ਮੇਰਾ ਹੱਲ ਤੀਜਾ ਸਥਾਨ ਲੈਂਦਾ ਹੈ, ਅਤੇ ਅੰਤਮ ਨਤੀਜੇ 1 ਜੁਲਾਈ ਨੂੰ ਜਾਣੇ ਜਾਣਗੇ।

ਮੇਰੇ ਬਾਰੇ

ਮੇਰਾ ਨਾਮ ਵੈਸੀਲੀ ਅਲਫੇਰੋਵ ਹੈ, ਮੈਂ ਹੁਣ ਨੈਸ਼ਨਲ ਰਿਸਰਚ ਯੂਨੀਵਰਸਿਟੀ ਹਾਇਰ ਸਕੂਲ ਆਫ਼ ਇਕਨਾਮਿਕਸ - ਸੇਂਟ ਪੀਟਰਸਬਰਗ ਵਿੱਚ ਆਪਣਾ ਤੀਜਾ ਸਾਲ ਪੂਰਾ ਕਰ ਰਿਹਾ ਹਾਂ। ਮੈਂ ਆਪਣੇ ਸਕੂਲ ਦੇ ਦਿਨਾਂ ਤੋਂ ਐਲਗੋਰਿਦਮ ਵਿੱਚ ਦਿਲਚਸਪੀ ਰੱਖਦਾ ਹਾਂ, ਜਦੋਂ ਮੈਂ ਮਾਸਕੋ ਸਕੂਲ ਨੰਬਰ 179 ਵਿੱਚ ਪੜ੍ਹਿਆ ਅਤੇ ਕੰਪਿਊਟਰ ਸਾਇੰਸ ਓਲੰਪੀਆਡ ਵਿੱਚ ਸਫਲਤਾਪੂਰਵਕ ਹਿੱਸਾ ਲਿਆ।

ਪੈਰਾਮੀਟਰਾਈਜ਼ਡ ਐਲਗੋਰਿਦਮ ਵਿੱਚ ਮਾਹਿਰਾਂ ਦੀ ਇੱਕ ਸੀਮਤ ਸੰਖਿਆ ਬਾਰ ਵਿੱਚ ਦਾਖਲ ਹੁੰਦੀ ਹੈ...

ਕਿਤਾਬ ਵਿੱਚੋਂ ਲਈ ਗਈ ਉਦਾਹਰਣ "ਪੈਰਾਮੀਟਰਾਈਜ਼ਡ ਐਲਗੋਰਿਦਮ"

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

ਕਿਉਂਕਿ ਤੁਹਾਡਾ ਸ਼ਹਿਰ ਛੋਟਾ ਹੈ, ਤੁਸੀਂ ਜਾਣਦੇ ਹੋ ਕਿ ਸਰਪ੍ਰਸਤਾਂ ਦੇ ਕਿਹੜੇ ਜੋੜੇ ਲੜਨ ਦੀ ਸੰਭਾਵਨਾ ਰੱਖਦੇ ਹਨ ਜੇਕਰ ਉਹ ਇੱਕ ਬਾਰ ਵਿੱਚ ਇਕੱਠੇ ਹੁੰਦੇ ਹਨ। ਕੀ ਤੁਹਾਡੇ ਕੋਲ ਇੱਕ ਸੂਚੀ ਹੈ n ਉਹ ਲੋਕ ਜੋ ਅੱਜ ਰਾਤ ਬਾਰ ਵਿੱਚ ਆਉਣਗੇ। ਤੁਸੀਂ ਕਸਬੇ ਦੇ ਕੁਝ ਲੋਕਾਂ ਨੂੰ ਬਿਨਾਂ ਕਿਸੇ ਲੜਾਈ ਵਿੱਚ ਪੈਣ ਤੋਂ ਬਾਹਰ ਰੱਖਣ ਦਾ ਫੈਸਲਾ ਕਰਦੇ ਹੋ। ਇਸਦੇ ਨਾਲ ਹੀ, ਤੁਹਾਡੇ ਬੌਸ ਮੁਨਾਫੇ ਨੂੰ ਗੁਆਉਣਾ ਨਹੀਂ ਚਾਹੁੰਦੇ ਹਨ ਅਤੇ ਨਾਖੁਸ਼ ਹੋਣਗੇ ਜੇਕਰ ਤੁਸੀਂ ਇਸ ਤੋਂ ਵੱਧ ਨਹੀਂ ਹੋਣ ਦਿੰਦੇ k ਲੋਕ

ਬਦਕਿਸਮਤੀ ਨਾਲ, ਤੁਹਾਡੇ ਸਾਹਮਣੇ ਸਮੱਸਿਆ ਇੱਕ ਕਲਾਸਿਕ NP-ਹਾਰਡ ਸਮੱਸਿਆ ਹੈ। ਤੁਸੀਂ ਸ਼ਾਇਦ ਉਸ ਨੂੰ ਇਸ ਤਰ੍ਹਾਂ ਜਾਣਦੇ ਹੋ ਵਰਟੇਕਸ ਕਵਰ, ਜਾਂ ਇੱਕ ਸਿਰੇ ਨੂੰ ਢੱਕਣ ਵਾਲੀ ਸਮੱਸਿਆ ਦੇ ਰੂਪ ਵਿੱਚ। ਅਜਿਹੀਆਂ ਸਮੱਸਿਆਵਾਂ ਲਈ, ਆਮ ਕੇਸ ਵਿੱਚ, ਇੱਥੇ ਕੋਈ ਐਲਗੋਰਿਦਮ ਨਹੀਂ ਹਨ ਜੋ ਇੱਕ ਸਵੀਕਾਰਯੋਗ ਸਮੇਂ ਵਿੱਚ ਕੰਮ ਕਰਦੇ ਹਨ. ਸਟੀਕ ਹੋਣ ਲਈ, ਗੈਰ-ਪ੍ਰਮਾਣਿਤ ਅਤੇ ਕਾਫ਼ੀ ਮਜ਼ਬੂਤ ​​ਪਰਿਕਲਪਨਾ ETH (ਐਕਸਪੋਨੈਂਸ਼ੀਅਲ ਟਾਈਮ ਹਾਈਪੋਥੀਸਿਸ) ਕਹਿੰਦੀ ਹੈ ਕਿ ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਸਮੇਂ ਸਿਰ ਹੱਲ ਨਹੀਂ ਕੀਤਾ ਜਾ ਸਕਦਾ , ਭਾਵ, ਤੁਸੀਂ ਪੂਰੀ ਖੋਜ ਤੋਂ ਬਿਹਤਰ ਕਿਸੇ ਵੀ ਚੀਜ਼ ਬਾਰੇ ਨਹੀਂ ਸੋਚ ਸਕਦੇ। ਉਦਾਹਰਨ ਲਈ, ਮੰਨ ਲਓ ਕਿ ਕੋਈ ਤੁਹਾਡੀ ਬਾਰ ਵਿੱਚ ਆਉਣ ਵਾਲਾ ਹੈ n = 1000 ਮਨੁੱਖੀ. ਫਿਰ ਪੂਰੀ ਖੋਜ ਹੋਵੇਗੀ ਵਿਕਲਪ ਹਨ ਜੋ ਲਗਭਗ ਹਨ - ਪਾਗਲ ਰਕਮ. ਖੁਸ਼ਕਿਸਮਤੀ ਨਾਲ, ਤੁਹਾਡੇ ਪ੍ਰਬੰਧਨ ਨੇ ਤੁਹਾਨੂੰ ਇੱਕ ਸੀਮਾ ਦਿੱਤੀ ਹੈ ਕੇ = 10, ਇਸ ਲਈ ਸੰਜੋਗਾਂ ਦੀ ਸੰਖਿਆ ਜੋ ਤੁਹਾਨੂੰ ਦੁਹਰਾਉਣ ਦੀ ਲੋੜ ਹੈ ਬਹੁਤ ਘੱਟ ਹੈ: ਦਸ ਤੱਤਾਂ ਦੇ ਉਪ ਸਮੂਹਾਂ ਦੀ ਸੰਖਿਆ ਹੈ . ਇਹ ਬਿਹਤਰ ਹੈ, ਪਰ ਇਹ ਅਜੇ ਵੀ ਇੱਕ ਸ਼ਕਤੀਸ਼ਾਲੀ ਕਲੱਸਟਰ 'ਤੇ ਵੀ ਇੱਕ ਦਿਨ ਵਿੱਚ ਨਹੀਂ ਗਿਣਿਆ ਜਾਵੇਗਾ।

ਬਾਰ ਦੇ ਵਿਜ਼ਟਰਾਂ ਵਿਚਕਾਰ ਤਣਾਅਪੂਰਨ ਸਬੰਧਾਂ ਦੀ ਇਸ ਸੰਰਚਨਾ ਵਿੱਚ ਲੜਾਈ ਦੀ ਸੰਭਾਵਨਾ ਨੂੰ ਖਤਮ ਕਰਨ ਲਈ, ਤੁਹਾਨੂੰ ਬੌਬ, ਡੈਨੀਅਲ ਅਤੇ ਫੇਡੋਰ ਨੂੰ ਬਾਹਰ ਰੱਖਣ ਦੀ ਲੋੜ ਹੈ। ਅਜਿਹਾ ਕੋਈ ਹੱਲ ਨਹੀਂ ਜਿਸ ਵਿੱਚ ਸਿਰਫ਼ ਦੋ ਹੀ ਰਹਿ ਜਾਣਗੇ।

ਕੀ ਇਸਦਾ ਮਤਲਬ ਇਹ ਹੈ ਕਿ ਇਹ ਸਭ ਨੂੰ ਦੇਣ ਅਤੇ ਹਰ ਕਿਸੇ ਨੂੰ ਅੰਦਰ ਜਾਣ ਦੇਣ ਦਾ ਸਮਾਂ ਹੈ? ਆਉ ਹੋਰ ਵਿਕਲਪਾਂ 'ਤੇ ਵਿਚਾਰ ਕਰੀਏ. ਖੈਰ, ਉਦਾਹਰਨ ਲਈ, ਤੁਸੀਂ ਸਿਰਫ਼ ਉਨ੍ਹਾਂ ਲੋਕਾਂ ਨੂੰ ਨਹੀਂ ਦੇ ਸਕਦੇ ਜੋ ਬਹੁਤ ਵੱਡੀ ਗਿਣਤੀ ਵਿੱਚ ਲੋਕਾਂ ਨਾਲ ਲੜਨ ਦੀ ਸੰਭਾਵਨਾ ਰੱਖਦੇ ਹਨ. ਜੇ ਕੋਈ ਘੱਟੋ ਘੱਟ ਨਾਲ ਲੜ ਸਕਦਾ ਹੈ k+1 ਕੋਈ ਹੋਰ ਵਿਅਕਤੀ, ਫਿਰ ਤੁਸੀਂ ਨਿਸ਼ਚਤ ਤੌਰ 'ਤੇ ਉਸਨੂੰ ਅੰਦਰ ਨਹੀਂ ਆਉਣ ਦੇ ਸਕਦੇ - ਨਹੀਂ ਤਾਂ ਤੁਹਾਨੂੰ ਸਾਰਿਆਂ ਨੂੰ ਬਾਹਰ ਰੱਖਣਾ ਪਏਗਾ k+1 ਸ਼ਹਿਰ ਦੇ ਲੋਕ, ਜਿਨ੍ਹਾਂ ਨਾਲ ਉਹ ਲੜ ਸਕਦਾ ਹੈ, ਜੋ ਯਕੀਨੀ ਤੌਰ 'ਤੇ ਲੀਡਰਸ਼ਿਪ ਨੂੰ ਪਰੇਸ਼ਾਨ ਕਰੇਗਾ।

ਤੁਸੀਂ ਇਸ ਸਿਧਾਂਤ ਦੇ ਅਨੁਸਾਰ ਹਰ ਕਿਸੇ ਨੂੰ ਬਾਹਰ ਕੱਢ ਸਕਦੇ ਹੋ। ਫਿਰ ਹਰ ਕੋਈ ਹੋਰ ਨਾਲ ਲੜ ਸਕਦਾ ਹੈ k ਲੋਕ। ਉਨ੍ਹਾਂ ਨੂੰ ਬਾਹਰ ਸੁੱਟ ਦਿੱਤਾ k ਆਦਮੀ, ਤੁਸੀਂ ਇਸ ਤੋਂ ਵੱਧ ਕੁਝ ਨਹੀਂ ਰੋਕ ਸਕਦੇ ਝਗੜੇ ਇਸ ਦਾ ਮਤਲਬ ਹੈ ਕਿ ਜੇਕਰ ਇਸ ਤੋਂ ਵੱਧ ਹੈ ਜੇਕਰ ਕੋਈ ਵਿਅਕਤੀ ਘੱਟੋ-ਘੱਟ ਇੱਕ ਸੰਘਰਸ਼ ਵਿੱਚ ਸ਼ਾਮਲ ਹੈ, ਤਾਂ ਤੁਸੀਂ ਨਿਸ਼ਚਤ ਤੌਰ 'ਤੇ ਉਨ੍ਹਾਂ ਸਾਰਿਆਂ ਨੂੰ ਰੋਕ ਨਹੀਂ ਸਕਦੇ। ਕਿਉਂਕਿ, ਬੇਸ਼ੱਕ, ਤੁਸੀਂ ਨਿਸ਼ਚਤ ਤੌਰ 'ਤੇ ਪੂਰੀ ਤਰ੍ਹਾਂ ਗੈਰ-ਵਿਰੋਧੀ ਲੋਕਾਂ ਨੂੰ ਛੱਡ ਦਿਓਗੇ, ਤੁਹਾਨੂੰ ਦੋ ਸੌ ਲੋਕਾਂ ਵਿੱਚੋਂ ਦਸ ਦੇ ਆਕਾਰ ਦੇ ਸਾਰੇ ਉਪ ਸਮੂਹਾਂ ਵਿੱਚੋਂ ਲੰਘਣ ਦੀ ਲੋੜ ਹੈ। ਲਗਭਗ ਹਨ , ਅਤੇ ਓਪਰੇਸ਼ਨਾਂ ਦੀ ਇਹ ਗਿਣਤੀ ਪਹਿਲਾਂ ਹੀ ਕਲੱਸਟਰ 'ਤੇ ਛਾਂਟੀ ਜਾ ਸਕਦੀ ਹੈ।

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

ਅਸਲ ਵਿੱਚ, ਸਧਾਰਨ ਤਰਕ ਨਾਲ ਤੁਸੀਂ ਹੋਰ ਵੀ ਆਕਰਸ਼ਕ ਸਥਿਤੀਆਂ ਪ੍ਰਾਪਤ ਕਰ ਸਕਦੇ ਹੋ। ਨੋਟ ਕਰੋ ਕਿ ਸਾਨੂੰ ਯਕੀਨੀ ਤੌਰ 'ਤੇ ਸਾਰੇ ਵਿਵਾਦਾਂ ਨੂੰ ਸੁਲਝਾਉਣ ਦੀ ਲੋੜ ਹੈ, ਭਾਵ, ਹਰੇਕ ਵਿਵਾਦਪੂਰਨ ਜੋੜੇ ਵਿੱਚੋਂ, ਘੱਟੋ-ਘੱਟ ਇੱਕ ਵਿਅਕਤੀ ਨੂੰ ਚੁਣੋ ਜਿਸ ਨੂੰ ਅਸੀਂ ਅੰਦਰ ਨਹੀਂ ਆਉਣ ਦੇਵਾਂਗੇ। ਆਓ ਹੇਠਾਂ ਦਿੱਤੇ ਐਲਗੋਰਿਦਮ 'ਤੇ ਵਿਚਾਰ ਕਰੀਏ: ਕੋਈ ਵੀ ਵਿਵਾਦ ਲਓ, ਜਿਸ ਤੋਂ ਅਸੀਂ ਇੱਕ ਭਾਗੀਦਾਰ ਨੂੰ ਹਟਾਉਂਦੇ ਹਾਂ ਅਤੇ ਬਾਕੀ ਬਚੇ ਤੋਂ ਆਵਰਤੀ ਤੌਰ 'ਤੇ ਸ਼ੁਰੂ ਕਰਦੇ ਹਾਂ, ਫਿਰ ਦੂਜੇ ਨੂੰ ਹਟਾਉਂਦੇ ਹਾਂ ਅਤੇ ਦੁਬਾਰਾ ਸ਼ੁਰੂ ਕਰਦੇ ਹਾਂ। ਕਿਉਂਕਿ ਅਸੀਂ ਹਰ ਕਦਮ 'ਤੇ ਕਿਸੇ ਨੂੰ ਬਾਹਰ ਸੁੱਟ ਦਿੰਦੇ ਹਾਂ, ਅਜਿਹੇ ਐਲਗੋਰਿਦਮ ਦਾ ਰੀਕਰਸ਼ਨ ਟ੍ਰੀ ਡੂੰਘਾਈ ਦਾ ਇੱਕ ਬਾਈਨਰੀ ਟ੍ਰੀ ਹੈ k, ਇਸ ਲਈ ਕੁੱਲ ਮਿਲਾ ਕੇ ਐਲਗੋਰਿਦਮ ਕੰਮ ਕਰਦਾ ਹੈ ਕਿੱਥੇ n ਸਿਰਲੇਖਾਂ ਦੀ ਗਿਣਤੀ ਹੈ, ਅਤੇ m - ਪਸਲੀਆਂ ਦੀ ਗਿਣਤੀ. ਸਾਡੀ ਉਦਾਹਰਨ ਵਿੱਚ, ਇਹ ਲਗਭਗ XNUMX ਮਿਲੀਅਨ ਹੈ, ਜੋ ਕਿ ਇੱਕ ਲੈਪਟਾਪ 'ਤੇ ਹੀ ਨਹੀਂ, ਸਗੋਂ ਇੱਕ ਮੋਬਾਈਲ ਫੋਨ 'ਤੇ ਵੀ ਇੱਕ ਸਪਲਿਟ ਸਕਿੰਟ ਵਿੱਚ ਗਿਣਿਆ ਜਾ ਸਕਦਾ ਹੈ।

ਉਪਰੋਕਤ ਉਦਾਹਰਣ ਇੱਕ ਉਦਾਹਰਣ ਹੈ ਪੈਰਾਮੀਟਰਾਈਜ਼ਡ ਐਲਗੋਰਿਦਮ. ਪੈਰਾਮੀਟਰਾਈਜ਼ਡ ਐਲਗੋਰਿਦਮ ਉਹ ਐਲਗੋਰਿਦਮ ਹਨ ਜੋ ਸਮੇਂ ਦੇ ਨਾਲ ਚੱਲਦੇ ਹਨ f(k) ਪੌਲੀ(n)ਕਿੱਥੇ p - ਬਹੁਪਦ, f ਇੱਕ ਆਰਬਿਟਰਰੀ ਕੰਪਿਊਟੇਬਲ ਫੰਕਸ਼ਨ ਹੈ, ਅਤੇ k - ਕੁਝ ਪੈਰਾਮੀਟਰ, ਜੋ ਕਿ, ਸੰਭਵ ਤੌਰ 'ਤੇ, ਸਮੱਸਿਆ ਦੇ ਆਕਾਰ ਤੋਂ ਬਹੁਤ ਛੋਟਾ ਹੋਵੇਗਾ।

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

ਗਤੀ ਚੁਣੌਤੀ

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

ਮੁਕਾਬਲਾ ਹਰ ਸਾਲ ਪ੍ਰਸਿੱਧੀ ਪ੍ਰਾਪਤ ਕਰ ਰਿਹਾ ਹੈ. ਜੇ ਤੁਸੀਂ ਸ਼ੁਰੂਆਤੀ ਅੰਕੜਿਆਂ 'ਤੇ ਵਿਸ਼ਵਾਸ ਕਰਦੇ ਹੋ, ਤਾਂ ਇਸ ਸਾਲ 24 ਟੀਮਾਂ ਨੇ ਇਕੱਲੇ ਸਿਰੇ ਨੂੰ ਕਵਰ ਕਰਨ ਦੀ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਮੁਕਾਬਲੇ ਵਿਚ ਹਿੱਸਾ ਲਿਆ। ਇਹ ਧਿਆਨ ਦੇਣ ਯੋਗ ਹੈ ਕਿ ਮੁਕਾਬਲਾ ਕਈ ਘੰਟੇ ਜਾਂ ਇੱਕ ਹਫ਼ਤੇ ਤੱਕ ਨਹੀਂ, ਸਗੋਂ ਕਈ ਮਹੀਨਿਆਂ ਤੱਕ ਚੱਲਦਾ ਹੈ। ਟੀਮਾਂ ਨੂੰ ਸਾਹਿਤ ਦਾ ਅਧਿਐਨ ਕਰਨ ਦਾ ਮੌਕਾ ਮਿਲਦਾ ਹੈ, ਆਪਣੇ ਖੁਦ ਦੇ ਮੂਲ ਵਿਚਾਰ ਨਾਲ ਆਉਣਾ ਅਤੇ ਇਸਨੂੰ ਲਾਗੂ ਕਰਨ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰਨੀ ਪੈਂਦੀ ਹੈ। ਸੰਖੇਪ ਰੂਪ ਵਿੱਚ, ਇਹ ਮੁਕਾਬਲਾ ਇੱਕ ਖੋਜ ਪ੍ਰੋਜੈਕਟ ਹੈ. ਸਭ ਤੋਂ ਪ੍ਰਭਾਵਸ਼ਾਲੀ ਹੱਲ ਅਤੇ ਜੇਤੂਆਂ ਨੂੰ ਇਨਾਮ ਦੇਣ ਲਈ ਵਿਚਾਰ ਕਾਨਫਰੰਸ ਦੇ ਨਾਲ ਮਿਲ ਕੇ ਰੱਖੇ ਜਾਣਗੇ ਆਈ ਪੀ ਈ ਸੀ ਯੂਰਪ ਵਿੱਚ ਸਭ ਤੋਂ ਵੱਡੀ ਸਾਲਾਨਾ ਐਲਗੋਰਿਦਮਿਕ ਮੀਟਿੰਗ ਦੇ ਹਿੱਸੇ ਵਜੋਂ (ਪੈਰਾਮੀਟਰਾਈਜ਼ਡ ਐਂਡ ਐਕਸਕਟ ਕੰਪਿਊਟੇਸ਼ਨ ਉੱਤੇ ਅੰਤਰਰਾਸ਼ਟਰੀ ਸਿੰਪੋਜ਼ੀਅਮ) algo. ਮੁਕਾਬਲੇ ਬਾਰੇ ਵਧੇਰੇ ਵਿਸਤ੍ਰਿਤ ਜਾਣਕਾਰੀ ਖੁਦ 'ਤੇ ਪਾਈ ਜਾ ਸਕਦੀ ਹੈ ਸਾਈਟ, ਅਤੇ ਪਿਛਲੇ ਸਾਲਾਂ ਦੇ ਨਤੀਜੇ ਝੂਠ ਹਨ ਇੱਥੇ.

ਹੱਲ ਚਿੱਤਰ

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

ਆਮ ਸਕੀਮ ਇਹ ਹੈ: ਅਸੀਂ ਸਰਲੀਕਰਨ ਨਿਯਮਾਂ ਨੂੰ ਲਾਗੂ ਕਰਦੇ ਹਾਂ, ਫਿਰ ਅਸੀਂ ਕੁਝ ਸਿਰਲੇਖ ਚੁਣਦੇ ਹਾਂ, ਅਤੇ ਦੋ ਵਾਰ-ਵਾਰ ਕਾਲ ਕਰਦੇ ਹਾਂ: ਪਹਿਲਾਂ ਅਸੀਂ ਇਸਨੂੰ ਜਵਾਬ ਵਿੱਚ ਲੈਂਦੇ ਹਾਂ, ਅਤੇ ਦੂਜੇ ਵਿੱਚ ਅਸੀਂ ਇਸਦੇ ਸਾਰੇ ਗੁਆਂਢੀਆਂ ਨੂੰ ਲੈਂਦੇ ਹਾਂ। ਇਸ ਨੂੰ ਅਸੀਂ ਇਸ ਸਿਰਲੇਖ ਦੇ ਨਾਲ ਸਪਲਿਟਿੰਗ (ਸ਼ਾਖਾਬੰਦੀ) ਕਹਿੰਦੇ ਹਾਂ।

ਅਗਲੇ ਪੈਰੇ ਵਿੱਚ ਇਸ ਸਕੀਮ ਵਿੱਚ ਬਿਲਕੁਲ ਇੱਕ ਵਾਧਾ ਕੀਤਾ ਜਾਵੇਗਾ।

ਵੰਡਣ (ਬ੍ਰੰਚਿੰਗ) ਨਿਯਮਾਂ ਲਈ ਵਿਚਾਰ

ਆਉ ਇਸ ਬਾਰੇ ਚਰਚਾ ਕਰੀਏ ਕਿ ਇੱਕ ਸਿਖਰ ਦੀ ਚੋਣ ਕਿਵੇਂ ਕਰੀਏ ਜਿਸ ਦੇ ਨਾਲ ਵਿਭਾਜਨ ਹੋਵੇਗਾ।
ਮੁੱਖ ਵਿਚਾਰ ਐਲਗੋਰਿਦਮਿਕ ਅਰਥਾਂ ਵਿੱਚ ਬਹੁਤ ਲਾਲਚੀ ਹੈ: ਆਓ ਵੱਧ ਤੋਂ ਵੱਧ ਡਿਗਰੀ ਦਾ ਇੱਕ ਸਿਰਾ ਕਰੀਏ ਅਤੇ ਇਸਦੇ ਨਾਲ ਵੰਡੀਏ। ਇਹ ਬਿਹਤਰ ਕਿਉਂ ਲੱਗਦਾ ਹੈ? ਕਿਉਂਕਿ ਰਿਕਰਸਿਵ ਕਾਲ ਦੀ ਦੂਜੀ ਬ੍ਰਾਂਚ ਵਿੱਚ ਅਸੀਂ ਇਸ ਤਰੀਕੇ ਨਾਲ ਬਹੁਤ ਸਾਰੇ ਸਿਰਲੇਖਾਂ ਨੂੰ ਹਟਾ ਦੇਵਾਂਗੇ। ਤੁਸੀਂ ਬਚੇ ਹੋਏ ਇੱਕ ਛੋਟੇ ਗ੍ਰਾਫ਼ 'ਤੇ ਭਰੋਸਾ ਕਰ ਸਕਦੇ ਹੋ ਅਤੇ ਅਸੀਂ ਇਸ 'ਤੇ ਤੇਜ਼ੀ ਨਾਲ ਕੰਮ ਕਰ ਸਕਦੇ ਹਾਂ।

ਇਹ ਪਹੁੰਚ, ਪਹਿਲਾਂ ਹੀ ਵਿਚਾਰੀਆਂ ਗਈਆਂ ਸਧਾਰਨ ਕਰਨਲਾਈਜ਼ੇਸ਼ਨ ਤਕਨੀਕਾਂ ਦੇ ਨਾਲ, ਆਪਣੇ ਆਪ ਨੂੰ ਚੰਗੀ ਤਰ੍ਹਾਂ ਦਰਸਾਉਂਦੀ ਹੈ ਅਤੇ ਆਕਾਰ ਵਿੱਚ ਕਈ ਹਜ਼ਾਰ ਕੋਣਾਂ ਦੇ ਕੁਝ ਟੈਸਟਾਂ ਨੂੰ ਹੱਲ ਕਰਦੀ ਹੈ। ਪਰ, ਉਦਾਹਰਨ ਲਈ, ਇਹ ਕਿਊਬਿਕ ਗ੍ਰਾਫਾਂ ਲਈ ਚੰਗੀ ਤਰ੍ਹਾਂ ਕੰਮ ਨਹੀਂ ਕਰਦਾ ਹੈ (ਅਰਥਾਤ, ਉਹ ਗ੍ਰਾਫ ਜਿਨ੍ਹਾਂ ਦੇ ਹਰੇਕ ਸਿਰੇ ਦੀ ਡਿਗਰੀ ਤਿੰਨ ਹੈ)।
ਇੱਕ ਕਾਫ਼ੀ ਸਧਾਰਨ ਵਿਚਾਰ 'ਤੇ ਆਧਾਰਿਤ ਇੱਕ ਹੋਰ ਵਿਚਾਰ ਹੈ: ਜੇਕਰ ਗ੍ਰਾਫ ਡਿਸਕਨੈਕਟ ਕੀਤਾ ਗਿਆ ਹੈ, ਤਾਂ ਇਸਦੇ ਜੁੜੇ ਭਾਗਾਂ 'ਤੇ ਸਮੱਸਿਆ ਨੂੰ ਸੁਤੰਤਰ ਰੂਪ ਵਿੱਚ ਹੱਲ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਅੰਤ ਵਿੱਚ ਜਵਾਬਾਂ ਨੂੰ ਮਿਲਾ ਕੇ। ਇਹ, ਤਰੀਕੇ ਨਾਲ, ਸਕੀਮ ਵਿੱਚ ਇੱਕ ਛੋਟਾ ਵਾਅਦਾ ਕੀਤਾ ਸੋਧ ਹੈ, ਜੋ ਕਿ ਹੱਲ ਨੂੰ ਮਹੱਤਵਪੂਰਨ ਤੌਰ 'ਤੇ ਤੇਜ਼ ਕਰੇਗਾ: ਪਹਿਲਾਂ, ਇਸ ਕੇਸ ਵਿੱਚ, ਅਸੀਂ ਭਾਗਾਂ ਦੇ ਜਵਾਬਾਂ ਦੀ ਗਣਨਾ ਕਰਨ ਲਈ ਸਮੇਂ ਦੇ ਉਤਪਾਦ ਲਈ ਕੰਮ ਕੀਤਾ ਸੀ, ਪਰ ਹੁਣ ਅਸੀਂ ਇਸ ਲਈ ਕੰਮ ਕਰਦੇ ਹਾਂ। ਜੋੜ ਅਤੇ ਬ੍ਰਾਂਚਿੰਗ ਨੂੰ ਤੇਜ਼ ਕਰਨ ਲਈ, ਤੁਹਾਨੂੰ ਇੱਕ ਕਨੈਕਟ ਕੀਤੇ ਗ੍ਰਾਫ ਨੂੰ ਇੱਕ ਡਿਸਕਨੈਕਟ ਵਿੱਚ ਬਦਲਣ ਦੀ ਲੋੜ ਹੈ।

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

ਜਦੋਂ ਕਿਸੇ ਵੀ ਚੁਣੇ ਹੋਏ ਸਿਰਲੇਖ ਨੂੰ ਹਟਾ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ, ਤਾਂ ਗ੍ਰਾਫ ਕਨੈਕਟ ਕੀਤੇ ਭਾਗਾਂ ਵਿੱਚ ਵੰਡਿਆ ਜਾਵੇਗਾ।

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

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

ਮੈਂ ਬੇਤਰਤੀਬ ਸਿਰਲੇਖਾਂ ਦੇ ਜੋੜਿਆਂ ਦੇ ਵਿਚਕਾਰ ਕੱਟਾਂ ਨੂੰ ਲੱਭਣ ਅਤੇ ਸਭ ਤੋਂ ਸੰਤੁਲਿਤ ਇੱਕ ਲੈਣ ਲਈ ਕਈ ਵਾਰ ਕੋਸ਼ਿਸ਼ ਕੀਤੀ। ਬਦਕਿਸਮਤੀ ਨਾਲ, ਇਸ ਨਾਲ ਓਪਨ PACE ਚੈਲੇਂਜ ਟੈਸਟਿੰਗ ਵਿੱਚ ਮਾੜੇ ਨਤੀਜੇ ਨਿਕਲੇ। ਮੈਂ ਇਸਦੀ ਤੁਲਨਾ ਇੱਕ ਐਲਗੋਰਿਦਮ ਨਾਲ ਕੀਤੀ ਜੋ ਵੱਧ ਤੋਂ ਵੱਧ ਡਿਗਰੀ ਦੇ ਸਿਰਿਆਂ ਨੂੰ ਵੰਡਦਾ ਹੈ, ਉਹਨਾਂ ਨੂੰ ਉਤਰਨ ਦੀ ਡੂੰਘਾਈ 'ਤੇ ਸੀਮਾ ਦੇ ਨਾਲ ਚਲਾਉਂਦਾ ਹੈ। ਇੱਕ ਐਲਗੋਰਿਦਮ ਇਸ ਤਰੀਕੇ ਨਾਲ ਇੱਕ ਕੱਟ ਲੱਭਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰ ਰਿਹਾ ਹੈ ਜੋ ਵੱਡੇ ਗ੍ਰਾਫਾਂ ਨੂੰ ਪਿੱਛੇ ਛੱਡਦਾ ਹੈ। ਇਹ ਇਸ ਤੱਥ ਦੇ ਕਾਰਨ ਹੈ ਕਿ ਕਟੌਤੀ ਬਹੁਤ ਅਸੰਤੁਲਿਤ ਹੋ ਗਈ ਹੈ: 5-10 ਸਿਰਲੇਖਾਂ ਨੂੰ ਹਟਾਉਣ ਤੋਂ ਬਾਅਦ, ਸਿਰਫ 15-20 ਨੂੰ ਵੰਡਣਾ ਸੰਭਵ ਸੀ.

ਇਹ ਧਿਆਨ ਦੇਣ ਯੋਗ ਹੈ ਕਿ ਸਿਧਾਂਤਕ ਤੌਰ 'ਤੇ ਸਭ ਤੋਂ ਤੇਜ਼ ਐਲਗੋਰਿਦਮ ਬਾਰੇ ਲੇਖ ਵਿਭਾਜਨ ਲਈ ਸਿਰਿਆਂ ਦੀ ਚੋਣ ਕਰਨ ਲਈ ਬਹੁਤ ਜ਼ਿਆਦਾ ਉੱਨਤ ਤਕਨੀਕਾਂ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਨ। ਅਜਿਹੀਆਂ ਤਕਨੀਕਾਂ ਵਿੱਚ ਬਹੁਤ ਗੁੰਝਲਦਾਰ ਲਾਗੂ ਹੁੰਦਾ ਹੈ ਅਤੇ ਸਮੇਂ ਅਤੇ ਯਾਦਦਾਸ਼ਤ ਦੇ ਮਾਮਲੇ ਵਿੱਚ ਅਕਸਰ ਮਾੜੀ ਕਾਰਗੁਜ਼ਾਰੀ ਹੁੰਦੀ ਹੈ। ਮੈਂ ਉਹਨਾਂ ਦੀ ਪਛਾਣ ਕਰਨ ਵਿੱਚ ਅਸਮਰੱਥ ਸੀ ਜੋ ਅਭਿਆਸ ਲਈ ਕਾਫ਼ੀ ਸਵੀਕਾਰਯੋਗ ਹਨ।

ਸਰਲੀਕਰਨ ਨਿਯਮਾਂ ਨੂੰ ਕਿਵੇਂ ਲਾਗੂ ਕਰਨਾ ਹੈ

ਸਾਡੇ ਕੋਲ ਪਹਿਲਾਂ ਹੀ ਕਰਨਲਾਈਜ਼ੇਸ਼ਨ ਲਈ ਵਿਚਾਰ ਹਨ। ਮੈਨੂੰ ਤੁਹਾਨੂੰ ਯਾਦ ਦਿਵਾਉਣ ਦਿਓ:

1. ਜੇਕਰ ਕੋਈ ਅਲੱਗ-ਥਲੱਗ ਹੈ, ਤਾਂ ਇਸਨੂੰ ਮਿਟਾਓ।
2. ਜੇ ਡਿਗਰੀ 1 ਦਾ ਇੱਕ ਸਿਰਾ ਹੈ, ਤਾਂ ਇਸਨੂੰ ਹਟਾਓ ਅਤੇ ਜਵਾਬ ਵਿੱਚ ਇਸਦੇ ਗੁਆਂਢੀ ਨੂੰ ਲਓ।
3. ਜੇਕਰ ਘੱਟੋ-ਘੱਟ ਡਿਗਰੀ ਦਾ ਇੱਕ ਸਿਰਾ ਹੋਵੇ k+1, ਇਸਨੂੰ ਵਾਪਸ ਲੈ ਜਾਓ।

ਪਹਿਲੇ ਦੋ ਨਾਲ ਸਭ ਕੁਝ ਸਪੱਸ਼ਟ ਹੈ, ਤੀਜੇ ਦੇ ਨਾਲ ਇੱਕ ਚਾਲ ਹੈ. ਜੇਕਰ ਇੱਕ ਬਾਰ ਬਾਰੇ ਇੱਕ ਕਾਮਿਕ ਸਮੱਸਿਆ ਵਿੱਚ ਸਾਨੂੰ ਦੀ ਇੱਕ ਉਪਰਲੀ ਸੀਮਾ ਦਿੱਤੀ ਗਈ ਸੀ k, ਫਿਰ PACE ਚੈਲੇਂਜ ਵਿੱਚ ਤੁਹਾਨੂੰ ਘੱਟੋ-ਘੱਟ ਆਕਾਰ ਦਾ ਇੱਕ ਸਿਰਲੇਖ ਕਵਰ ਲੱਭਣ ਦੀ ਲੋੜ ਹੈ। ਇਹ ਖੋਜ ਸਮੱਸਿਆਵਾਂ ਦਾ ਨਿਰਣਾਇਕ ਸਮੱਸਿਆਵਾਂ ਵਿੱਚ ਇੱਕ ਆਮ ਤਬਦੀਲੀ ਹੈ; ਅਕਸਰ ਦੋ ਕਿਸਮਾਂ ਦੀਆਂ ਸਮੱਸਿਆਵਾਂ ਵਿੱਚ ਕੋਈ ਅੰਤਰ ਨਹੀਂ ਹੁੰਦਾ ਹੈ। ਅਭਿਆਸ ਵਿੱਚ, ਜੇਕਰ ਅਸੀਂ ਸਿਰਲੇਖ ਨੂੰ ਕਵਰ ਕਰਨ ਵਾਲੀ ਸਮੱਸਿਆ ਲਈ ਇੱਕ ਹੱਲ ਕਰਨ ਵਾਲਾ ਲਿਖ ਰਹੇ ਹਾਂ, ਤਾਂ ਇੱਕ ਅੰਤਰ ਹੋ ਸਕਦਾ ਹੈ। ਉਦਾਹਰਨ ਲਈ, ਤੀਜੇ ਬਿੰਦੂ ਦੇ ਰੂਪ ਵਿੱਚ.

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

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

ਕਈ ਰਾਤ ਦੇ ਪ੍ਰਯੋਗਾਂ ਦਾ ਸੰਚਾਲਨ ਕਰਨ ਤੋਂ ਬਾਅਦ, ਮੈਂ ਇਹਨਾਂ ਦੋ ਤਰੀਕਿਆਂ ਦੇ ਸੁਮੇਲ 'ਤੇ ਸੈਟਲ ਹੋ ਗਿਆ: ਪਹਿਲਾਂ, ਮੈਂ ਖੋਜ ਡੂੰਘਾਈ 'ਤੇ ਕਿਸੇ ਕਿਸਮ ਦੀ ਸੀਮਾ ਦੇ ਨਾਲ ਆਪਣੇ ਐਲਗੋਰਿਦਮ ਨੂੰ ਚਲਾਉਂਦਾ ਹਾਂ (ਇਸ ਨੂੰ ਚੁਣਨਾ ਤਾਂ ਜੋ ਇਹ ਮੁੱਖ ਹੱਲ ਦੇ ਮੁਕਾਬਲੇ ਬਹੁਤ ਘੱਟ ਸਮਾਂ ਲਵੇ) ਅਤੇ ਸਭ ਤੋਂ ਵਧੀਆ ਵਰਤੋਂ ਹੱਲ ਉੱਤਰ ਦੀ ਉਪਰਲੀ ਸੀਮਾ ਦੇ ਰੂਪ ਵਿੱਚ ਲੱਭਿਆ ਗਿਆ ਹੈ - ਅਰਥਾਤ, ਉਸੇ ਚੀਜ਼ ਲਈ k.

ਡਿਗਰੀ 2 ਦੇ ਸਿਰਲੇਖ

ਅਸੀਂ ਡਿਗਰੀ 0 ਅਤੇ 1 ਦੇ ਸਿਰਲੇਖਾਂ ਨਾਲ ਨਜਿੱਠਿਆ ਹੈ। ਇਹ ਪਤਾ ਚਲਦਾ ਹੈ ਕਿ ਇਹ ਡਿਗਰੀ 2 ਦੇ ਸਿਰਿਆਂ ਨਾਲ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਪਰ ਇਸ ਲਈ ਗ੍ਰਾਫ ਤੋਂ ਵਧੇਰੇ ਗੁੰਝਲਦਾਰ ਕਾਰਵਾਈਆਂ ਦੀ ਲੋੜ ਪਵੇਗੀ।

ਇਸ ਦੀ ਵਿਆਖਿਆ ਕਰਨ ਲਈ, ਸਾਨੂੰ ਕਿਸੇ ਤਰ੍ਹਾਂ ਨਾਲ ਕੋਨਾਵਾਂ ਨੂੰ ਮਨੋਨੀਤ ਕਰਨ ਦੀ ਲੋੜ ਹੈ। ਆਉ ਡਿਗਰੀ 2 ਦੇ ਇੱਕ ਸਿਖਰ ਨੂੰ ਇੱਕ ਸਿਖਰ ਕਹਿੰਦੇ ਹਾਂ v, ਅਤੇ ਇਸਦੇ ਗੁਆਂਢੀ - ਸਿਰਲੇਖ x и y. ਅੱਗੇ ਸਾਡੇ ਕੋਲ ਦੋ ਕੇਸ ਹੋਣਗੇ।

1. ਕਦੋਂ x и y - ਗੁਆਂਢੀ। ਫਿਰ ਤੁਸੀਂ ਜਵਾਬ ਦੇ ਸਕਦੇ ਹੋ x и yਅਤੇ v ਮਿਟਾਓ. ਦਰਅਸਲ, ਇਸ ਤਿਕੋਣ ਤੋਂ ਬਦਲੇ ਵਿੱਚ ਘੱਟੋ-ਘੱਟ ਦੋ ਸਿਰਲੇਖ ਲੈਣ ਦੀ ਲੋੜ ਹੈ, ਅਤੇ ਜੇਕਰ ਅਸੀਂ ਲੈਂਦੇ ਹਾਂ ਤਾਂ ਅਸੀਂ ਯਕੀਨੀ ਤੌਰ 'ਤੇ ਨਹੀਂ ਗੁਆਵਾਂਗੇ x и y: ਉਹਨਾਂ ਦੇ ਸ਼ਾਇਦ ਹੋਰ ਗੁਆਂਢੀ ਹਨ, ਅਤੇ v ਉਹ ਇੱਥੇ ਨਹੀਂ ਹਨ।
2. ਕਦੋਂ x и y - ਗੁਆਂਢੀ ਨਹੀਂ। ਫਿਰ ਇਹ ਦੱਸਿਆ ਗਿਆ ਹੈ ਕਿ ਸਾਰੇ ਤਿੰਨ ਸਿਰਿਆਂ ਨੂੰ ਇੱਕ ਵਿੱਚ ਚਿਪਕਾਇਆ ਜਾ ਸਕਦਾ ਹੈ। ਵਿਚਾਰ ਇਹ ਹੈ ਕਿ ਇਸ ਕੇਸ ਵਿੱਚ ਇੱਕ ਅਨੁਕੂਲ ਜਵਾਬ ਹੈ, ਜਿਸ ਵਿੱਚ ਅਸੀਂ ਜਾਂ ਤਾਂ ਲੈਂਦੇ ਹਾਂ v, ਜਾਂ ਦੋਵੇਂ ਸਿਰਲੇਖ x и y. ਇਸ ਤੋਂ ਇਲਾਵਾ, ਪਹਿਲੇ ਮਾਮਲੇ ਵਿਚ ਸਾਨੂੰ ਜਵਾਬ ਵਿਚ ਸਾਰੇ ਗੁਆਂਢੀਆਂ ਨੂੰ ਲੈਣਾ ਹੋਵੇਗਾ x и y, ਪਰ ਦੂਜੇ ਵਿੱਚ ਇਹ ਜ਼ਰੂਰੀ ਨਹੀਂ ਹੈ। ਇਹ ਉਹਨਾਂ ਮਾਮਲਿਆਂ ਨਾਲ ਬਿਲਕੁਲ ਮੇਲ ਖਾਂਦਾ ਹੈ ਜਦੋਂ ਅਸੀਂ ਜਵਾਬ ਵਿੱਚ ਗੂੰਦ ਵਾਲੇ ਸਿਰੇ ਨੂੰ ਨਹੀਂ ਲੈਂਦੇ ਅਤੇ ਜਦੋਂ ਅਸੀਂ ਕਰਦੇ ਹਾਂ। ਇਹ ਸਿਰਫ ਨੋਟ ਕਰਨ ਲਈ ਰਹਿੰਦਾ ਹੈ ਕਿ ਦੋਵਾਂ ਮਾਮਲਿਆਂ ਵਿੱਚ ਅਜਿਹੇ ਓਪਰੇਸ਼ਨ ਤੋਂ ਪ੍ਰਤੀਕ੍ਰਿਆ ਇੱਕ ਘਟ ਜਾਂਦੀ ਹੈ.

ਇਹ ਧਿਆਨ ਦੇਣ ਯੋਗ ਹੈ ਕਿ ਇਸ ਪਹੁੰਚ ਨੂੰ ਨਿਰਪੱਖ ਰੇਖਿਕ ਸਮੇਂ ਵਿੱਚ ਸਹੀ ਢੰਗ ਨਾਲ ਲਾਗੂ ਕਰਨਾ ਬਹੁਤ ਮੁਸ਼ਕਲ ਹੈ. ਗਲੂਇੰਗ ਵਰਟੀਸਿਜ਼ ਇੱਕ ਗੁੰਝਲਦਾਰ ਕਾਰਵਾਈ ਹੈ; ਤੁਹਾਨੂੰ ਗੁਆਂਢੀਆਂ ਦੀਆਂ ਸੂਚੀਆਂ ਦੀ ਨਕਲ ਕਰਨ ਦੀ ਲੋੜ ਹੈ। ਜੇ ਇਹ ਲਾਪਰਵਾਹੀ ਨਾਲ ਕੀਤਾ ਜਾਂਦਾ ਹੈ, ਤਾਂ ਤੁਸੀਂ ਅਸੈਂਪਟੋਟਿਕ ਤੌਰ 'ਤੇ ਸਬ-ਅਪਟੀਮਲ ਰਨਿੰਗ ਟਾਈਮ (ਉਦਾਹਰਨ ਲਈ, ਜੇ ਤੁਸੀਂ ਹਰੇਕ ਗਲੂਇੰਗ ਤੋਂ ਬਾਅਦ ਬਹੁਤ ਸਾਰੇ ਕਿਨਾਰਿਆਂ ਦੀ ਨਕਲ ਕਰਦੇ ਹੋ) ਨਾਲ ਖਤਮ ਹੋ ਸਕਦੇ ਹੋ। ਮੈਂ ਡਿਗਰੀ 2 ਦੇ ਸਿਰਿਆਂ ਤੋਂ ਪੂਰੇ ਮਾਰਗਾਂ ਨੂੰ ਲੱਭਣ ਅਤੇ ਵਿਸ਼ੇਸ਼ ਕੇਸਾਂ ਦੇ ਇੱਕ ਸਮੂਹ ਦਾ ਵਿਸ਼ਲੇਸ਼ਣ ਕਰਨ 'ਤੇ ਸੈਟਲ ਹੋ ਗਿਆ, ਜਿਵੇਂ ਕਿ ਅਜਿਹੇ ਸਿਰਲੇਖਾਂ ਤੋਂ ਚੱਕਰ ਜਾਂ ਇੱਕ ਨੂੰ ਛੱਡ ਕੇ ਅਜਿਹੇ ਸਾਰੇ ਸਿਖਰਾਂ ਤੋਂ।

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

ਰੇਖਿਕ ਕਰਨਲ

ਅੰਤ ਵਿੱਚ, ਕਰਨਲ ਦਾ ਸਭ ਤੋਂ ਦਿਲਚਸਪ ਹਿੱਸਾ.

ਸ਼ੁਰੂ ਕਰਨ ਲਈ, ਯਾਦ ਕਰੋ ਕਿ ਦੋ-ਪੱਖੀ ਗ੍ਰਾਫਾਂ ਵਿੱਚ ਘੱਟੋ-ਘੱਟ ਸਿਰਲੇਖ ਕਵਰ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਲੱਭਿਆ ਜਾ ਸਕਦਾ ਹੈ . ਅਜਿਹਾ ਕਰਨ ਲਈ ਤੁਹਾਨੂੰ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰਨ ਦੀ ਲੋੜ ਹੈ ਹੋਪਕ੍ਰਾਫਟ-ਕਾਰਪ ਉੱਥੇ ਅਧਿਕਤਮ ਮੇਲ ਲੱਭਣ ਲਈ, ਅਤੇ ਫਿਰ ਪ੍ਰਮੇਏ ਦੀ ਵਰਤੋਂ ਕਰੋ ਕੋਨਿਗ-ਏਗਰਵਰੀ.

ਇੱਕ ਲੀਨੀਅਰ ਕਰਨਲ ਦਾ ਵਿਚਾਰ ਇਹ ਹੈ: ਪਹਿਲਾਂ ਅਸੀਂ ਗ੍ਰਾਫ ਨੂੰ ਵੰਡਦੇ ਹਾਂ, ਅਰਥਾਤ, ਹਰੇਕ ਸਿਰਲੇਖ ਦੀ ਬਜਾਏ v ਆਉ ਦੋ ਸਿਖਰ ਜੋੜੀਏ и , ਅਤੇ ਹਰੇਕ ਕਿਨਾਰੇ ਦੀ ਬਜਾਏ u - v ਆਓ ਦੋ ਪਸਲੀਆਂ ਜੋੜੀਏ и . ਨਤੀਜਾ ਗ੍ਰਾਫ ਦੋ-ਪੱਖੀ ਹੋਵੇਗਾ। ਆਓ ਇਸ ਵਿੱਚ ਘੱਟੋ-ਘੱਟ ਸਿਰੇ ਦਾ ਕਵਰ ਲੱਭੀਏ। ਮੂਲ ਗ੍ਰਾਫ਼ ਦੇ ਕੁਝ ਸਿਰੇ ਦੋ ਵਾਰ, ਕੁਝ ਸਿਰਫ਼ ਇੱਕ ਵਾਰ, ਅਤੇ ਕੁਝ ਕਦੇ ਨਹੀਂ ਮਿਲਣਗੇ। ਨੇਮਹਾਊਜ਼ਰ-ਟ੍ਰੋਟਰ ਥਿਊਰਮ ਦੱਸਦਾ ਹੈ ਕਿ ਇਸ ਸਥਿਤੀ ਵਿੱਚ ਕੋਈ ਵੀ ਉਹਨਾਂ ਸਿਰਲੇਖਾਂ ਨੂੰ ਹਟਾ ਸਕਦਾ ਹੈ ਜੋ ਇੱਕ ਵਾਰ ਵੀ ਨਹੀਂ ਹਿੱਟੇ ਅਤੇ ਉਹਨਾਂ ਨੂੰ ਵਾਪਸ ਲੈ ਸਕਦੇ ਹਨ ਜੋ ਦੋ ਵਾਰ ਹਿੱਟ ਹੋਏ ਹਨ। ਇਸ ਤੋਂ ਇਲਾਵਾ, ਉਹ ਕਹਿੰਦੀ ਹੈ ਕਿ ਬਾਕੀ ਬਚੇ ਸਿਰਿਆਂ ਵਿੱਚੋਂ (ਜਿਹੜੇ ਇੱਕ ਵਾਰ ਹਿੱਟ ਹੁੰਦੇ ਹਨ) ਤੁਹਾਨੂੰ ਜਵਾਬ ਵਜੋਂ ਘੱਟੋ-ਘੱਟ ਅੱਧੇ ਲੈਣ ਦੀ ਲੋੜ ਹੈ।

ਅਸੀਂ ਹੁਣੇ ਛੱਡਣਾ ਸਿੱਖਿਆ ਹੈ ਇਸ ਤੋਂ ਵੱਧ ਨਹੀਂ 2k ਸਿਖਰਾਂ ਵਾਸਤਵ ਵਿੱਚ, ਜੇਕਰ ਬਾਕੀ ਉੱਤਰ ਸਾਰੇ ਸਿਰਲੇਖਾਂ ਦਾ ਘੱਟੋ-ਘੱਟ ਅੱਧਾ ਹੈ, ਤਾਂ ਕੁੱਲ ਵਿੱਚ ਇਸ ਤੋਂ ਵੱਧ ਕੋਈ ਹੋਰ ਕੋਣ ਨਹੀਂ ਹਨ 2k.

ਇੱਥੇ ਮੈਂ ਇੱਕ ਛੋਟਾ ਜਿਹਾ ਕਦਮ ਅੱਗੇ ਵਧਾਉਣ ਦੇ ਯੋਗ ਸੀ। ਇਹ ਸਪੱਸ਼ਟ ਹੈ ਕਿ ਇਸ ਤਰੀਕੇ ਨਾਲ ਬਣਾਇਆ ਗਿਆ ਕਰਨਲ ਇਸ ਗੱਲ 'ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ ਕਿ ਅਸੀਂ ਬਾਇਪਾਰਟਾਈਟ ਗ੍ਰਾਫ ਵਿੱਚ ਕਿਸ ਕਿਸਮ ਦਾ ਨਿਊਨਤਮ ਵਰਟੈਕਸ ਕਵਰ ਲਿਆ ਹੈ। ਮੈਂ ਇੱਕ ਲੈਣਾ ਚਾਹਾਂਗਾ ਤਾਂ ਜੋ ਬਾਕੀ ਬਚੇ ਸਿਰਿਆਂ ਦੀ ਸੰਖਿਆ ਘੱਟ ਤੋਂ ਘੱਟ ਹੋਵੇ। ਪਹਿਲਾਂ, ਉਹ ਸਿਰਫ ਸਮੇਂ ਸਿਰ ਅਜਿਹਾ ਕਰਨ ਦੇ ਯੋਗ ਸਨ . ਮੈਂ ਸਮੇਂ ਵਿੱਚ ਇਸ ਐਲਗੋਰਿਦਮ ਨੂੰ ਲਾਗੂ ਕਰਨ ਦੇ ਨਾਲ ਆਇਆ ਹਾਂ , ਇਸ ਤਰ੍ਹਾਂ, ਇਸ ਕੋਰ ਨੂੰ ਹਰ ਬ੍ਰਾਂਚਿੰਗ ਪੜਾਅ 'ਤੇ ਸੈਂਕੜੇ ਹਜ਼ਾਰਾਂ ਸਿਰਲੇਖਾਂ ਦੇ ਗ੍ਰਾਫਾਂ ਵਿੱਚ ਖੋਜਿਆ ਜਾ ਸਕਦਾ ਹੈ।

ਇਸ ਦਾ ਨਤੀਜਾ

ਅਭਿਆਸ ਦਿਖਾਉਂਦਾ ਹੈ ਕਿ ਮੇਰਾ ਹੱਲ ਕਈ ਸੌ ਸਿਰਲੇਖਾਂ ਅਤੇ ਕਈ ਹਜ਼ਾਰ ਕਿਨਾਰਿਆਂ ਦੇ ਟੈਸਟਾਂ 'ਤੇ ਵਧੀਆ ਕੰਮ ਕਰਦਾ ਹੈ। ਅਜਿਹੇ ਟੈਸਟਾਂ ਵਿੱਚ ਇਹ ਆਸ ਕੀਤੀ ਜਾ ਸਕਦੀ ਹੈ ਕਿ ਅੱਧੇ ਘੰਟੇ ਵਿੱਚ ਕੋਈ ਹੱਲ ਲੱਭ ਲਿਆ ਜਾਵੇਗਾ। ਇੱਕ ਸਵੀਕਾਰਯੋਗ ਸਮੇਂ ਵਿੱਚ ਜਵਾਬ ਲੱਭਣ ਦੀ ਸੰਭਾਵਨਾ, ਸਿਧਾਂਤਕ ਤੌਰ 'ਤੇ, ਵਧ ਜਾਂਦੀ ਹੈ ਜੇਕਰ ਗ੍ਰਾਫ ਵਿੱਚ ਉੱਚ ਡਿਗਰੀ ਦੇ ਉੱਚ ਕੋਣ ਦੀ ਕਾਫੀ ਵੱਡੀ ਸੰਖਿਆ ਹੈ, ਉਦਾਹਰਨ ਲਈ, ਡਿਗਰੀ 10 ਅਤੇ ਉੱਚ।

ਪ੍ਰਤੀਯੋਗਿਤਾ ਵਿੱਚ ਭਾਗ ਲੈਣ ਲਈ ਹੱਲ ਨੂੰ ਭੇਜਣਾ ਪੈਂਦਾ ਸੀ optil.io. ਉਥੇ ਮੌਜੂਦ ਜਾਣਕਾਰੀ ਦੇ ਆਧਾਰ 'ਤੇ ਪ੍ਰੋ ਚਿੰਨ੍ਹ, ਓਪਨ ਟੈਸਟਾਂ ਵਿੱਚ ਮੇਰਾ ਹੱਲ ਦੂਜੇ ਤੋਂ ਵੱਡੇ ਅੰਤਰ ਦੇ ਨਾਲ, ਵੀਹ ਵਿੱਚੋਂ ਤੀਜੇ ਨੰਬਰ 'ਤੇ ਹੈ। ਪੂਰੀ ਤਰ੍ਹਾਂ ਈਮਾਨਦਾਰ ਹੋਣ ਲਈ, ਇਹ ਪੂਰੀ ਤਰ੍ਹਾਂ ਸਪੱਸ਼ਟ ਨਹੀਂ ਹੈ ਕਿ ਮੁਕਾਬਲੇ ਵਿੱਚ ਹੱਲਾਂ ਦਾ ਮੁਲਾਂਕਣ ਕਿਵੇਂ ਕੀਤਾ ਜਾਵੇਗਾ: ਉਦਾਹਰਨ ਲਈ, ਮੇਰਾ ਹੱਲ ਚੌਥੇ ਸਥਾਨ 'ਤੇ ਹੱਲ ਨਾਲੋਂ ਘੱਟ ਟੈਸਟ ਪਾਸ ਕਰਦਾ ਹੈ, ਪਰ ਜਿਹੜੇ ਪਾਸ ਹੁੰਦੇ ਹਨ, ਇਹ ਤੇਜ਼ੀ ਨਾਲ ਕੰਮ ਕਰਦਾ ਹੈ।

ਬੰਦ ਕੀਤੇ ਗਏ ਟੈਸਟਾਂ ਦੇ ਨਤੀਜੇ XNUMX ਜੁਲਾਈ ਨੂੰ ਜਾਣੇ ਜਾਣਗੇ।

ਸਰੋਤ: www.habr.com