Kruskal ਦੇ ਐਲਗੋਰਿਥਮ - ਇੱਕ ਅਨੁਕੂਲ ਫਰੇਮਵਰਕ ਦੀ ਉਸਾਰੀ

ਛੇਤੀ 19 ਸਦੀ geometer ਵਿਚ ਬਰ੍ਲਿਨ ਤੱਕ ਜੇਕਬ Steiner ਨੂੰ ਤਿੰਨ ਪਿੰਡ ਨਾਲ ਕੁਨੈਕਟ ਕਰਨ ਲਈ, ਜੋ ਕਿ ਇਸ ਨੂੰ ਆਪਣੇ ਲੰਬਾਈ ਛੋਟੀ ਸੀ ਦਾ ਕੰਮ ਸੈੱਟ ਕੀਤਾ. ਬਾਅਦ ਵਿਚ ਉਸ ਨੇ ਸਮੱਸਿਆ ਦਾ ਸਾਰ: ਇਸ ਨੂੰ ਇੱਕ ਜਹਾਜ਼ ਵਿੱਚ ਇੱਕ ਬਿੰਦੂ ਦਾ ਪਤਾ ਕਰਨ ਲਈ ਲੋੜ ਹੈ, n ਹੋਰ ਅੰਕ ਕਰਨ ਲਈ ਇਸ ਨੂੰ ਤੱਕ ਦੂਰੀ ਘੱਟ ਸਨ. 20 ਸਦੀ ਵਿੱਚ, ਇਸ ਨੂੰ ਇਸ ਵਿਸ਼ੇ 'ਤੇ ਕੰਮ ਕਰਨ ਲਈ ਜਾਰੀ ਹੈ. ਇਹ ਕੁਝ ਇੱਕ ਅੰਕ ਲੈ ਅਤੇ ਅਜਿਹੇ ਤਰੀਕੇ ਨਾਲ ਹੈ, ਜੋ ਕਿ ਨੂੰ ਵਿਚਕਾਰ ਦੂਰੀ ਘੱਟ ਸੀ ਨਾਲ ਜੁੜਨ ਦਾ ਫੈਸਲਾ ਕੀਤਾ ਗਿਆ ਸੀ. ਇਹ ਸਭ ਸਮੱਸਿਆ ਦਾ ਇੱਕ ਵਿਸ਼ੇਸ਼ ਸਥਿਤੀ ਦਾ ਅਧਿਐਨ ਕੀਤਾ ਜਾ ਰਿਹਾ ਹੈ.

"ਲੋਭੀ" ਕਲਨ

Kruskal ਦੇ ਐਲਗੋਰਿਥਮ "ਲੋਭੀ" ਐਲਗੋਰਿਥਮ (ਇਹ ਵੀ ਕਹਿੰਦੇ ਹਨ ਢਾਲ) ਦਾ ਹਵਾਲਾ ਦਿੰਦਾ ਹੈ. ਜਿਹੜੇ ਦੇ ਤੱਤ - ਹਰ ਕਦਮ 'ਤੇ ਸਭ ਦੀ ਜਿੱਤ. ਹਮੇਸ਼ਾ ਨਾ, "ਲਾਲਚੀ" ਐਲਗੋਰਿਥਮ ਸਮੱਸਿਆ ਦਾ ਵਧੀਆ ਹੱਲ ਹੈ ਮੁਹੱਈਆ ਕਰਦਾ ਹੈ. ਇੱਕ ਥਿਊਰੀ ਦਿਖਾ ਹੈ, ਜੋ ਕਿ ਖਾਸ ਕੰਮ ਕਰਨ ਲਈ ਆਪਣੇ ਕਾਰਜ ਨੂੰ ਉਹ ਸਰਵੋਤਮ ਦਾ ਹੱਲ ਦੇਣ, ਹੈ. ਇਹ matroids ਦੀ ਥਿਊਰੀ ਹੈ. Kruskal ਦੇ ਐਲਗੋਰਿਥਮ ਅਜਿਹੇ ਸਮੱਸਿਆ ਦਾ ਹਵਾਲਾ ਦਿੰਦਾ ਹੈ.

