Quelle est la manière la plus insidieuse de poser ce problème?

Question

Mon meilleur coup jusqu'à présent:

  

Un véhicule de livraison doit effectuer une série de livraisons (d ₁ , d ₂ , ... d _n ) et peut faites-le dans n'importe quel ordre - autrement dit, toutes les permutations possibles de l'ensemble D = {d 1 , d 2 , ... d n } sont des solutions valables - mais la solution doit être déterminée avant de quitter la station de base située à une extrémité de la route (imaginez par exemple que les packages doivent être chargés dans le véhicule LIFO du véhicule).

     

De plus, le coût des différentes permutations n’est pas le même. Il peut être calculé comme la somme des carrés de distance parcourue entre d _{i -1} et d _i , où d ₀ est pris pour la station de base, avec l’avertissement que tout segment impliquant un changement de direction coûte 3 fois plus cher (imaginez que cela se passe sur un chemin de fer ou un tube pneumatique, et que la marche arrière perturbe les autres types de trafic).

     

Étant donné l'ensemble des diffusions D représentées par leur distance à la station de base (donc abs (d _i -d _j ) est la distance entre deux diffusions) et un itérateur permutations (D) qui produira chaque permutation successivement, trouvez un permutation qui a un coût inférieur ou égal à celui de toute autre permutation.

Une implémentation directe à partir de cette description peut conduire à un code comme celui-ci:

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

Qui est O (n * n! ^ 2), par ex. assez affreux - surtout par rapport au O (n log (n)), trouverait quelqu'un avec un aperçu en triant simplement D.

Ma question: pouvez-vous proposer une description plausible du problème qui conduirait naturellement les imprudents vers une implémentation pire (ou autrement horrible) d'un algorithme de tri?

Answer 1

Je suppose que vous utilisez cette question pour un entretien afin de voir si le demandeur peut remarquer une solution simple dans une question apparemment complexe.

[Cette hypothèse est incorrecte - MarkusQ]

Vous donnez trop d'informations.

Pour résoudre ce problème, il est essentiel de comprendre que les points sont dans une dimension et qu’un tri est tout ce qui est requis. Pour rendre cette question plus difficile, cachez ce fait autant que possible.

Le plus gros indice est la formule de distance. Il introduit une pénalité pour changer de direction. La première chose qui me vient à l’esprit est de minimiser cette pénalité. Pour supprimer la pénalité, je dois les ordonner dans une certaine direction. Cet ordre est l’ordre de tri naturel.

Je supprimerais la pénalité pour changement de direction, c'est trop risqué.

Un autre indice important est les valeurs d’entrée de l’algorithme: une liste d’entiers. Donnez-leur une liste de permutations, ou même toutes . Cela les incite à penser qu’un algorithme O (n!) Pourrait effectivement être attendu.

Je le formulerais comme suit:

  

Avec une liste de tous les possibles   permutations de n lieux de livraison,   où chaque permutation des livraisons   (d ₁ , d ₂ , ...,   d _n ) a un coût défini par:

     

     

Retourne la permutation P telle que la   le coût de P est inférieur ou égal à tout   autre permutation.

Tout ce qui reste à faire est lu dans la première permutation et trié.

S'ils construisent une seule boucle pour comparer les coûts, demandez-leur quelle est la durée d'exécution de leur algorithme où n est le nombre d'emplacements de livraison (un autre piège).

Answer 2

Ce n'est pas une réponse directe, mais je pense qu'il faut clarifier davantage.

D _i est-il autorisé à être négatif? Si tel est le cas, le tri ne suffit pas, à ma connaissance.

Par exemple:

d ₀ = 0

deliveryies = (-1,1,1,2)

Il semble que le chemin optimal dans ce cas serait 1 > 2 > 1 > -1 .

Éditer: ce n'est peut-être pas le chemin optimal, mais cela illustre le point.

Answer 3

Vous pourriez le reformuler, après avoir trouvé la solution optimale, comme

"Donnez-moi la preuve que la combinaison suivante est la plus optimale pour l'ensemble de règles suivant, où optimal signifie que le plus petit nombre résulte de la somme de tous les coûts de l'étape, en tenant compte du fait que toutes les étapes (A ..Z) doit être présent une fois et une fois seulement.

Conviction:

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

Coûts de la scène:

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

Cela devrait garder quelqu'un occupé pendant un moment.

Answer 4

Cela me rappelle le problème de sac à dos , plus important que le voyageur de commerce. Mais le sac à dos est aussi un problème NP-difficile, vous pouvez donc être en mesure de duper les gens en leur proposant une solution complexe utilisant une programmation dynamique s’ils corrèlent votre problème avec le sac à dos. Où le problème de base est:

  

peut-on atteindre une valeur d'au moins V   sans dépasser le poids W?

Le problème est qu’une bonne solution peut être trouvée lorsque V est unique, vos distances, en tant que telles:

  

Le problème de sac à dos avec chaque type de   l'article j ayant une valeur distincte par   unité de poids (vj = pj / wj) est   considéré comme l'un des plus faciles   NP-complet des problèmes. En effet empirique   la complexité est de l'ordre de O ((log   n) 2) et de très gros problèmes peuvent être   résolu très rapidement, par exemple en 2003 la   temps moyen nécessaire pour résoudre   cas avec n = 10 000 était inférieur à 14   millisecondes en utilisant un produit personnel   ordinateurs 1 .

Donc, vous voudrez peut-être indiquer que plusieurs arrêts / packages peuvent partager le même vj, invitant les gens à réfléchir à la solution vraiment difficile à:

  

Cependant dans le   cas dégénéré de plusieurs éléments   partageant la même valeur vj il devient   beaucoup plus difficile à l'extrême   cas où vj = constant étant le   problème de somme partielle avec une complexité   de O (2N / 2N).

Donc, si vous remplacez le poids par valeur par la distance par valeur et déclarez que plusieurs distances peuvent effectivement partager les mêmes valeurs, dégénérées, certaines personnes risquent de tomber dans ce piège.

Answer 5

N’est-ce pas juste le (NP-Hard) problème de voyageur de commerce ? Il semble peu probable que vous rendiez les choses beaucoup plus difficiles.

Peut-être formulons-nous le problème de manière à ce que l’algorithme actuel ne soit pas clair - par exemple. en décrivant les chemins comme des lignes de chemin de fer mono-rail, de sorte que la personne doit déduire de la connaissance du domaine que le retour en arrière est plus coûteux.

Pourquoi ne pas décrire la question de manière à ce que quelqu'un soit tenté de faire des comparaisons récursives - par ex. "pouvez-vous accélérer l'algorithme en utilisant le sous-ensemble optimal optimal de vos meilleurs résultats (jusqu'à présent)"?

BTW, quel est le but de tout cela? On dirait que l'intention est de torturer les personnes interrogées.

Answer 6

Vous devez préciser si le camion de livraison doit retourner à la base (aller-retour) ou non. Si le camion retourne , un tri simple ne produira pas l'itinéraire le plus court, car le carré du retour entre le point le plus éloigné et le prix de base coûte trop cher. Manquer quelques sauts en route et les utiliser au retour s'avère moins cher.

Si vous trompez quelqu'un en lui donnant une mauvaise réponse (par exemple, en ne lui donnant pas toutes les informations), est-ce que c'est sa bêtise ou votre déception qui l'a provoquée?

Quelle est la force de la sagesse des sages s'ils ne prêtent pas attention aux mensonges de leur ego?