Ottimalità di un algoritmo avido

Question

Se hai progettato un algoritmo avido per ottenere una soluzione ottimale e l'algoritmo può produrre diverse combinazioni di valori, ma ancora, qualsiasi combinazione di tesi è una soluzione ottimale.Come si dimostra è ottimalità?

Ad esempio si ha un set di numeri $ \ Mathcal {m}={1,2,3,4 \} $ e si desidera progettare unAlgoritmo per ottenere il numero minimo di numeri interi necessari per ottenere una somma 5. In questo caso, $ 1,4 $ o $ 2,3 $ può produrre 5 ed entrambi sono soluzioni ottimali in quanto il numero minimo richiesto è due.

Come dimostrare l'ottimalità dell'algoritmo?

Ho provato per contraddizione un presumere che ci sia una soluzione ottimale $ p ^ * $ e il mio algoritmo non produce una soluzione ottimale $ P $ così $ p \ neq p ^ * $ .Ma non so come continuare l'argomento.

Answer 1

Questo è il Modifica creazione di problemi .Per alcuni set di denominazioni (ad es. Poteri di qualche base $ B $ , le monete statunitensi, o quasi tutti i sistemi di moneta nel mondo) l'algoritmo avido dà il numero minimo dimonete.Il caso generale è NP-Complete, una soluzione pratica richiede una programmazione dinamica (vedere l'articolo di Wikipedia apprezzato).Esiste un algoritmo di tempo polinomiale per verificare se un determinato insieme di denominazioni rende l'algoritmo avido o meno o meno, vedere Pearson (1994) " un algoritmo polinomiale per il problema di creazione di cambiamento" , doi 10.1.1.57.3243.

Answer 2

Se un algoritmo avido non è sempre ottimale, un controexample è una prova sufficiente di questo.

In questo caso, prendere $ \ mathcal {m}={1,2,4,5,6 \} $ .Quindi per una somma di $ 9 $ L'algoritmo avido produce $ 6 + 2 + 1 $ Ma questo non è ottimale> ma questo non è ottimale> Ma questo non è ottimalePerché $ 5 + 4 $ ha meno sommentazioni.

Answer 3

L'algoritmo avido di solito comporta una sequenza di scelte e una volta fatta una scelta che non possiamo annullarlo nel passaggio successivo. Quindi è importante che (l'algoritmo avido) non abbia mai commesso un errore. Una soluzione ottimale locale significa una migliore soluzione possibile.

Lascia impostare $ s $ Sii una soluzione ottimale per qualche problema e il nostro algoritmo avido dà un set $ P $ < / span>. Se entrambi $ p $ e $ s $ sono uguali, quindi vengono eseguiti. Supponiamo che sia $ P $ e $ s $ sono diversi, in questo caso l'algoritmo avido avrà una scelta Elemento nel passaggio intermedio (soluzione locale) che è meno ottimale che ha comportato $ P $ anziché set ottimale $ s $ < / span>. Ma secondo l'algoritmo avido, scegliamo sempre una soluzione ottimale locale. Quindi l'argomento è dimostrato dalla prova per contraddizione.