여행자 순간 이동, 시간에 따른 최적의 이익 문제

Question

나는 여행사 전체를 처음 사용하고 Stackoverflow를 처음 사용하므로 옳지 않은 것을 말하면 알려주십시오.

소개 :

여러 국가 (영역) 내에서 여러 도시 (노드)를 포함하는 게임에 대한 이익/시간 최적화 된 다중 거래 알고리즘을 코딩하려고합니다.

• 연결된 두 도시를 여행하는 데 걸리는 물리적 시간은 항상 동일합니다.
• 도시는 선형으로 연결되어 있지 않습니다 (동시에 일부 도시간에 순간 이동할 수 있음).
• 일부 국가 (지역)에는 다른 국가를 통해 가장 짧은 경로를 제공하는 순간 이동 경로가 있습니다.
• 여행자 (또는 상인)는 그의 동전-urse, 상품의 무게 및 특정 무역 경로에서 거래 할 수있는 수량에는 한계가 있습니다. 무역 경로는 여러 도시에 걸쳐있을 수 있습니다.

---

질문 매개 변수 :

이미 메모리에 데이터베이스 (Python : SQLite)가 존재하는데, 이는 소스 도시와 목적지 도시, 배열 및 금액 사이의 가장 짧은 경로 도시, 총 자본에 대한 비율의 제한 요인 (또는)이 있습니다. 요인이 제한되지 않는 경우, 총 자본에서 가장 높은 수익을 제공하는 방법 만 있습니다).

• 나는 특정 사전 설정된 시간 덩어리 (즉, 30 분) 동안 최적의 이익을 찾으려고 노력하고 있습니다.
• 새로운 도시로 건너는 행위는 실제로 동시에
• 도시지도를 가로 질러 여행하는 데 일반적으로 동일한 정의 된 시간이 걸립니다 (예 : 2 분)
• 첫 번째 또는 새로운 무역을 시작하는 행위는 한 도시지도를 건너는 것과 같은 시간이 걸립니다 (예 : 2 분)
• 내 출발점은 실제로 유효한 거래가 없을 수 있습니다 (첫 번째/가장 가까운/최고/최고로 여행해야합니다).

---

지금까지 의사 솔루션

최적화

먼저, 나는 시간이 걸리는 시간이 제한되어 있기 때문에 각 홉이 얼마나 오래 걸리는지 알고 있기 때문에 (무역 강화를위한 -1 포함), 홉이 아래에 있거나 같은 모든 거래에 그래프를 제한 할 수 있습니다. max_hops=int(max_time/route_time) -1. 나는이 시간 제한 내에 속하지 않는 무역 데이터베이스의 요소를 삭감하고, 길이가 가장 짧은 도시는 max_hops.

나는 현재 도시와 현재 도시가 아닌 모든 기존 거래의 시작 도시 사이의 가장 짧은 경로를 포함하는 Trades 데이터베이스에 또 다른 진입을하고 0%의 수익을줍니다. 나는 이것을 도시 홉의 수가보다 작은 곳으로 제한 할 것입니다. max_hops, 그리고 나는 또한 현재 도시가 출발 도시로, 가장 짧은 경로-홀을 거래하는 도시를 낙태 할 것인지 계산할 것입니다. max_hops 이 한계를 실행 한 것을 제거하십시오.

그런 다음 나머지 거래를합니다 (current_city->starting_city) 그리고 모든 목적지와 시작 도시 사이에 0%의 수익을 가진 무역 경로를 추가합니다. max_hops

그런 다음 트레이드 데이터베이스에없는 모든 도시에 시작 도시, 목적지 도시 또는 가장 짧은 Path City Array의 일부로 마지막 자두를 만듭니다.

그래프 검색나는 시간 제한 (예 : 30 분) 내에 가능한 더 작은 거래 그래프를 남겼습니다.

연결된 모든 노드는 인접 해 있기 때문에 연결은 기본적으로 모든 가중치입니다. 1은 거래의 홉 수에 대한 %수익을 나누고 역전을 취하고 + 1을 추가합니다 (이것은 100% 반품 경로). 반품이 0%인 경우, 나는 ... 2를 추가합니까?

그런 다음 가장 수익성있는 경로를 반환해야합니다 ...

---

질문:

주로,

1. 돈이나 공간을 떠났을 때 여러 경로를 취하고 단일 무역 경로로 이산 된 경로를 통해 경로 찾기를 유지하는 능력을 추가하려면 어떻게해야합니까? 도시 내에서 여러 가격과 수량으로 판매되는 상품의 특성으로 인해 많은 겹치는 경로가있을 것입니다.

2. 새로운 무역 경로 시작을 어떻게 처벌합니까?

3. 이 상황에서 그래프 검색이 유용합니까?

