가장 긴 경로를 찾는 방법은 무엇입니까?

Question

다음 문제 :

엔진 (예 : 자동차)이 직진 도로에서 여행을 시작합니다. 그것의 소비는 거리에 직접적으로 비례한다 (예를 들어, 480km는 연료 1 단위를 사용하므로 48km는 10 분의 1 단위의 연료를 사용한다). 이 엔진은 기껏해야 1 단위의 연료를 수송 할 수 있습니다.

시작 지점에는 n0 연료 장치가 공급됩니다. 경로상의 다른 지점에는 연료 저장소 (예 : n1 @ d1, n2 @ d2 등)가 있으며 운전자는 경로의 어느 곳에서나 연료를 배출 할 수 있습니다. 예를 들어, 한 단위의 경우 480km로 운전자는 160km를 주행 할 수 있고 1/3 단위의 연료가있는 저장소를 만들고 엔진에 연료를 보급하기 위해 출발점으로 다시 돌아올 수 있습니다.

출발 연료와 경로의 저장소에 따라 얻을 수있는 최대 거리를 찾기위한 알고리즘 (또는 몇 가지 아이디어를 찾고 있습니다)을 찾고 있습니다.

Answer 1

여러분은 또한 *, dijkstra 방법에 사용 된 "< ="비교를 "반전"시킬 수 있다고 생각합니다.

또는 논리 매개 변수 (최상의, 최악의) 경로를 추가하십시오.

반복 된 코드없이 동일한 경로 검색을 유지할 수 있습니다.

Answer 2

직감으로 욕심 많은 알고리즘이 최적이어야합니다. 즉, 각 저장소에서 사용할 수있는 연료의 양을 최대화하여 가능한 경로를 최대화해야합니다. 이것은 단지 제 의견입니다. 나는 "어느 곳에서나"실제로 "어떤 창고"에 있다고 가정합니다.

그리 디 알고리즘은 어떻게 작동합니까? 각 시점에서, "앞으로 나아갈 것"또는 "다시 채울 이전 창고로 돌아 가라."라는 두 가지 결정만을해야합니다. 탐욕스러운 욕구는 현재의 디포 예비비를 늘리는 한 항상 되돌아갑니다.