1
어떤 조각의 움직임 규칙이 주어지면 말 (또는 기사) 또는 다른 무엇이라고 부르는 지, 어떻게 조각이 현재있는 곳과 체스 판의 다른 주어진 지점 사이의 최단 경로를 계산할 수 있을까요?체스 판에서 두 지점 사이의 최단 경로를 찾는 방법은 무엇입니까?
나는 코드를 찾는 것이 아니라 생각 만하고 있습니다. 나는 알고리즘을 찾고있다.
도움 주셔서 감사합니다.
A
답변
1
BFS을 경로 찾기 알고리즘으로 사용할 수 있습니다. 각 단계에서 다음 정거장은 조각에 의한 모든 가능한 동작이됩니다.
+1
그러나 DFS는 최단 경로를 찾지 못합니다. 나는 그가 BFS 만 필요하다고 생각한다. –
+0
DFS의 약간의 수정은 문제를 해결할 것이지만 나는 더 혼란을 일으킬 것이라고 생각한다. 댓글 주셔서 감사합니다. –
+1
A * ("지능형 DFS")는 단일 최단 경로를 반환합니다. 그러나 기사에 대한 가능한 모든 최단 경로를 생성 할 때 두 가지 시작점 BFS를 사용했습니다 (CS 과정 할당). BFS는 런타임이 눈에 띄기 전에 UI에서 가능한 모든 경로를 나열하기 위해 메모리가 부족하기 때문에 빠릅니다 (약 20 제곱 거리는 1M 최단 경로에 가까운 거리를 생성합니다). –
관련 문제
- 1. 특정 경로를 따라 두 지점 사이의 거리를 찾는 방법은 무엇입니까?
- 2. 그래프에서 두 vertives 간의 최단 경로를 찾는 방법은 무엇입니까?
- 3. 두 객체 간의 최단 경로를 찾는 알고리즘
- 4. 두 배열 사이의 최단 거리를 찾는 효율적인 방법은 무엇입니까?
- 5. Swift에서 두 지점 (주석) 사이의 경로를 그리는 방법은 무엇입니까?
- 6. 두 도형 사이의 최단 경로 찾는 법?
- 7. QuickGraph를 사용하여 두 꼭지점 사이의 모든 경로를 찾는 방법
- 8. 무 방향성 그래프에서 두 정점 사이의 모든 최단 경로를 찾는 방법은 무엇입니까?
- 9. 파이썬 목록에서 점 사이의 최단 거리를 찾는 클리너 방법은 무엇입니까?
- 10. 행렬에서 최단 경로를 찾는 방법
- 11. 이진 행렬의 두 점 사이의 최단 경로
- 12. 두 단어 사이의 "최단 거리"를 계산하는 방법은 무엇입니까?
- 13. 두 지점 사이의 대각선이
- 14. 랩핑 넘는 숫자의 양방향에서 최단 경로를 찾는 방법은 무엇입니까?
- 15. 두 지점 사이의 경로 그리기
- 16. 두 점 사이의 최단 거리를 가져옵니다
- 17. 행렬에서 최단 경로를 찾는 데 문제가 있습니다.
- 18. 최단 경로를 찾는 재귀 적 접근
- 19. 두 줄 사이의 최단 거리
- 20. O (| V |)의 무향 그래프에서 u와 v 사이의 최단 경로를 찾는 방법은 무엇입니까?
- 21. 고도를 사용하여 최단 경로를 찾는 그래프 알고리즘
- 22. 두 장소 사이의 위치를 찾는 방법은 무엇입니까?
- 23. Oracle에서 최단 경로를 찾으라는 질문
- 24. BFS를 사용하여 두 노드 사이의 거리를 찾는 방법은 무엇입니까?
- 25. 좌표계의 두 점 사이의 최단 경로
- 26. 거대한 그래프를 메모리에로드하여 주어진 두 노드 사이의 최단 경로를 반복적으로 찾는 방법?
- 27. xquery - 두 노드 사이의 모든 경로를 찾는 BFS
- 28. 암시 적 그래프에서 최단 경로를 찾는 연결 검사의 수 최소화하기
- 29. Google지도에서 두 geocoords 사이의 경로를 표시하는 방법은 무엇입니까?
- 30. 두 지점 간의 경로를 찾는 데 사용할 SQL 쿼리
cs.stackexchange.com에서 질문하거나 추가 정보를 제공하는 것이 좋습니다. 우리는 기존의 작품 만 다루거나 새로운 작품을 임의의 동작으로 정의 할 수 있습니까? 특정 위치에 도달 할 수 없다면 어떻게 처리합니까? (예 : 검정색 바탕에 흰색 대상에 접근하려는 주교가있는 경우) 그리드의 크기는 얼마입니까? – ilim
고맙습니다. 좋은 지적이야. 나는 내 머리 속에서 해답을 가지고 있지만, 나는이 세부 사항을 채우기 위해 질문을 편집 할 것이다. –