ਘੱਟੋ-ਘੱਟ ਲਾਸ਼ ਦਾ ਭਾਰ ਲੱਭਣਾ

ਦੇਖੇ ਐਲਗੋਰਿਥਮ ਇੱਕ ਅਨੁਕੂਲ ਫਰੇਮ ਗਿਣਤੀ ਬਣਾਏ. ਇਸ ਦੀ ਸਮੱਸਿਆ ਦਾ ਪ੍ਰਕਾਰ ਹੈ. ਦਾਨ ਪੈਰਲਲ ਕਿਨਾਰੇ ਅਤੇ ਇਹਨਆ ਬਿਨਾ ਗ੍ਰਾਫ undirected ਹੈ, ਅਤੇ ਕੋਨੇ ਦੇ ਸੈੱਟ ਦਾ ਭਾਰ ਫੰਕਸ਼ਨ W, ਜਿਸ ਲਈ ਹਰ ਕਿਨਾਰੇ ਈ ਨੰਬਰ ਨਿਰਧਾਰਤ ਦਿੱਤਾ ਗਿਆ ਹੈ - ਭਾਰ ਪੱਸਲੀ - w (ਈ). ਬਿੱਲਕੁਲ ਦੇ plurality ਦੇ ਹਰ ਸਮੂਹ ਦੇ ਭਾਰ ਨੂੰ ਇਸ ਦੇ ਕਿਨਾਰੇ ਦੇ ਭਾਰ ਦਾ ਜੋੜ ਹੈ. ਇੱਕ ਛੋਟੇ ਭਾਰ ਦੀ ਫਿਰਦੀ ਦਾ ਪਤਾ ਕਰਨ ਲਈ ਲੋੜ ਹੈ.

ਦਾ ਵੇਰਵਾ

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

ਨੂੰ ਲਾਗੂ ਕਰਨ

ਮੌਜੂਦਾ ਜੰਗਲ F. ਇਹ ਕੁਨੈਕਸ਼ਨ ਦੇ ਖੇਤਰ ਵਿਚ ਕੋਣਬਿੰਦੂ ਦੇ ਸੈੱਟ ਵੰਡ ਦਰਸਾਉਣ (ਆਪਣੇ ਯੂਨੀਅਨ ਫਾਰਮ ਤੇ ਜੁਡ਼ੋ, ਅਤੇ ਉਹ ਅਲੱਗ ਹਨ). ਲਾਲ ਕੋਣਬਿੰਦੂ ਦੇ ਕੋਨੇ 'ਤੇ ਉਹ ਇੱਕੋ ਹੀ ਟੁਕੜੇ ਦਾ ਝੂਠ. ਭਾਗ (x) - ਫੰਕਸ਼ਨ ਹੈ, ਜੋ ਕਿ ਹਰ ਇੱਕ ਕੋਣ X ਲਈ ਨਾਮ ਦੇ ਇੱਕ ਹਿੱਸੇ ਵਾਪਸ ਹੈ, ਇਸ ਨੂੰ X ਸਬੰਧਿਤ ਹੈ. Unite (x, y) - ਇੱਕ ਵਿਧੀ ਹੈ, ਜੋ ਕਿ ਇੱਕ ਨਵ ਭਾਗ ਬਣਾਉਦਾ ਹੈ, x ਅਤੇ y ਦੇ ਹਿੱਸੇ ਹਨ ਅਤੇ ਜੋ ਹੋਰ ਸਾਰੇ ਅੰਗ ਦਾ ਸੰਯੋਗ ਹੈ ਰੱਖਦਾ. n ਕਰੀਏ - ਕੋਨੇ ਦੀ ਗਿਣਤੀ ਹੈ. ਇਹ ਸਾਰੇ ਸੰਕਲਪ Kruskal ਦੇ ਐਲਗੋਰਿਥਮ ਵਿੱਚ ਸ਼ਾਮਿਲ ਰਹੇ ਹਨ. ਲਾਗੂ:

