Viajante de teletransporte, lucro ideal ao longo do tempo Problema

Question

Eu sou novo em todo o problema do Sales-Sales de Viajantes, bem como em Stackoverflow, então me avise se eu disser algo que não está certo.

Introdução:

Estou tentando codificar um algoritmo de múltiplas trades de lucro/tempo otimizado para um jogo que envolve várias cidades (nós) em vários países (áreas), onde:

• O tempo físico necessário para viajar entre duas cidades conectadas é sempre o mesmo;
• As cidades não estão linearmente conectadas (você pode se teletransportar entre algumas cidades ao mesmo tempo);
• Alguns países (áreas) têm rotas de teleporte que disponibilizam o caminho mais curto em outros países.
• O viajante (ou comerciante) tem um limite em sua purga de moedas, o peso de seus bens e a quantidade comercializável em uma certa ritmo comercial. A rota comercial pode abranger várias cidades.

---

Parâmetros de perguntas:

Já existe um banco de dados na memória (Python: Sqlite) que possui negociações com base em sua cidade de origem e sua cidade de destino, as cidades mais curtas entre os dados como uma matriz e o valor, e o fator limitante com seu % de retorno sobre o capital total (ou No caso de nenhum dos fatores ser limitantes, apenas o método que fornece o maior retorno sobre o capital total).

• Estou tentando encontrar o lucro ideal para um certo pedaço de tempo predefinido (ou seja, 30 minutos)
• O ato de atravessar uma nova cidade é realmente simultâneo
• Geralmente leva a mesma quantidade definida de tempo para viajar pelo mapa da cidade (ou seja, 2 minutos)
• O ato de iniciar o primeiro ou qualquer novo comércio leva ao mesmo tempo que atravessar um mapa da cidade (ou seja, 2 minutos)
• Meu ponto de partida pode não ter uma negociação válida (eu teria que viajar para o primeiro/mais próximo/melhor)

---

Pseudo-solução até agora

Otimização

Primeiro, percebo que, como tenho um limite no tempo que leva e sei quanto tempo cada salto leva (incluindo -1 para intriagar o comércio), posso limitar o gráfico a todos os negócios cujos saltos estão abaixo ou iguais a max_hops=int(max_time/route_time) -1. Cortei elementos do banco de dados comercial que não se enquadram nesse prazo, podando cidades que têm mais comprimentos de caminho mais curtos do que max_hops.

Faço outra entrada no banco de dados de negociações que inclui os contamis mais curtos entre minha cidade atual e as cidades iniciais de todos os negócios existentes que não são minha cidade atual e dão a eles um retorno de 0%. Eu os limitaria a onde o número de saltos da cidade é menor que max_hops, e eu também calcularia se a cidade atual para a cidade inicial mais que negocia mais curtos que seriam extinguidos max_hops e remova aqueles que superam esse limite.

Então eu pego os negócios restantes que não são (current_city->starting_city) e adicione rotas comerciais com o retorno de 0% entre todos os destinos e cidades iniciais, onde o salto não existe max_hops

Depois, faço uma última ameixa para todas as cidades que não estão no banco de dados de negociações como uma cidade inicial, cidade de destino ou parte das matrizes da cidade mais curta.

Pesquisa de gráficoFico com um (muito) gráfico menor de negócios viável dentro do prazo (ou seja, 30 minutos).

Como todos os nós conectados são adjacentes, as conexões são, por padrão, todos ponderados 1. Divido o %de retorno sobre o número de lúpulos no comércio e depois tomo o inverso e adiciono + 1 (isso significaria um peso de 1,01 para um Rota de retorno de 100%). No caso em que o retorno é de 0%, eu acrescento ... 2?

Deve então retornar a rota mais lucrativa ...

---

A questão:

Majoritariamente,

1. Como adiciono a capacidade de seguir várias rotas quando restar dinheiro ou espaço e manter a descoberta de rota através de rotas comerciais discretas para uma única única? Devido à natureza das mercadorias vendidas a vários preços e quantidades da cidade, haveria muitas rotas sobrepostas.

2. Como eu penalizo iniciar uma nova rota comercial?

