droga skoczka z użyciem branch and bound

Odpowiedz Nowy wątek
2011-09-13 11:50
Radek
0

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.

Pozostało 580 znaków

2011-09-13 14:37
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.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2011-09-13 15:17
Radek
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.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0