Cad é an backtracking?

Question

Accepted Answer

**Tógann backtracking** réitigh bharrúil go céimníoch agus **thréigean** (filleann sé siar) ó bharrúil pháirteach a luath is nach féidir léi réiteach bhailí a thabhairt ar chéachtas. Scrúdaíonn sé an spás réiteach go córasach trí DFS, ag foluain ghéaga marbha.

## An smaoineamh

Roghnaigh -> fiosraigh -> diomhnaigh. Triail a dhéanamh ar rogha, athfhillteach; más theip uirthi, cuir ar ceal í agus triail an chéad cheann eile.

## Sampla: gach iomalartú

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # complete solution
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                             # un-choose (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 permutations
```

## Fadhbanna clasaiceacha

- **N-banríona**, Sudoku, cuairt an ridire.
- **Fo-thacair / teaglaim / iomalartú.**
- **Cuardach focal**, réiteach dédail.

## Castacht

Go minic easpónantúil (m.sh., O(n!) do iomalartú), ach **foluain** laghdaíonn an cuardach praiticiúil go mór.

## Cathain a úsáid / píteal

Úsáid do shásúchán srianta agus fadhbanna "gach cumrasc bailí a aimsiú". Is é an bua príomhúil ná **foluain luath** — scip ghéaga a bhréagann srianta. Is é an fabht clasaiceach dearmad a dhéanamh ar stát a chur ar ceal ("diomhnaigh").

## Cén fáth atá sé tábhachtach

Is é an backtracking an bealach córasach chun spásanna comhbhiain a rafánáil gan iarratasaí a bheith ar iarraidh nó ag athrá.

Cumrasc maith a thrasnann brúidiúlacht inatráchtála ina rud a bhíonn críochnú in am.

Cumhachtaíonn sé réiteoir do phuzail, sceidealúchán, agus fadhbanna srianta ar fud an tionscail.