Les algorithmes de temps exponentiel à cas générique sont-ils courants dans les logiciels de production?

Je sais que les algorithmes de temps exponentiels devraient généralement être évités mais sont parfois nécessaires. Un cas étant le voyageur de commerce. Ces algorithmes sont-ils courants dans les logiciels de production? Ces cas sont-ils généralement nécessaires ou résultent-ils de travaux urgents? Je comprends que beaucoup peuvent être résolus avec une bonne heuristique. Que fait-on généralement avec ceux qui ne le peuvent pas?

Quelque chose qui n'est pas dans le logiciel de production mais fait sur le logiciel de production est une vérification officielle . Il n'est probablement pas adopté pour la plupart des logiciels clients mais gagne du terrain pour les systèmes embarqués et les pilotes, c'est-à-dire pour les logiciels et les logiciels dont l'exactitude est importante (et exploitable).

Ces problèmes de vérification qui sont réellement calculables (barrière # 1) sont souvent EXPTIME- dur, dans les cas les plus chanceux vous obtenez des problèmes PSPACE -complet (barrière # 2). Les deux classes sont (soupçonnées d'être) plus difficiles que les problèmes NP-complets, ce qui est facile en comparaison. Des problèmes doublement exponentiels sont également facilement obtenus.

Dans ces cas, l'heuristique (dans le sens du résultat final) ne suffit pas car vous avez besoin de résultats précis; vous avez donc besoin de grosses machines et de temps. Il existe des heuristiques (dans le sens d'une sélection alternative) qui conduisent souvent à une durée d'exécution plus courte (c'est-à-dire une exploration intelligente de l'espace de recherche lorsque les états d'erreur sont recherchés) mais dans le pire des cas, l'attente est tout ce que vous pouvez faire. Ou vous pouvez faire une épreuve au crayon et sur papier et la faire vérifier par des machines , ce qui est plus simple sur le plan des calculs.

Un algorithme couramment utilisé avec une complexité exponentielle dans le pire des cas est la méthode simplex utilisée dans la programmation linéaire . Cependant, quelle est la complexité du cas générique de cette méthode est un problème ouvert. Avec certaines hypothèses spécifiques, c'est polynomial.

Les interprètes de langage de programmation sont pires que le temps exponentiel (dans la longueur de leur entrée, c'est-à-dire dans la longueur du programme qu'ils interprètent), et ils sont assez courants. Un autre exemple est la démonstration automatique de théorèmes / résolution de contraintes / résolution sat / programmation linéaire entière. Et encore un autre exemple est la différenciation symbolique implémentée par exemple dans Maple / Mathematica (bien qu'il soit possible de faire une différenciation symbolique en temps linéaire si vous êtes autorisé à partager des sous-expressions entre les nœuds).

Permettez-moi de prendre l'exemple du problème du voyageur de commerce. J'y ai travaillé plusieurs fois.

Il y a quelques fois où j'ai fait partie d'une équipe qui a écrit une solution pour un problème de voyageur de commerce mais avec quelques paramètres supplémentaires. Par exemple, il pourrait s'agir d'un magasin avec une flotte de techniciens et d'ingénieurs possédant chacun un ensemble de compétences unique. Les destinations apparaissent chaque jour sous forme de demandes de service. Tous les programmes sont en cours de production bien qu'ils aient subi des modifications et une maintenance depuis leur création initiale.

Voilà comment ils fonctionnaient. Chaque ingénieur recevrait tous les jours une liste de choses à entretenir sur un appareil portatif. Lorsqu'ils terminent chaque tâche de service, ils doivent fermer le dossier. Les cas laissés de côté rejoignent les cas qui doivent être programmés pour le lendemain avec une priorité légèrement plus élevée car le client aurait alors exprimé une certaine insatisfaction. Il y avait un grand nombre de raisons pour lesquelles un ingénieur ne voulait pas assister à une affaire. Les problèmes de circulation étaient les plus courants.

Sont-ils courants? Au moins aussi courant que le nombre de demandes de service après-vente émanant des clients. Sans service après-vente, par exemple, il sera difficile de fidéliser les clients et d'en gagner de nouveaux.

Avec de nombreuses boutiques en ligne telles qu'Amazon et d'autres librairies et autres magasins de ce type qui fonctionnent bien dans les affaires, je pense que le vendeur itinérant est plus courant qu'auparavant. En outre, il pourrait y avoir de nombreuses variantes du problème des vendeurs ambulants qui sont enseignées dans les manuels.