Qual é a maneira mais insidiosa a representar este problema?

StackOverflow https://stackoverflow.com/questions/643594

  •  22-07-2019
  •  | 
  •  

Pergunta

O meu melhor tiro até agora:

a necessidade de veículos de entrega para fazer uma série de extracções (d 1 , d 2 , ... d n ), e lata fazê-lo em qualquer ordem - em outras palavras, todas as possíveis permutações do conjunto d = {d 1 , d 2 , ... d n } são soluções válidas - mas as necessidades particulares de solução a ser determinado antes de sair da estação de base em uma extremidade do percurso (imaginar que as embalagens têm de ser carregado no veículo LIFO, por exemplo)

Além disso, o custo das várias permutações não é o mesmo. Ele pode ser calculado como a soma dos quadrados de distância percorrida entre d i -1 e d i , onde d 0 é considerado como sendo a estação de base, com a ressalva de que qualquer segmento que envolve uma mudança de direção custa 3 vezes mais (imagine isso está acontecendo em uma estrada de ferro ou de um tubo pneumático, e backup interrompe outro tráfego).

Dado o conjunto de entregas D representada como a sua distância a partir da estação de base (de modo abs(d i -d j ) é a distância entre duas partos) e uma permutations(D) iteração quais vai produzir cada permutação em sucessão, encontrar uma permutação que tem um custo menor ou igual à de qualquer outra permutação.

Agora, a execução directa a partir desta descrição pode levar a um código como este: 

function Cost(D) ...

function Best_order(D)
    for D1 in permutations(D)
        Found = true
        for D2 in permutations(D)
            Found = false if cost(D2) > cost(D1)
        return D1 if Found

O que é O (n * n! ^ 2), por exemplo, horrível -. especialmente em comparação com o O (n log (n)) alguém com visão iria encontrar, simplesmente classificando D

A minha pergunta: você pode vir para cima com uma descrição do problema plausível que conduziria naturalmente os incautos em uma implementação de pior (ou de forma diferente terrível) de um algoritmo de ordenação

Foi útil?

Solução

Eu suponho que você está usando essa questão para uma entrevista para ver se o candidato pode notar uma solução simples em uma questão aparentemente complexa.

[Esta suposição é incorreta - MarkusQ]

Você dá muita informação.

A chave para resolver este é perceber que os pontos estão em uma dimensão e que uma espécie é tudo o que é necessário. Para tornar esta questão mais difícil esconder esse fato, tanto quanto possível.

A maior pista é a fórmula de distância. Ele introduz uma penalidade para mudar de direção. A primeira coisa que um que vem à minha mente é minimizar esta penalidade. Para remover a pena eu tenho que encomendá-los em uma determinada direção, essa ordem é a ordem de classificação natural.

Gostaria de remover a penalidade para mudar de direção, é muito de dar um fora.

Outra grande dica é os valores de entrada para o algoritmo: uma lista de inteiros. Dê-lhes uma lista de permutações, ou mesmo todas permutações. Que define-los a pensar que uma O (n!) Algoritmo pode realmente ser esperado.

Eu faria frase-lo como:

Dada uma lista de todos os possíveis permutações de locais de entrega n, onde cada permutação de entregas (D 1 , d 2 , ..., d n ) tem um custo definida por:

Voltar permutação P tal que o custo de P é menos do que ou igual a quaisquer outra permutação.

Tudo o que realmente precisa ser feito é lido na primeira permutação e classificá-lo.

Se eles constroem um único circuito para comparar os custos perguntar-lhes o que o Big-O tempo de execução de seu algoritmo é onde n é o número de locais de entrega (Outra armadilha).

Outras dicas

Esta não é uma resposta direta, mas acho mais esclarecimentos é necessária.

é d i autorizados a ser negativo? Se assim for, a triagem por si só não é suficiente, tanto quanto eu posso ver.

Por exemplo:

d 0 = 0

deliveries = (-1,1,1,2)

Parece que o caminho ideal neste caso seria 1 > 2 > 1 > -1.

Edit:. Isso não pode realmente ser o caminho ideal, mas ilustra o ponto

pode refazer-lo, tendo primeiro encontrou a solução óptima, como

"Dê-me uma prova de que o seguinte convination é o mais ideal para o seguinte conjunto de regras, onde os meios óptimos o menor número resulta da soma de todos os custos do estágio, tendo em conta que todos necessidade estágios (A..Z) estar presente uma vez e apenas uma vez.

convination: 

A->C->D->Y->P->...->N

custa Stage: 

A->B = 5,
B->A = 3,
A->C = 2,
C->A = 4,
...
...
...
Y->Z = 7,
Z->Y = 24."

Isso deve manter alguém ocupado por um tempo.

Isso me faz lembrar do Knapsack problema , mais do que o Caixeiro Viajante. Mas a mochila também é um problema NP-Hard, de modo que você pode ser capaz de enganar as pessoas para pensar em uma solução mais complexa usando programação dinâmica se correlacionar o seu problema com a mochila. Onde o problema básico é:

pode ser alcançado um valor de, pelo menos, V sem exceder o W peso?

Agora o problema é uma boa solução pode ser encontrada quando V é única, suas distâncias, como tal:

O problema da mochila com cada tipo de j produto tendo um valor distinto por unidade de peso (vj = pj / wj) é considerou-se dos mais fáceis problemas NP-completos. Na verdade empírica complexidade é da ordem de O ((log n) 2) e muito grandes problemas podem ser resolvido muito rapidamente, por exemplo em 2003, o tempo médio necessário para resolver instâncias com n = 10000 era inferior a 14 milissegundos usando mercadoria pessoal computadores 1 .

Então você pode querer estado que várias paragens / pacotes podem compartilhar o mesmo vj, convidando as pessoas a pensar sobre a solução realmente difícil:

No entanto, no caso degenerado de vários itens compartilhando o mesmo valor vj torna-se muito mais difícil com a extrema caso em que vj = constante sendo o problema soma subconjunto com uma complexidade de O (2N / 2N).

Então, se você substituir o peso por valor à distância por valor, e afirmam que várias distâncias pode realmente compartilham os mesmos valores, degenerada, algumas pessoas podem cair nesta armadilha.

Não é este apenas o (NP-Hard) Problema do Caixeiro Viajante ? Não parece provável que você está indo para torná-lo muito mais difícil.

Talvez fraseado o problema para que o algoritmo real é claro - por exemplo, descrevendo os caminhos como linhas ferroviárias de trilho único para que a pessoa teria de inferir a partir do conhecimento de domínio que o retrocesso é mais caro.

E descrevendo a questão de maneira tal que alguém está tentado a fazer comparações recursiva - por exemplo, "Você pode acelerar o algoritmo usando o subconjunto máximo ideal de seus melhores (até agora) resultados"?

BTW, qual é o propósito desta - parece que a intenção é a de torturar entrevistados.

Você precisa ser mais clara sobre se o caminhão de entrega tem que voltar à base (tornando-se uma ida e volta), ou não. Se o caminhão faz retorno, em seguida, uma espécie simples não produzir a rota mais curta, porque o quadrado do retorno do ponto mais distante para os custos de base tanto. Faltando alguns saltos no caminho 'out' e usá-los no caminho de volta acaba por ser mais barato.

Se você enganar alguém em uma resposta ruim (por exemplo, não dando-lhes todas as informações), então, é a sua loucura ou a sua decepção que causou isso?

Como é grande a sabedoria dos sábios, se eles acatam mentiras não do seu ego?

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top