Mam zrobić referat dotyczący metody obcinania gałęzi w algorytmie branch and bound rozwiązującym znany problem drogi skoczka przez wszystkie pola szachownicy. Przypuszczam, że ktoś już to robił dlatego nie kazano mi tego wymyślać a jedynie zreferować odkrytą metodę sprytnego obcinania. Obcinanie ma być zrobione funkcją heurystyczną lub niezłą funkcją która na wczesnym etapie obcina drogi, które na pewno nie dadzą rozwiązania. Jeśli ktoś coś wie o materiałach na ten temat, w miarę przystępnie napisanych, po polsku lub po angielsku, to proszę o informacje.
0
0
Wydaje mi się że pomysł był taki żeby z dostępnych ruchów wybierać zawsze takich ruch z którego mamy najmniej ruchów w nastepnej kolejce.
0
Sortowanie ruchów w danym posunięciu według priorytetów to jest jakiś pomysł, ale z tego co czytałem to nie zmniejszy znacząco ilości przeglądanych gałęzi, która dla algorytmu z powrotami może iść w kwadryliony. Chodzi przede wszystkim o zastosowanie funkcji obcinającej, która eliminuje całkowicie (lub ewentualnie z bardzo dużym prawdopodobieństwem) potrzebę przeglądania wielu rozgałęzień już we wczesnych posunięciach, co powinno zredukować liczbę potrzebnych badań do kilku milionów. Niestety funkcja ta musi być dopasowywana osobno dla danego zadania, więc nie ma ogólnych reguł jej opracowania.