tsp 알고리즘

: Traveling Salesman Problem

조합 최적화 문제의 일종

 

알고리즘의 배경

- 여러 지역을 돌면서 물건을 판매하는 판매원이 모든 지역을 돌고 다시 출발점으로 돌아와야한다고 할 때, 가장 최적의 경로를 찾는 문제

 

조건) 모든 노드를 방문해야함

          최단 경로여야함

---

https://dayofday.tistory.com/89

[자료구조] 6장 실습 kruskal, prim, sollin

https://dayofday.tistory.com/88

[자료구조] 6장 개념&코드 정리

+ shortest path 자료구조

 

---

게임 진행 방식 1) 시작점으로부터 모든 노드 방문 (원판원 X)

(가변 부분)

1. 우리가 위와 같은 노드와 각 노드 사이 이동비용이 적힌 루트를 공개

2. 각 조마다 적절한(20분?)의 시간동안 위 노드들의 최소 비용 루트를 결정함 => 적절한 이유와 함께

-시작점 자유

-ex) 노드 개수 7개라면 총 6번의 이동 time 존재

3. 각 time 동안 조마다 자신들의 루트에 따라 이동 //사탕 개수 default x개 배정

3-1. 마주치는 조들 중 자신들의 루트의 최소 비용이 더 적은 조가 win => 진 조 사탕 압수 ?

4번이 있으니최소비용보다는 정준이가 말했듯 가위바위보 정도로 간단하게 하는 것도 좋을 듯 (=팀원 전원 승)

4. 각 조의 최소 비용 & 전체 사탕의 개수를 가지고 1등 조 선별 => 최소 비용에 가중치 부여 or 사탕 개수에 가산점 부여

 

 

> 컴페가 게임 진행 전 할 일

=> 최소 비용 루트 계산해두기 

=> 사탕 / 분장 준비

=> 디폴트 사탕 개수 정해두기

=> 점수 산출 방법 확정해두기

 

> 컴페가 게임 진행 (중/후) 할 일

=> 각 조의 루트 최소 비용 입수?

=> 각 조의 사탕 개수 취합

 

근데 이렇게 진행되려면 최소비용 알고리즘을 미리 알려주지 않는 것이 게임 진행이 될 듯

=> 알려주면 같은 루트인 조들이 나올 것

아니면 위 알고리즘 방법들을 알려주고,, 각자 시작점을 다르게 배정해주면 그나마 각 조마다 다른 루트가 나오긴 할 듯

---

보완한 내용 9/19 

시작점에 따라 루트가 같을 순 있어도 도는 순서가 다르니 ㄱㅊ을 거 같고,,,

-시작점을 각 조마다 다르게 주고 각자 알아서 최소 비용 루트 찾아가라 //우리가 최소비용 루트 알고리즘 몇개를 알려줄지 말지

//이때 각 조마다 최소 비용 찾는 시간을 좀 줘야겠지 아무래도..? 아님 그냥 냅다 시작하고 마지막에 사실 이런 최소비용 알고리즘에는 이런것들이 있어요~~라고 할까.. 코딩짜는 거라 알고리즘 이론은  진짜 간단한것들 많긴 한디..

-한 타임에 한 노드씩 이동하며 각 타임 이동시간에 만난 팀들 대결

//각 팀당 최소 사탕 수를 정하던 해야함 (최소 사탕수, 각 이동시간마다 졌을 경우 상대에게 줄 사탕 수)

-결과 판단 법 : 최소비용 루트인가 => 점수 a점 부여

                       사탕 수 많은 순으로 점수 부여 

사탕 수 많은 순으로 비중을 많이 둘지 아님 최소 비용 루트를 잘 찾은 조들에게 큰 가산점을 줄지

//즉 학습,,?쪽에 영향을 많이 둘지 아님 그냥 노는데 요점을 둘지..?

 

각 시작점에 따라 어떤 조들은 겁나 많이 마주치고 어떤 조들은 하나도 안 마주치면 우짜지.. 아직 귀찮아서 시뮬 안돌려봄 이따 시간 나면 돌려봐여지  ㅎㅅㅎ

만약에 이대로 진행한다면 저 루트 그대로 해도 될 거 같기도 하고,, 어디서 인원 한명만 델꾸와서 땜빵해주신다묜..