여행하는 판매원 문제
여행하는 세일즈맨 문제는 세일즈맨과 도시 집합에 따라 발생합니다. 세일즈맨은 특정 도시(예: 고향)를 시작으로 모든 도시를 방문하고 동일한 도시로 돌아와야 합니다. 문제는 여행하는 세일즈맨이 전체 여행 기간을 최소화해야 한다는 것입니다.
도시가 x라고 가정하자. 1 엑스 2 .....x N 어디 비용 c ij 도시 x에서 여행하는 데 드는 비용을 나타냅니다. 나 x로 제이 . 여행하는 판매원 문제는 x에서 시작하고 끝나는 경로를 찾는 것입니다. 1 최소한의 비용으로 모든 도시를 수용할 수 있습니다.
예: 신문 중개인은 매일 최소한의 이동 비용으로 해당 지역의 모든 집을 돌도록 지정된 지역에 신문을 투하합니다. 최소 여행 비용을 계산합니다.
신문을 떨어뜨려야 하는 에이전트에게 할당된 영역은 그림에 표시됩니다.
해결 방법: 그래프 G의 비용 인접 행렬은 다음과 같습니다.
비용 ij =
투어는 H구역에서 시작됩니다. 1 H에서 도달할 수 있는 최소 비용 영역을 선택합니다. 1 .
마크 영역 H 6 H에서 도달할 수 있는 최소 비용 영역이기 때문입니다. 1 H에서 도달할 수 있는 최소 비용 영역을 선택합니다. 6 .
마크 영역 H 7 H에서 도달할 수 있는 최소 비용 영역이기 때문입니다. 6 H에서 도달 가능한 최소 비용 영역을 선택합니다. 7 .
마크 영역 H 8 H에서 도달할 수 있는 최소 비용 영역이기 때문입니다. 8 .
마크 영역 H 5 H에서 도달할 수 있는 최소 비용 영역이기 때문입니다. 5 .
마크 영역 H 2 H에서 도달할 수 있는 최소 비용 영역이기 때문입니다. 2 .
마크 영역 H 삼 H에서 도달할 수 있는 최소 비용 영역이기 때문입니다. 삼 .
마크 영역 H 4 H에서 도달할 수 있는 최소 비용 영역을 선택합니다. 4 그것은 H이다 1 .그리디 전략을 사용하면 다음과 같은 결과를 얻습니다.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
따라서 최소 여행 비용 = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
매트로이드:
매트로이드는 다음 조건을 만족하는 순서쌍 M(S, I)입니다.
- S는 유한집합이다.
- I는 B ∈ I이고 A ∈ I인 S의 독립 부분 집합이라고 불리는 비어 있지 않은 S 부분 집합의 계열입니다. 이 속성을 충족하면 I가 유전적이라고 말합니다. 공집합 ∅는 반드시 I의 구성원이라는 점에 유의하세요.
- A ∈ I, B ∈ I 및 |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
각 요소 x ∈ S에 엄격하게 양의 가중치 w(x)를 할당하는 관련 가중치 함수 w가 있는 경우 매트로이드 M(S, I)에 가중치가 부여된다고 말합니다. 가중치 함수 w는 합산을 통해 S의 하위 집합으로 확장됩니다. :
w (A) = ∑<sub>x∈A</sub> w(x)
A ∈ S에 대해.