1. n-ਫਰਬਰੀ ਆਰੋਹੀ ਵਜ਼ਨ ਨੂੰ 1 ਦਾ ਦਰਜਾ ਤੱਕ ਗਰਾਫ਼ ਦੇ ਸਾਰੇ ਕੋਨੇ ਪ੍ਰਬੰਧ ਕਰੋ. (AI, ਦੋ - ਮੈਨੂੰ ਸੁਪਰੀਮ ਕਿਨਾਰੇ ਨੰਬਰ ਨਾਲ).

2. ਮੈਨੂੰ = 1 n ਕਰਦੇ ਹਨ.

3. X: = ਭਾਗ (AI).

4. y: = ਭਾਗ (BI).

5. X ਬਰਾਬਰ y ਫਿਰ Unite (x, y) ਕਰਦਾ ਹੈ, ਨਾ ਹੈ, ਜੇ, ਕਿਨਾਰੇ ਤੇ ਜੁਡ਼ੋ i ਨੰਬਰ ਨਾਲ ਸ਼ਾਮਲ ਕਰਨ ਦੀ.

ਸਹੀ

ਆਓ ਟੀ - ਇਸ ਦੇ ਆਪਹੁਦਰੇ ਫਰੇਮ - ਅਸਲੀ ਗਰਾਫ਼ ਦੇ ਫਰੇਮ Kruskal ਐਲਗੋਰਿਥਮ ਅਤੇ S ਵਰਤ ਬਣਾਇਆ ਗਿਆ ਹੈ. ਸਾਨੂੰ ਇਹ ਸਾਬਤ ਕਰਨ ਲਈ ਹੈ, ਜੋ ਕਿ w (ਟੀ) w (ਐਸ) ਵੱਧ ਹੈ, ਨਾ ਹੈ.

