Minimalna potęga dodawania łańcucha

Question

Wiem, że zostało to udowodnione NP-complete, i to jest w porządku. Obecnie rozwiązuję go z odgałęzieniem i ograniczeniem, w którym ustawiłem początkowy górny limit na liczbę mnożeń, które przyjęłoby zwykły binarny algorytm kwadratowy/mnożnikowy, i daje on prawidłowe odpowiedzi, ale nie jestem zadowolony z biegania czas (może potrwać kilka sekund dla liczb około 200). Jest to problem NP-zupełny, nie spodziewam się niczego spektakularnego; ale często pojawiają się sztuczki, aby nieco kontrolować Rzeczywisty Czas.

Czy w praktyce są na to szybsze sposoby? Jeśli tak, to jakie one są?

Answer 1

To wygląda jak sekcja 4.6.3 "Ocena uprawnień" w Knuth Vol 2 Seminumerical Algorithms. Jest to bardzo szczegółowe, ponieważ daje różne podejścia, które wyglądają o wiele szybciej niż rozgałęzienia i ograniczenia, ale nie wszystkie zapewniają absolutnie najlepsze rozwiązanie.

Knuth stwierdza w dyskusji po twierdzeniu F, że używa przeszukiwania wstecznego, aby udowodnić, że l (191) = 11, więc wątpię, czy znajdziesz na to krótką odpowiedź. Odwołuje się do wyjaśnienia przeszukiwania wstecznego do sekcji 7.2.2, co moim zdaniem wciąż nie zostało opublikowane, chociaż istnieją ślady pracy nad tym na http://www-cs-faculty.stanford.edu/~uno/programs.html.

Answer 2

Metaheurystyki algorytmy będą skalować znacznie lepiej. Obejmują one Tabu przeszukiwanie, Algorytmy genetyczne, Symulowane wyżarzanie ...

Istnieje kilka freebooks i bezpłatnym software tam.