여행하는 세일즈맨 문제는 세일즈맨과 도시 집합에 따라 발생합니다. 세일즈맨은 특정 도시(예: 고향)를 시작으로 모든 도시를 방문하고 동일한 도시로 돌아와야 합니다. 문제는 여행하는 세일즈맨이 전체 여행 기간을 최소화해야 한다는 것입니다.
문자열 연결 자바
도시가 x라고 가정하자.1엑스2.....xN어디 비용 cij도시 x에서 여행하는 데 드는 비용을 나타냅니다.나x로제이. 여행하는 판매원 문제는 x에서 시작하고 끝나는 경로를 찾는 것입니다.1최소한의 비용으로 모든 도시를 수용할 수 있습니다.
예: 신문 중개인은 매일 최소한의 이동 비용으로 해당 지역의 모든 집을 돌도록 지정된 지역에 신문을 투하합니다. 최소 여행 비용을 계산합니다.
신문을 떨어뜨려야 하는 에이전트에게 할당된 영역은 그림에 표시됩니다.
해결 방법: 그래프 G의 비용 인접 행렬은 다음과 같습니다.
비용ij=
투어는 H구역에서 시작됩니다.1H에서 도달할 수 있는 최소 비용 영역을 선택합니다.1.
마크 영역 H6H에서 도달할 수 있는 최소 비용 영역이기 때문입니다.1H에서 도달할 수 있는 최소 비용 영역을 선택합니다.6.
마크 영역 H7H에서 도달할 수 있는 최소 비용 영역이기 때문입니다.6H에서 도달 가능한 최소 비용 영역을 선택합니다.7.
마크 영역 H8H에서 도달할 수 있는 최소 비용 영역이기 때문입니다.8.
마크 영역 H5H에서 도달할 수 있는 최소 비용 영역이기 때문입니다.5.
마크 영역 H2H에서 도달할 수 있는 최소 비용 영역이기 때문입니다.2.
마크 영역 H삼H에서 도달할 수 있는 최소 비용 영역이기 때문입니다.삼.
마크 영역 H4H에서 도달할 수 있는 최소 비용 영역을 선택합니다.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에 대해.