ਆਓ ਐਮ - fins ਐਸ, ਪੀ ਦੀ ਬਹੁ - fins ਦੀ ਇੱਕ plurality ਟੀ ਜੇ ਐਸ ਟੀ ਦੇ ਬਰਾਬਰ ਨਹੀ ਹੈ, ਫਿਰ ਉਥੇ ਇੱਕ ਫਰੇਮ ਪਸਲੀ ਅਤੇ ਟੀ, ਨੂੰ ਸ ਸ ਅਤੇ ਸਬੰਧਤ ਹੈ, ਨਾ ਚੱਕਰ, ਇਸ ਨੂੰ ਸੈਲਸੀਅਸ C ਕਿਹਾ ਗਿਆ ਹੈ, ਕੋਈ ਵੀ ਕਿਨਾਰੇ es ਤੱਕ ਨੂੰ ਹਟਾਉਣ adjoin ਨਾਲ ਸਬੰਧਤ ਹੈ ਸ ਸਾਨੂੰ ਇੱਕ ਨਵ ਫਰੇਮ ਨੂੰ ਪ੍ਰਾਪਤ ਹੈ, ਕਿਉਕਿ ਕਿਨਾਰੇ ਅਤੇ ਕੋਣਬਿੰਦੂ ਹੀ ਹੈ. ਇਸ ਦਾ ਭਾਰ w (ਐਸ), ਬਾਅਦ w (ਅਤੇ) ਕੋਈ ਵੀ ਹੁਣ w (ਹੈ) ਇੱਕ ਪਾਵਰ Kruskal ਐਲਗੋਰਿਥਮ ਵਿੱਚ ਵੱਧ ਵੱਡਾ ਨਹੀ ਹੈ. ਇਹ ਕਾਰਵਾਈ (ਬਿੱਲਕੁਲ 'ਤੇ ਬਦਲ ਦੇ ਟੀ ਐਸ ਬਿੱਲਕੁਲ) ਦੇ ਤੌਰ ਤੇ ਲੰਬੇ ਟੀ ਹਰ ਉਪਰੰਤ ਪ੍ਰਾਪਤ ਕੀਤੀ ਫਰੇਮ ਦੇ ਭਾਰ ਨੂੰ ਪ੍ਰਾਪਤ ਤੌਰ ਦੁਹਰਾਇਆ ਕੀਤਾ ਜਾਵੇਗਾ ਪਿਛਲੇ ਭਾਰ, ਜਿਸ ਦਾ ਮਤਲਬ ਹੈ ਵੱਧ ਹੈ, ਨਾ ਹੈ, ਜੋ ਕਿ w (ਟੀ) w (ਐਸ) ਵੱਧ ਹੈ.

Kruskal ਦੇ ਐਲਗੋਰਿਥਮ ਦੀ ਮਜ਼ਬੂਤੀ matroids ਤੇ Rado-Edmonds ਦੇ ਪ੍ਰਮੇਏ ਤੱਕ ਹੈ.

ਐਪਲੀਕੇਸ਼ਨ ਉਦਾਹਰਨ Kruskal ਐਲਗੋਰਿਥਮ

ਨੋਡ A, B, C, D, E ਅਤੇ ਬਿੱਲਕੁਲ (ਏ, ਬੀ), (ਇੱਕ, ਈ), (ਅ, ੲ), (ਅ, ਈ) ਦੇ ਨਾਲ ਦਾਨ ਗ੍ਰਾਫ, (C, D), (C, E) , (ਸ, ਈ). ਕੋਨੇ ਦੇ ਵਜ਼ਨ ਸਾਰਣੀ ਵਿੱਚ ਅਤੇ ਚਿੱਤਰ ਵਿੱਚ ਦਿਖਾਏ ਗਏ ਹਨ. ਸ਼ੁਰੂ ਵਿਚ, ਉਸਾਰੀ ਜੰਗਲ ਜੁਡ਼ੋ ਗਰਾਫ਼ ਦੇ ਸਾਰੇ ਕੋਣਬਿੰਦੂ ਰੱਖਦਾ ਹੈ ਅਤੇ ਕਿਸੇ ਵੀ ਬਿੱਲਕੁਲ ਨਹੀ ਹੈ. ਐਲਗੋਰਿਥਮ Kruskal ਪਹਿਲੀ ਪੱਸਲੀ (ਇੱਕ, ਈ), ਫਿਰ ਪਸਲੀ ਨੂੰ ਜੋਡ਼ਨ ਬਾਅਦ ਭਾਰ ਘੱਟ ਸੀ, ਅਤੇ ਕੋਣਬਿੰਦੂ ਏ ਅਤੇ ਈ-ਵੱਖ ਭਾਗ ਵਿੱਚ ਹਨ, ਲੱਕੜ ਕੁਨੈਕਸ਼ਨ ਜੁਡ਼ੋ (ਪੱਸਲੀ (ਇੱਕ ਈ) ਹਰੀ ਹੈ), (C, D), ਕਿਉਕਿ ਹੈ, ਜੋ ਕਿ ਘੱਟੋ-ਘੱਟ ਗ੍ਰਾਫ ਕੋਨੇ ਦੇ ਇਸ ਕਿਨਾਰੇ ਭਾਰ, F ਤੱਕ ਨਾ ਨਾਲ ਸਬੰਧਤ ਹੈ, ਅਤੇ ਇਸ ਨੂੰ ਹਰੀ ਹੈ, ਉਸੇ ਕਾਰਨ ਫਿਰ ਲਈ ਕਿਨਾਰੇ ਪਰ੍ਾਪਤ (A, b). ਪਰ ਕਿਨਾਰੇ (ਅ, ਹ) ਪਾਸ ਕੀਤਾ ਗਿਆ ਹੈ, ਪਰ ਫਿਰ ਵੀ ਉਹ ਅਤੇ ਬਾਕੀ ਕੋਨੇ ਦੇ ਘੱਟੋ-ਘੱਟ ਭਾਰ ਹੈ, ਕਿਉਕਿ ਇਸ ਨੂੰ ਲਾਲ ਹੈ: ਕੋਣਬਿੰਦੂ ਅ ਅਤੇ ਈ ਜੰਗਲ ਕੁਨੈਕਸ਼ਨ ਜੁਡ਼ੋ ਦੇ ਇਸੇ ਹਿੱਸੇ ਦੇ ਨਾਲ ਸਬੰਧਤ ਹੈ, ਜੋ ਕਿ ਹੈ, ਜੇ ਸਾਨੂੰ F ਤੱਕ ਕਿਨਾਰੇ (ਅ, ਹ) ਸ਼ਾਮਿਲ ਹੈ, ਦਾ ਗਠਨ ਕੀਤਾ ਗਿਆ ਹੈ ਚੱਕਰ. ਫਿਰ ਹਰੀ ਕਿਨਾਰੇ (ਅ, ੲ), ਪਾਸ ਹੈ ਲਾਲ ਕਿਨਾਰੇ (C, ਈ), ਅਤੇ ਫਿਰ d, ਈ ਹੈ. ਇਸ ਲਈ, ਕੋਨੇ ਸ਼ਾਮਿਲ ਕਰ ਰਹੇ ਹਨ ਕ੍ਰਮ (ਇੱਕ, ਈ), (C, D), (ਏ, ਬੀ), (ਅ, ੲ). nihera ਅਨੁਕੂਲ ਫਰੇਮ ਤੱਕ ਹੈ ਅਤੇ ਅਸਲੀ ਗ੍ਰਾਫ ਦੇ ਸ਼ਾਮਲ ਹਨ. ਇਸ ਲਈ ਇਸ ਮਾਮਲੇ 'ਚ ਇਸ ਨੂੰ ਇੱਕ ਕਲਨ ਕੰਮ Kruskal. ਇੱਕ ਉਦਾਹਰਨ ਵੇਖਾਇਆ ਗਿਆ ਹੈ.

ਇਹ ਅੰਕੜਾ ਦੋ ਜੁੜੇ ਭਾਗ ਹਨ, ਜੋ ਕਿ ਇੱਕ ਗਰਾਫ਼, ਪਤਾ ਲੱਗਦਾ ਹੈ. ਬੋਲਡ ਲਾਈਨ ਅਨੁਕੂਲ ਫਰੇਮ ਬਿੱਲਕੁਲ (ਹਰੀ) Kruskal ਐਲਗੋਰਿਥਮ ਵਰਤ ਨਿਰਮਾਣ ਦਾ ਸੰਕੇਤ.

ਘੱਟੋ-ਘੱਟ ਭਾਰ ਦੇ ਇੱਕ ਫਿਰਦੀ, ਉਸ ਲਈ ਬਣਾਇਆ ਐਲਗੋਰਿਥਮ ਵਰਤ ਕੇ - ਚੋਟੀ ਦੇ ਤਸਵੀਰ ਅਸਲੀ ਗ੍ਰਾਫ, ਅਤੇ ਹੇਠਲੇ ਪਤਾ ਲੱਗਦਾ ਹੈ.

ਜੋੜੇ ਬਿੱਲਕੁਲ ਦੀ ਲੜੀ (1.6); (0,3), (2,6) ਜ (2,6), (0,3) - ਜ਼ਰੂਰੀ ਨਹੀ ਹੈ; (3,4); (0,1), (1,6) ਜ (1,6), (0,1), ਨੂੰ ਵੀ ਦੇਖ-ਭਾਲ (5,6).

Kruskal ਦੇ ਐਲਗੋਰਿਥਮ gasket ਸੰਚਾਰ, ਹਰੇਕ ਦੇਸ਼ ਵਿਚ ਨਵ ਹਾਊਸਿੰਗ ਜਾਇਦਾਦ ਇਲਾਕੇ, ਦੇ ਨਾਲ ਨਾਲ 'ਚ ਹੋਰ ਮਾਮਲੇ ਵਿੱਚ ਸੜਕ ਨੂੰ ਅਨੁਕੂਲ ਕਰਨ ਲਈ, ਉਦਾਹਰਨ ਲਈ, ਅਮਲੀ ਕਾਰਜ ਨੂੰ ਲੱਭਦੀ ਹੈ.