ਲਾਲਚੀ ਐਲਗੋਰਿਦਮ ਕੀ ਹਨ, ਅਤੇ ਉਹ ਕਦੋਂ ਕੰਮ ਕਰਦੇ ਹਨ?

Question

Accepted Answer

ਇੱਕ **ਲਾਲਚੀ ਐਲਗੋਰਿਦਮ**ਹਰ ਪੜਾਅ ਤੇ **ਸਥਾਨਕ ਤੌਰ ਤੇ ਸਰਵੋਤ੍ਤਮ ਚੋਣ**ਕਰਦਾ ਹੈ, ਏਸ ਉਮੀਦ ਨਾਲ ਕਿ ਇਹ ਗਲੋਬਲ ਸਰਵੋਤ੍ਤਮ ਵੱਲ ਲੈ ਜਾਵੇ। ਇਹ ਸਰਲ ਅਤੇ ਤੇਜ਼ ਹੈ, ਪਰ ਸਿਰਫ ਤਦ ਸਠੀਕ ਹੈ ਜਦੋਂ ਸਮੱਸਿਆ **ਲਾਲਚੀ-ਚੋਣ ਵਿਸ਼ੇਸ਼ਤਾ**ਅਤੇ **ਸਰਵੋਤ੍ਤਮ ਉਪ-ਬਣਤਰ** ਰੱਖਦੀ ਹੈ।

## ਵਿਚਾਰ

ਅਤੀਤ ਦੀ ਚੋਣਾਂ ਤੇ ਦੁਬਾਰਾ ਵਿਚਾਰ ਨਾ ਕਰੋ — ਸਭ ਤੋਂ ਬਿਹਤਰ ਤਤਕਾਲ ਵਿਕਲਪ ਲਈ ਪ੍ਰਤਿਬੱਧ ਹੋ ਅਤੇ ਅੱਗੇ ਵਧੋ।

## ਉਦਾਹਰਨ: ਪ੍ਰਮਾਣਿਕ ਸਿੱਕਿਆਂ ਨਾਲ ਸਿੱਕਾ ਬਦਲਾਓ

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

ਇਹ ਅਮਰੀਕੀ ਸਿੱਕਿਆਂ ਲਈ ਸਰਵੋਤ੍ਤਮ ਹੈ, ਪਰ {1, 3, 4} ਜਿਵੇ ਸੈੱਟਾਂ ਲਈ **ਅਸਫਲ** ਹੁੰਦਾ ਹੈ ਜਿੱਥੇ ਲਾਲਚੀ 6 ਲਈ 3+3 ਦੀ ਜਗ੍ਹਾ 4+1+1 ਦਿੰਦਾ ਹੈ।

## ਜਦੋਂ ਲਾਲਚੀ ਕੰਮ ਕਰਦਾ ਹੈ

- **ਸਰਵੋਤ੍ਤਮ ਉਪ-ਬਣਤਰ:** ਇੱਕ ਸਰਵੋਤ੍ਤਮ ਹੱਲ ਸਰਵੋਤ੍ਤਮ ਸਬ-ਸਮਾਧਾਨ ਧਾਰਦਾ ਹੈ।
- **ਲਾਲਚੀ-ਚੋਣ ਵਿਸ਼ੇਸ਼ਤਾ:** ਇੱਕ ਸਥਾਨਕ ਸਰਵੋਤ੍ਤਮ ਗਲੋਬਲ ਸਰਵੋਤ੍ਤਮ ਦਾ ਹਿੱਸਾ ਹੈ।

ਕੰਮ ਕਰਨ ਵਾਲੀਆਂ ਉਦਾਹਰਨਾਂ: Dijkstra, Kruskal/Prim (MST), Huffman ਕੋਡਿੰਗ, ਅੰਤਰਾਲ ਸ਼ਿਡਿউਲਿੰਗ।

## ਜਟਿਲਤਾ

ਆਮ ਤੌਰ ਤੇ ਤੇਜ਼ — ਅਕਸਰ ਛਾਂਟਣ ਤੋਂ ਬਾਅਦ O(n log n)।

## ਨੁਕਸਾਨ

ਲਾਲਚੀ **ਹਮੇਸ਼ਾ ਸਠੀਕ ਨਹੀਂ ਹੈ**। ਲਾਲਚੀ-ਚੋਣ ਵਿਸ਼ੇਸ਼ਤਾ ਸਾਬਤ ਕਰੋ ਜਾਂ ਇਸ ਤੇ ਭਰੋਸਾ ਕਰਨ ਤੋਂ ਪਹਿਲਾਂ ਬਿਰੂਟ-ਫੋਰਸ/DP ਬੇਸਲਾਈਨ ਵਿਰੁੱਧ ਟੈਸਟ ਕਰੋ।

## ਕਿਉਂ ਇਹ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ

ਜਦੋਂ ਲਾਲਚੀ ਲਾਗੂ ਹੁੰਦਾ ਹੈ, ਇਹ DP ਜਾਂ ਬਿਰੂਟ ਫੋਰਸ ਨਾਲੋਂ ਬਹੁਤ ਸਰਲ ਅਤੇ ਤੇਜ਼ ਹੈ।

*ਕਦੋਂ* ਇਹ ਵੈਧ ਹੈ — ਅਤੇ *ਕਦੋਂ* ਇਹ ਚੁੱਪ ਨਾਲ ਗਲਤ ਜਵਾਬ ਦਿੰਦਾ ਹੈ ਜਾਣਨਾ — ਇਹ ਐਲਗੋਰਿਦਮਿਕ ਪਰਿਪੱਕਤਾ ਦਾ ਨਿਸ਼ਾਨ ਹੈ।

ਬਹੁਤ ਸਾਰੀਆਂ ਮੁੱਖ ਗ੍ਰਾਫ ਐਲਗੋਰਿਦਮ ਦਿਲ ਵਿਚ ਲਾਲਚੀ ਹਨ।