3. A pesquisa de gráficos é útil nessa situação?

Em uma nota lateral,

3. Que tipos de ameixas/otimizações no gráfico devo (ou não devo) fazer?
4. Meu método de ponderação está correto? Tenho a sensação de que isso me dará pesos desproporcionais. Devo usar o retorno real em vez de retorno percentual?
5. Se estou codificando em python são bibliotecas como Python-Graph Adequado para minhas necessidades? Ou isso me economizaria muitas despesas gerais (pelo que eu entendo, os algoritmos de pesquisa de gráficos podem ser computacionalmente intensivos) para escrever uma função especializada?
6. Estou melhor usando uma* pesquisa?
7. Devo estar pré-calculando os pontos mais curtos no banco de dados do comércio e no máximo de otimizações ou devo deixar tudo para a pesquisa de gráficos?
8. Você pode notar qualquer coisa que eu pudesse melhorar?

Answer 1

Eu acho que você definiu algo que se encaixa em uma classe de problemas chamados de inventário - problemas de roteamento. Presumo que você tenha mercadorias e moedas, o viajante está comprando e vendendo ao longo da rota escolhida. Vamos primeiro supor que tudo seja determinístico - todas as quantidades de mercadorias em demanda, oferta disponíveis, preços de compra e venda, etc. são conhecidas com antecedência. A versão estocástica fica mais difícil (obviamente).

Um objetivo seria maximizar os lucros com uma restrição na bolsa e nas mercadorias. Se o viajante tiver que voltar para casa, parece um passeio, se não, parece um caminho. Como você não exigiu que o viajante visitasse todos os nó, ele não é uma TSP. Isso é bom - os problemas de caminho mais curtos geralmente são muito mais fáceis do que os TSPs para resolver.

Devido às restrições laterais e à escolha limitada das próximas etapas em cada nó - eu consideraria o uso da primeira tentativa de programação dinâmica em uma técnica de solução. Isso ajudará você a enumerar o que você compra e vende em cada estágio e há um número limitado de estágios. Além disso, porque você coloca uma restrição de tempo na decisão, isso limita o espaço de estado do estado.

Para aqueles que sugeriram o algoritmo de Djikstra - você pode estar certo - as convenções de rotulagem precisariam incluir tempo, moeda e mercadorias e lucros correspondentes. Pode ser que as suposições dos Djikstra possam não funcionar para isso com a complexidade adicional do lucro. Ainda não pensei nisso.

Aqui está um link a um problema semelhante no orçamento de capital.

Boa sorte !

Answer 2

Se este é um jogo em que você está jogando contra os seres humanos, eu presumiria que o tamanho total do espaço de dados é realmente bastante limitado. Se sim, eu estaria inclinado a jogar fora toda a poda chique, pois duvido que valha a pena.

Em vez disso, que tal uma simples pesquisa de largura?

Construa uma lista de todas as cidades, marque -as não visitadas

Pegue sua cidade inicial, marque o tempo de viagem como zero

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 (): o loop externo executa as cidades * tempos máximos de salto. O loop interno é executado uma vez por cidade. Não são necessárias alocações de memória.

Agora, para cada cidade, olhe para o que você pode comprar aqui e vender lá. Ao calcular a taxa de retorno em uma negociação, lembre -se de que o crescimento é exponencial, não linear. Duas vezes o lucro por uma negociação que leva o dobro do tempo é NÃO um bom acordo! Procure como calcular a taxa interna de retorno.

Se a cidade atual não tiver comércio, não se preocupe com a análise completa, basta examinar os vizinhos e executar a análise neles, adicionando uma ao tempo para cada movimento.

Se você tem ciclos de CPU de sobra (e você pode muito bem, qualquer coisa destinada a um humano para tocar terá um espaço de dados bem pequeno), você pode executar a análise em todas as cidades adicionando o tempo necessário para chegar à cidade.

EDIT: Com base no seu comentário, você tem toneladas de energia da CPU disponíveis, pois o jogo não está sendo executado na sua CPU. Eu mantenho minha solução: verifique tudo. Suspeito fortemente que levará mais tempo para obter as informações de rota e troca do que será calcular a solução ideal.