Wyszukiwanie kombinatoryczne

W informatyce i sztucznej inteligencji wyszukiwanie kombinatoryczne bada algorytmy wyszukiwania w celu rozwiązywania przypadków problemów, które ogólnie uważa się za trudne , poprzez wydajne badanie zwykle dużej przestrzeni rozwiązań tych przypadków. Kombinatoryczne algorytmy wyszukiwania osiągają tę wydajność poprzez zmniejszenie efektywnego rozmiaru przestrzeni wyszukiwania lub zastosowanie heurystyki. Niektóre algorytmy gwarantują znalezienie optymalnego rozwiązania, podczas gdy inne mogą zwrócić tylko najlepsze rozwiązanie znalezione w badanej części przestrzeni stanów.

Klasyczne kombinatoryczne problemy wyszukiwania obejmują rozwiązywanie zagadki z ośmioma hetmanami lub ocenianie ruchów w grach z dużym drzewem gier , takich jak reversi lub szachy .

Badanie teorii złożoności obliczeniowej pomaga motywować poszukiwania kombinatoryczne. Algorytmy przeszukiwania kombinatorycznego zwykle dotyczą problemów, które są NP-trudne . Ogólnie uważa się, że takie problemy nie są skutecznie rozwiązywane. Jednak różne przybliżenia teorii złożoności sugerują, że niektóre przypadki (np. „małe” przypadki) tych problemów można skutecznie rozwiązać. Tak jest w rzeczywistości, a takie przypadki często mają ważne konsekwencje praktyczne.

Przykłady

Typowe algorytmy rozwiązywania problemów wyszukiwania kombinatorycznego obejmują:

Patrz przed siebie

Lookahead jest ważnym elementem wyszukiwania kombinatorycznego, który określa z grubsza, jak głęboko eksplorowany jest wykres reprezentujący problem. Potrzeba określonego limitu przewidywania wynika z dużych wykresów problemów w wielu aplikacjach, takich jak szachy komputerowe i komputer Go . Naiwne przeszukiwanie tych wykresów wszerz szybko pochłonęłoby całą pamięć każdego nowoczesnego komputera. Ustawiając określony limit wyprzedzający, można dokładnie kontrolować czas algorytmu; jego czas rośnie wykładniczo wraz ze wzrostem limitu wyprzedzającego.

Bardziej wyrafinowane techniki wyszukiwania, takie jak przycinanie alfa-beta, są w stanie wyeliminować z rozważań całe poddrzewa drzewa wyszukiwania. Gdy stosowane są te techniki, wyprzedzanie nie jest precyzyjnie określoną wielkością, ale albo maksymalną przeszukiwaną głębokością, albo pewnym rodzajem średniej.

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Combinatorial_search&oldid=979971956 ”