Quanto sono comuni gli algoritmi esponenziali del caso generico nel software di produzione?

Qualcosa che non in software di produzione ma fatto su software di produzione è formale verifica . Probabilmente non è adottato per la maggior parte dei software dei clienti, ma guadagna la traccia per i sistemi e i driver incorporati, vale a dire per hard e software la cui correttezza è importante (e trattabile).

Questi problemi di verifica che sono effettivamente calcolabili (barriera # 1) sono spesso EXPTIME -hard, nei casi più fortunati ottieni problemi PSPACE - completi (barriera n. 2). Entrambe le classi sono (sospettate di essere) più difficili dei problemi NP-completi, che sono facili da confrontare. Si ottengono facilmente anche problemi doppi-esponenziali.

In questi casi, l'euristica (nel senso del risultato finale) non la taglia in quanto hai bisogno di risultati definiti; quindi hai bisogno di grandi macchine e tempo. Esistono euristiche (nel senso di una selezione alternativa) che spesso portano a un runtime più breve (ad esempio, un'intelligente esplorazione dello spazio di ricerca quando vengono cercati gli stati di errore) ma nel peggiore dei casi, l'attesa è tutto ciò che si può fare. Oppure puoi fare una dimostrazione a penna e carta e averla controllata da macchine , che è computazionalmente più semplice.

L'algoritmo comunemente utilizzato con la peggiore complessità esponenziale è il metodo simplex utilizzato in programmazione lineare . Tuttavia, la complessità del caso generico di tale metodo è un problema aperto. Con alcune ipotesi specifiche è polinomiale.

Gli interpreti di linguaggio di programmazione sono peggio del tempo esponenziale (nella lunghezza del loro input, cioè nella lunghezza del programma che stanno interpretando), e sono abbastanza comuni. Un altro esempio è la dimostrazione automatica del teorema / risoluzione di vincoli / sat solving / programmazione lineare intera. E ancora un altro esempio è la differenziazione simbolica implementata ad es. Maple / Mathematica (anche se è possibile fare la differenziazione simbolica nel tempo lineare se si è autorizzati a condividere sottoespressioni tra i nodi).

Lasciatemi fare l'esempio del problema del commesso viaggiatore. Ci ho lavorato un paio di volte.

Ci sono alcune volte in cui ho lavorato in un team che ha scritto una soluzione per il problema del commesso viaggiatore, ma con alcuni altri parametri. Ad esempio, potrebbe essere un negozio con una flotta di tecnici e ingegneri ciascuno con un set di abilità unico. Le destinazioni arrivano ogni giorno sotto forma di richieste di servizio. Tutti i programmi sono in produzione anche se hanno subito modifiche e manutenzione da quando li hanno scritti in origine.

Ecco come hanno funzionato. Ogni ingegnere riceve ogni giorno un elenco di cose da prestare su un dispositivo portatile. Mentre finiscono ogni attività di servizio, dovrebbero chiudere il caso. I casi trascurati si uniscono ai casi da programmare per il giorno successivo con priorità leggermente più alta, poiché a quel punto il cliente avrebbe espresso insoddisfazione. C'era una serie di motivi per cui un ingegnere non avrebbe partecipato a un caso. I problemi di traffico erano più comuni.

Quanto sono comuni? Almeno comune come numero di richieste di assistenza post vendita provenienti dai clienti. Senza il servizio post vendita, ad esempio, mantenere i clienti sarà difficile e acquistarne di nuovi sarà più difficile.

Con molti negozi online come Amazon e altri negozi di libri e altri negozi di questo tipo che stanno facendo buoni affari, penserei che il commesso viaggiatore sia più comune di quanto non fosse in passato. Inoltre, potrebbero esserci molte varianti del problema del venditore ambulante che vengono insegnate nei libri di testo.