일반적으로 조건은 가장 적은 비용으로 A에서 B로 이동하지만 비용 옆에있는 각 링크는 구매/수집 할 수있는 몇 가지 항목이 있습니다.A * 변형에는 추가 제한이 포함됩니다.
사실 포켓몬 플레이어는 아니지만 더 잘 설명하기 위해 테마를 사용하면 가장 가까운 길을 따라 도로 주변의 각 항목 중 적어도 하나를 집에서 체육관으로 가져 가야합니다.
나는 A *와 최단 경로를 해결할 수있다. 추가 제한을 포함하려면 어떻게해야합니까? 또는 다른 알고리즘을 사용해야합니까?
시작 비용을 사용하려고 생각 중이므로 항목을 찾을 때 비용을 줄이고 여행 할 때 비용이 증가합니다. 그리고 0에 가까워 지려고 시도하십시오.
다른 옵션은 모든 항목에 적용되는 경로를 찾으려고합니다. 그런 다음 해당 하위 집합과 함께 A *를 사용하십시오. 그러나 어떤 알고리즘이 그것을 해결할 수 있는지 확실하지 않습니다.
나는 BFS을 사용할 것입니다. 일반적으로 노드를 방문한 것으로 표시하여 각 노드를 한 번만 방문합니다. 하지만이 문제의 경우 발견 된 항목과 이동 한 거리를 추적해야합니다. 따라서 각 노드는 여러 항목 집합을 사용하여 여러 번 방문 할 수 있습니다. 귀하의 예제를 사용
는
A for 200 poke balls
B for lure module
C for incense
D for egg
및 노드
S for the start node
T for the top node
M for the middle node
L for the lowest node
Z for the end node
는 IS 문제는 {S::0}으로 시작합니다. 즉 항목이없고 거리가 0 인 노드 S를 의미합니다. 그런 다음 {T:C:1}, {M:A:1} 및 {L:BD:1}을 대기열에 넣습니다.
{T:C:1}부터 {S:C:2}, {M:BC:2} 및 {Z:BCD:2}을 대기열로 지정합니다.
대기열에서 {S:C:2}를 당길 때 당신이하지 큐 {T:C:3}을 그래서, 당신은 T는 이미 거리 1 항목 C를 가지고 해당 노드를 알게 될 것이다. 그러나 {M:AC:3}과 {L:BCD:3}을 대기열에 넣습니다.
결국 {Z:ABCD:n}이 표시됩니다. n이 약간 거리에 있습니다.
BFS가 A *보다 느리게 _ 진행됩니다. –
@MooingDuck 몇 가지 예가 있습니까? 링크 또는 문서는 정상입니다. –
제 아이디어는 바보 같았습니다. 당신이 보통 몇 번 시도해 보는 가정에서 일종의 일을합니다. 그리고 생각하기에는 A * 경험적 방법이 과소 평가되어야한다고 생각합니다. 그래서 추가가 무효합니다. 내가 말한 것을 무시하십시오. –
@MooingDuck 예, 실제로 우선 순위가 인정되는 허용 가능한 휴리스틱을 찾을 수 없다면 A *는 문제에도 적용되지 않습니다. 실제로 저조한 휴리스틱 스를 사용하면 A *가 실제로 느린 BFS로 축소됩니다. 단순 대기열 대신 우선 순위 대기열을 사용하므로 속도가 느리며 휴리스틱을 계산하는 데 시간을 낭비하기 때문에 속도가 느립니다. – user3386109