NP가 완전하다는 것이 입증되었고, 괜찮습니다. 나는 현재 분지를 사용하여 그것을 해결하고 있는데, 곱셈의 수로 초기 상한값을 정하면 정규 이진 사각형/곱셈 알고리즘을 취할 것이고 올바른 답을 얻을 수 있지만 실행에 만족하지는 않습니다. 시간 (200 정도의 숫자는 수 초가 걸릴 수 있습니다). NP 완성 문제이기 때문에 나는 특별한 것을 기대하지 않습니다. 실제 시간을 다소 통제하기위한 트릭이 종종 있습니다.최소한의 덧셈 - 체인 누적
실제로이를 수행하는 더 빠른 방법이 있습니까? 그렇다면 무엇입니까?
이것은 Knuth Vol.2 Seminumerical Algorithms의 4.6.3 "Powers의 평가"섹션과 같습니다. 이것은 다양한 접근 방식을 제공하기 위해 상당한 세부 사항으로 들어가는데, 이는 지점 및 바운드보다 훨씬 빠르게 보이지만 모두 최선의 최상의 솔루션을 제공하지는 못합니다.
크 누스 (Knuth)는 정리 F 이후의 토론에서 그가 역 추적 검색을 사용하여 l (191) = 11임을 증명하기 때문에이 문제에 대한 답을 찾을 수 있을지 의심 스럽습니다. 그는 섹션 7.2.2에 대한 백 트랙 검색에 대한 설명을 뒷받침합니다. 아직 공개되지 않은 것 같습니다. http://www-cs-faculty.stanford.edu/~uno/programs.html에서 이것에 대한 작업 흔적이 있습니다.
OP가 더 나은 속도와 교환하여 정확한 최상의 솔루션을 포기할 용의가 있는지 잘 모르겠습니다. 적어도 그는 그의 질문에 명시 적으로 말하지 않았다. –
나는 그렇게 명시 적으로 말하지는 않았지만 실제로는 최소한의 것이어야하며, 최소한의 지역적 최소값을 가져야 만한다. 그래서 저는 실생활의 관점에서이 문제를 더 잘 수행하는 다른 지수 시간 알고리즘을 찾고 있습니다. – harold
고마워, 적어도 이보다 더 좋은 초기 바인딩을 설정할 수있을 것이다. 7 장을 기다리 라. – harold