trädsök

Trädsök, eller tree search på engelska, är en samling algoritmer för att utforska ett tillståndsutrymme som kan representeras som ett träd eller en graf. Målet är vanligtvis att hitta en sekvens av åtgärder som leder från starttillståndet till ett mål eller att avgöra att ett mål är uppnåeligt eller inte. Trädsök används inom artificiell intelligens, automatiserad planering och spelteori.

En uppdelning görs oftast mellan uninformerad (blind) trädsök och informerande (heuristisk) trädsök. Bland de grundläggande blindmetoderna finns bred först-sökning och djup först-sökning, samt variantens kostnadssökningar som uniformkostnadssökning. Inom heuristisk sök används målfunktioner (heuristik) som leder sökningen mot lovande delproblem, exempelvis A*-sökning och andra best-first-metoder.

Skillnaden mellan trädsök och graf-sök ligger i hur upprepningar hanteras. Trädsök behandlar varje gren som ett nytt tillstånd även om det upprepas i andra grenar, vilket kan vara enklare men mer minneskrävande. Graf-sök använder en uppsättning besökta tillstånd för att undvika cykler och kan vara mer effektiv i många situationer.

Komplexitet och minne är centrala begränsningar: i praktiken växer antalet nodar exponentiellt med djupet i trädet. Djupet och grenningen påverkar körningstiden och minnesbehovet kraftigt. Heuristikernas kvalitet avgör hur snabbt en lösning hittas och hur minneskrävande processen blir.

Användningsområden omfattar pussel och spel, planering och ruttval i robotik. Ursprungligen utvecklades trädsök som en kärnpunkt inom artificiell intelligens under 1950- och 1960-talen, med influenser från tidiga forskare som Allen Newell och Herbert Simon. Modern tillämpning inkluderar sökoptimering i programvara och AI-system.