최상의 경로를 찾으려면 알고리즘이 필요합니다.

Question

경로 찾기 문제의 최상의 솔루션을 찾으려면 알고리즘이 필요합니다. 문제는 다음과 같이 설명 할 수 있습니다.

• 출발점에서 나는 여러 경로를 따라 진행할 수 있습니다.
• 각 단계마다 다른 가능한 여러 가지 선택 사항이 있습니다.
• 각 단계에서의 수 개의 동작이 있습니다
  • 경로가 수용 가능 여부를 결정하는 경계 조건.
  • 경로가 최종 대상에 도달했으며 최상의 경로로 선택할 수 있는지를 결정하는 조건.
• 각 단계에서 여러 경로를 제거하여 "양호한"경로 만 성장시킬 수 있습니다.

이 내용이 제 문제와 충분히 무차별 한 해결책을 충분히 설명하기를 바랍니다.

내 질문은 : 무력은 문제에 대한 최선의 해결책 일 뿐이며 알고리즘의 최상의 코딩 구조에 대한 힌트가 필요합니다.

Answer 1

는 당신이 시도했던 breadth-first search? 길이가 최상의 경로 위한 기준 인 경우입니다 (BFS) 당신은 또한 A *를 살펴 보자

Answer 2

무시 "받아 들일 수없는 경로"할 수있는 알고리즘을 수정해야하고,을 사용합니다 길이를 경계 조건으로 사용합니다.

http://en.wikipedia.org/wiki/A%2a_search_algorithm

Answer 3

당신은 상태 공간 탐색 알고리즘의 어떤 종류를 찾고 있습니다. 특정 문제에 대해 더 많이 알지 못하면 다른 문제를 추천하기가 어렵습니다.

공간이 제한이 없거나 (예 : 체스) 무제한 경로를 제거하고 유망한 경로를 선택하는 알고리즘이 필요한 경우. 알파 베타 알고리즘 (많은 OLD 체스 프로그램에서 사용됨)이 즉시 적용됩니다.

A * 알고리즘으로 좋은 결과를 얻을 수 있습니다. A *에서 좋은 결과를 얻으려면 현재 노드와 여러 후속 노드를 평가하여 가장 유망한 경로를 선택하는 좋은 추론 (가중 함수)을 선택해야합니다. 간단한 경로 길이로는 충분하지 않을 수 있습니다.

Elaine Rich의 AI 교재 (oldie하지만 goodie)는 다양한 검색 알고리즘에 상당한 시간을 보냈습니다. Full Disclosure : UT 오스틴에서 학부모 시절 동안 본문의 기니피그 중 한 명이었습니다.

Answer 4

문제가 정확히 묘사 된 경우 깊이 우선 검색과 폭 넓은 첫 번째 검색의 두 가지 옵션이 있습니다.

깊이 우선 검색은 가능한 경로를 고려하여 끝까지 (또는 허용되는 범위까지) 추적하고 다른 경로와 비교합니다.

너비가 큰 첫 번째 검색이 더 적절할 것입니다. 각 교차점에서 가능한 모든 다음 단계를 고려하고 각 단계를 수행하는 순서의 순위를 매기는 점수를 사용하십시오.이를 통해 검색의 우선 순위를 지정하고 좋은 솔루션을 더 빨리 찾을 수 있습니다 (그러나 은입니다. 깊이 우선 탐색만큼 오래 걸리고 가장 쉽게 병렬화 할 수있는 최상의 솔루션을 찾았습니다).

그러나 문제는 세부 사항에 따라 Dijkstra's algorithm에 적합 할 수도 있습니다. 그렇다면 더 나은 접근 방법입니다! (예 : 알고리즘이되지 않을 수있는, 실제로 가능 인 경우!)

이

또한 반복적 인 검색보다 훨씬 더 좋은 성능을 자신의 알고리즘을 개발하는 좋은 출발점이 될 것입니다

Answer 5

A * 플러스 플러드 필 동적 프로그래밍. 구현하기가 어렵고 간단한 게시물에서 설명하기가 너무 어렵고 미안하다. 더 제공 할 수는 없지만 홍수 채우기 및 동적 프로그래밍을 검색하면 원하는 결과를 얻을 수 있습니다. 노선.