>source

다음 레이아웃이 있습니다 :

그래프 표현

목적은 흰색 공을 움직여서 모든 노란색 블록을 수집하는 것입니다. 효율적인 경로를 계산하는 알고리즘을 만들려고하지만 어디서부터 시작 해야할지 잘 모르겠습니다.

처음에 Djikstra 및 A *와 같은 경로 찾기 알고리즘에 대해 생각했지만 제 목표에 맞지 않는 것 같습니다. 나는 또한 내가 원하는 것에 더 가깝지만 여전히 문제를 해결하지 못하는 hamiltonian 경로에 대해 생각했습니다.

어떤 종류의 알고리즘을 사용할 수 있는지에 대한 제안은 감사하겠습니다.


  • 답변 # 1

    문제는 문학에서 고전적인 이름을 가지고 있으며최소한의 hamiltonian walk 문제입니다. 그것은 훨씬 더 유명하고 훨씬 더 어렵 기 때문에 최소한의 hamiltonian path 문제 인 'cousin'으로 착각하지 않도록 조심하십시오 (다항식 시간에 hamiltonian walking을 찾는 것은 hamiltonian 경로를 찾는 것이 NP-complete입니다) . 여행하는 판매원 문제는 최소 hamiltonian 경로 문제 (도보가 아닌 경로)의 다른 이름입니다.

    이 문제에 대한 자원은 거의 없지만 그럼에도 불구하고 1980 년부터 Takamizawa, Nishizeki 및 Saito의 '그래프에서 짧은 닫힌 스패닝 보행을 찾는 알고리즘'이라는 기사를 볼 수 있습니다. 다항식을 제공합니다. 그러한 경로를 찾기위한 알고리즘.

    논문을 읽기가 어렵거나 구현하기에 너무 복잡한 알고리즘이라면, 다항식 시간에 실행되고 어떻게 든 효율적이기 때문에 christofides 알고리즘을 사용하는 것이 좋습니다. -잘 기억하면 근사))

    또 다른 가능한 접근법은 가장 가까이에 방문하지 않은 네이버 알고리즘과 같은 탐욕스러운 알고리즘을 찾는 것입니다 (어딘가에서 시작하여 아직 걸어 있지 않은 가장 가까운 노드로 이동하고 모두가 걸어서 갈 때까지 반복하십시오).
    전적으로, 나는 가장 쉽고 아마도 가장 간단한 해결책은 탐욕스러운 것이라고 생각합니다.

관련 자료

  • 이전 angular - # to pug-template HTML 요소
  • 다음 휴고 블로그 + netlify 배포 + 사용자 정의 도메인 = 페이지를 찾을 수 없음