참고로,

3. 그래프에 어떤 종류의 자두/최적화를 만들어야합니까?
4. 내 가중치가 맞습니까? 나는 그것이 나에게 불균형적인 무게를 줄 것이라고 생각한다. 백분율 수익 대신 실제 수익을 사용해야합니까?
5. Python에서 코딩하는 경우 라이브러리는 다음과 같은 라이브러리입니다. 파이썬 그래프 내 필요에 적합합니까? 아니면 전문적인 기능을 작성하기 위해 많은 오버 헤드를 절약 할 수 있습니까?
6. * 검색을 사용하는 것이 가장 좋습니다.
7. 거래 데이터베이스에서 가장 짧은 경로 지점을 미리 계산하고 최적화 최적화를 최대화해야합니까, 아니면 그래프 검색에 모두 맡겨야합니까?
8. 내가 개선 할 수있는 것을 알 수 있습니까?

Answer 1

나는 당신이 재고 - 라우팅 문제라고 불리는 일련의 문제에 맞는 것을 정의했다고 생각합니다. 나는 당신이 상품과 동전을 모두 가지고 있기 때문에, 여행자는 선택한 경로를 따라 구매하고 판매하고 있다고 생각합니다. 먼저 모든 것이 결정적이라고 가정 해 봅시다. 모든 수요의 수요, 공급, 구매 및 판매 가격 등이 미리 알려져 있습니다. 확률 론적 버전은 더 어려워집니다.

한 가지 목표는 지갑과 상품에 대한 제약으로 이익을 극대화하는 것입니다. 여행자가 집으로 돌아와야한다면 투어처럼 보입니다. 그렇지 않은 경우 경로처럼 보입니다. 여행자가 모든 노드를 방문 할 필요가 없었기 때문에 TSP가 아닙니다. 좋은 경로 문제는 일반적으로 TSP보다 훨씬 쉽습니다.

측면 제약 조건과 각 노드에서 다음 단계의 제한된 선택으로 인해 솔루션 기술에서 동적 프로그래밍 첫 번째 시도를 고려합니다. 각 단계에서 사고 판매하는 것을 열거하고 제한된 수의 단계가 있습니다. 또한 결정에 시간 제약 을가하기 때문에 상태 선택의 공간을 제한합니다.

Djikstra의 알고리즘을 제안한 사람들에게 - 당신이 옳을 수도 있습니다 - 라벨링 컨벤션에는 시간, 동전 및 상품 및 해당 이익이 포함되어야합니다. Djikstra의 가정은 이익의 복잡성이 추가되어이를 위해 효과가 없을 수도 있습니다. 아직 그것에 대해 생각하지 않았습니다.

여기에 있습니다 링크 자본 예산 책에서 비슷한 문제로.

행운을 빕니다 !

Answer 2

이것이 당신이 인간과 대결하는 게임이라면 나는 데이터 공간의 총 크기가 실제로 상당히 제한되어 있다고 가정합니다. 그렇다면 나는 그만한 가치가 있다고 의심하는 모든 멋진 가지 치기를 버리는 경향이 있습니다.

대신, 간단한 폭이 먼저 검색되는 것은 어떻습니까?

모든 도시 목록을 구축하고 방문하지 않은 표시

출발 도시를 타고 여행 시간을 0으로 표시하십시오.

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

O () : 외부 루프는 도시를 실행합니다 * 최대 홉 시간. 내부 루프는 도시당 한 번에 실행됩니다. 메모리 할당이 필요하지 않습니다.

이제 각 도시가 여기에서 구입할 수있는 것을 살펴보고 그곳에서 팔 수 있습니다. 무역 수익률을 파악할 때 성장은 선형이 아니라 지수임을 기억하십시오. 두 배나 긴 거래의 이익은 두 배입니다. 아니다 좋은 거래! 내부 수익률을 계산하는 방법을 찾으십시오.

현재 도시가 무역이없는 경우 전체 분석을 귀찮게하지 않으면 이웃을 살펴보고 대신 분석을 실행하여 각 이동 시간에 하나를 추가하십시오.

여분의 CPU 사이클이 있다면 (그리고 당신이 잘 할 수도 있습니다., 인간이 플레이하는 것이 꽤 작은 데이터 공간을 가질 것입니다) 도시에 도착하는 데 걸리는 시간에 모든 도시에서 분석을 실행할 수 있습니다.

편집 : 의견을 바탕으로 게임이 CPU에서 실행되지 않으므로 수많은 CPU 전원이 있습니다. 나는 내 해결책을지지한다 : 모든 것을 확인하십시오. 최적의 솔루션을 계산하는 것보다 경로와 거래 정보를 얻는 데 시간이 더 걸릴 것이라고 강력하게 생각합니다.