Qual è il modo più insidioso di porre questo problema?

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

  •  22-07-2019
  •  | 
  •  

Domanda

Il mio scatto migliore finora:

  

Un veicolo di consegna deve effettuare una serie di consegne (d 1 , d 2 , ... d n ) e può fallo in qualsiasi ordine - in altre parole, tutte le possibili permutazioni dell'insieme D = {d 1 , d 2 , ... d n } sono soluzioni valide - ma la soluzione particolare deve essere determinata prima di lasciare la stazione base a un'estremità del percorso (immagina che i pacchi debbano essere caricati nel veicolo LIFO, per esempio).

     

Inoltre, il costo delle varie permutazioni non è lo stesso. Può essere calcolato come la somma dei quadrati della distanza percorsa tra d i -1 e d i , dove d 0 è considerato la stazione base, con l'avvertenza che ogni segmento che comporta un cambio di direzione costa 3 volte di più (immagina che questo accada su una ferrovia o un tubo pneumatico e il backup interrompe l'altro traffico).

     

Dato l'insieme di consegne D rappresentato come distanza dalla stazione base (quindi abs(di -d j ) è la distanza tra due consegne) e un iteratore permutazioni (D) che produrrà ogni permutazione in successione, trova un permutazione che ha un costo inferiore o uguale a quello di qualsiasi altra permutazione.

Ora, un'implementazione diretta da questa descrizione potrebbe portare a un codice come questo: 

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

Che è O (n * n! ^ 2), ad es. piuttosto terribile - specialmente se paragonato a O (n log (n)) troverebbe qualcuno con intuito, semplicemente ordinando D.

La mia domanda: puoi fornire una descrizione plausibile del problema che indurrebbe naturalmente gli incauti a implementare un peggio (o diversamente terribile) di un algoritmo di ordinamento?

È stato utile?

Soluzione

Suppongo che tu stia usando questa domanda per un colloquio per vedere se il richiedente può notare una soluzione semplice in una domanda apparentemente complessa.

[Questo presupposto non è corretto - MarkusQ]

Fornisci troppe informazioni.

La chiave per risolverlo è rendersi conto che i punti sono in una dimensione e che è richiesto solo un ordinamento. Per rendere questa domanda più difficile, nascondere questo fatto il più possibile.

L'indizio più grande è la formula della distanza. Introduce una penalità per il cambio di direzione. La prima cosa che mi viene in mente è minimizzare questa penalità. Per rimuovere la penalità devo ordinarli in una certa direzione, questo ordinamento è il naturale ordinamento.

Vorrei rimuovere la penalità per il cambio di direzione, è troppo un regalo.

Un altro indizio importante sono i valori di input per l'algoritmo: un elenco di numeri interi. Fornisci loro un elenco di permutazioni o anche tutte permutazioni. Ciò li induce a pensare che un algoritmo O (n!) Potrebbe effettivamente essere previsto.

Lo definirei come:

  

Dato un elenco di tutti i possibili   permutazioni di n luoghi di consegna,   dove ogni permutazione delle consegne   (d 1 , d 2 , ...,   d n ) ha un costo definito da:

     

     

Permutazione di ritorno P tale che il   il costo di P è inferiore o uguale a qualsiasi   altra permutazione.

Tutto ciò che deve davvero essere fatto è letto nella prima permutazione e lo ordina.

Se costruiscono un singolo ciclo per confrontare i costi, chiedi loro quale è il runtime big-o del loro algoritmo dove n è il numero di posizioni di consegna (Un'altra trappola).

Altri suggerimenti

Questa non è una risposta diretta, ma penso che siano necessari ulteriori chiarimenti.

D i può essere negativo? In tal caso, l'ordinamento da solo non è sufficiente, per quanto posso vedere.

Ad esempio:

d 0 = 0

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

Sembra che il percorso ottimale in questo caso sia 1 > 2 > 1 > -1 .

Modifica: questo potrebbe non essere il percorso ottimale, ma illustra il punto.

È possibile riformularlo, avendo prima trovato la soluzione ottimale, come

" Dammi una prova che la seguente convinzione è la più ottimale per il seguente insieme di regole, dove ottimale significa che il numero più piccolo risulta dalla somma di tutti i costi di fase, tenendo conto del fatto che tutte le fasi (A ..Z) deve essere presente una volta e una volta sola.

Convination: 

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

Costi dello stage: 

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

Questo dovrebbe tenere qualcuno occupato per un po '.

Questo mi ricorda il Problema zaino , più che il commesso viaggiatore. Ma lo zaino è anche un problema NP-difficile, quindi potresti essere in grado di ingannare le persone a pensare a una soluzione troppo complessa usando la programmazione dinamica se correlano il tuo problema con lo zaino. Dove si trova il problema di base:

  

è possibile ottenere un valore di almeno V   senza superare il peso W?

Ora il problema è che una soluzione abbastanza buona può essere trovata quando V è unica, le tue distanze, in quanto tali:

  

Il problema dello zaino con ogni tipo di   l'articolo j ha un valore distinto per   unità di peso (vj = pj / wj) è   considerato uno dei più facili   Problemi NP-completi. Anzi empirico   la complessità è dell'ordine di O ((log   n) 2) e possono esserci problemi molto grandi   risolto molto rapidamente, ad es. nel 2003 il   tempo medio necessario per la risoluzione   le istanze con n = 10.000 erano inferiori a 14   millisecondi usando merce personale   computer 1 .

Quindi potresti voler affermare che diverse fermate / pacchetti potrebbero condividere lo stesso vj, invitando le persone a pensare alla soluzione davvero difficile per:

  

Comunque in   caso degenerato di più elementi   condividendo lo stesso valore vj diventa   molto più difficile con l'estremo   caso in cui vj = costante è il   problema di somma di sottoinsieme con una complessità   di O (2N / 2N).

Quindi, se si sostituisce il peso per valore alla distanza per valore e si afferma che diverse distanze potrebbero effettivamente condividere gli stessi valori, degenerare, alcune persone potrebbero cadere in questa trappola.

Non è solo questo (NP-Hard) Problema del commesso viaggiatore ? Non sembra probabile che lo renderai molto più difficile.

Forse è necessario formulare il problema in modo che l'algoritmo effettivo non sia chiaro - ad es. descrivendo i percorsi come linee ferroviarie a binario singolo in modo che la persona dovrebbe dedurre dalla conoscenza del dominio che il backtracking è più costoso.

Che dire della descrizione della domanda in modo tale che qualcuno sia tentato di fare confronti ricorsivi - ad es. " puoi velocizzare l'algoritmo usando il sottoinsieme massimo ottimale dei tuoi migliori (finora) risultati " ;?

A proposito, qual è lo scopo di questo - sembra che l'intenzione sia quella di torturare gli intervistati.

Devi essere più chiaro se il camion di consegna deve tornare alla base (rendendolo un viaggio di andata e ritorno) o no. Se il camion ritorna , un semplice ordinamento non produce il percorso più breve, perché il quadrato del ritorno dal punto più lontano alla base costa così tanto. Perdere alcuni salti sulla via "fuori" e usarli sulla via del ritorno risulta essere più economico.

Se induci qualcuno a dare una cattiva risposta (ad esempio, non dando loro tutte le informazioni), è stata la loro follia o il tuo inganno a causarla?

Quanto è grande la saggezza dei saggi, se non ascoltano le bugie del loro ego?

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top