Undirected Graphs

Question

Java를 사용하여 작업하려하지만 다음 그래프의 노드를 설정하는 방법에 대해 혼란스러워합니다. 기본적으로 펜 플로터 문제이거나 여행 판매원 문제로 더 일반적으로 알려져 있습니다.

Line between 4 1 and 4 4  
Line between 4 4 and 4 7  
Line between 2 6 and 4 4 
Line between 4 4 and 6 2 
Line between 6 6 and 4 4 
Line between 2 2 and 4 4 

내 출력으로 나온다 : 어디에 다음과 같은 입력은 종이 조각의 왼쪽 아래에, 당신의 시작 (0,0) 및 될 것이라고 가정

<n> nodes explored 
cost = 24.61 
Move from 0 0 to 2 2 
Draw from 2 2 to 4 4 
Draw from 4 4 to 6 6 
Move from 6 6 to 4 7 
Draw from 4 7 to 4 4 
Draw from 4 4 to 4 1 
Move from 4 1 to 6 2 
Draw from 6 2 to 4 4 
Draw from 4 4 to 2 6 

그것은 좌표로 올라가고, 각 좌표는 노드이며, 어떻게 이동하고 선을 그리는지를 결정할 것입니다. 나는 A와 함께 무향 그래프를 사용해야 만한다는 것을 알고 있습니다. 그러나 어떤 것들이 노드 (정점)인지에 대해 여전히 혼란 스럽습니다. 그리고 언제 움직이는 지, 언제 선을 그릴지를 결정할 때 누군가 조언을 해줄 수 있습니까?

편집 : 전체 검색에서 탐색 된 노드의 수/개수를 나타냅니다.

Answer 1

A *를 사용하려면 먼저 admissible heuristic function이 필요합니다. [이 답변의 끝에는 설명이 첨부되어 있습니다]. A에 대한 그래프로서

가

문제점 : *
정의 그래프로서 G = (V, E)되도록 :
V={all possible drawings prefixes} [즉 가능한 모든 추첨의 모든 가능한 '스냅 샷']. 이 그래프는 메모리에 저장하지 말고 나중에 작성하는 next()으로 즉시 작성해야합니다. [실제로 각 상태에 대해 실제로 저장할 위치는 (1) 펜이 현재 어디에 있는지 (2) 이미 그려져있는 위치의 라인이 무엇입니까?]
E={all possible changes from one 'snap shot' to another}
[가중치 함수]가 필요합니다. w(point1,point2)=euclidian_distance(point1,point2)

또한 next:V->P(V)을 정의해야합니다 : next(v)={all snap shots you can get from v, using exactly one move/draw
마지막으로, 당신은 또한 F을 정의해야합니다 : 모든 상태를 "종료". F={all the prefixes which all the lines are drawn}

A * 실행하는 방법 : 당신의 펜 (0,0) 인 스냅 샷에서
시작하고, 더 라인 [이 초기 상태] 그려되지 않으며, 당신이 하나를 찾을 때까지 계속 최종 상태.당신이 할 때 발견이 유효한 경우 A *가 admissible and optimized

(*) 허용 휴리스틱 기능이 있기 때문에, 당신은 최적화 된 솔루션을 가지고 보장됩니다. 정점 V에서 h*(v)=real distance to target하자

휴리스틱 함수 h : V

당신의 진짜 도전
의 각 V에 대한 h(v)<=h*(v)는 TSP에 대한 어려운 부분은 허용 h을 찾는 경우 V-> R은 허용입니다. 최단 경로가 무엇인지 전혀 알지 못하기 때문에 매우 어렵습니다. 경험적 기능이 허용되지 않는 경우 발견 된 솔루션이 최적화 될 것이라는 보장이 없습니다.

제안

:이 비슷한을했을 때이
당신은 어떤 any time algorithm을 사용할 수 있습니다, [여러 에이전트와 해결 TSP] 나는 또한 A *를 사용하지만, 비 유효 발견으로 시작하고, 반복적으로 감소 시간이 충분하면 최적의 솔루션을 찾았고 그렇지 않다면 찾을 수있는 최상의 솔루션을 반환했습니다.

Answer 2

해결하려는 문제가 NP Hard이므로, 여행하는 세일즈맨 문제를 해결할 효율적인 방법이 없습니다. 먼저해야 할 일은 모든 꼭지점 쌍 (from과 from)을 ArrayList에 저장하고 필요에 따라 사용하는 것입니다.

언제 이동해야합니까?
한 지점에 있고 ArrayList에 시작 노드가없는 경우 배열의 다음 요소를 선택하여 이동해야합니다.

그릴 때 :
추첨은 두 가지 상황에서 발생할 수 있습니다. 특정 지점으로 이동하면 추첨이 이어집니다. 또한 선 끝점이 ArrayList에 시작점으로 존재할 때 그리기가 발생합니다.

그릴 때마다 ArrayList에서 특정 선분을 제거해야합니다. 버켓에 다른 것을 가지고 있지 않으면 프로그램을 멈추게됩니다.