Czy ktoś ma przykłady z życia, w których regularnie rozwiązuje NP pełne lub trudne problemy NP (heurystykami, szukając rozwiązania nieoptymalnego lub cokolwiek innego) w swojej pracy? Wiem, że występują one w planowaniu, planowaniu, projektowaniu VLSI itp., Ale staram się zorientować, jakie główne branże zatrudniają dziś programistów lub inżynierów, którzy regularnie to robią. Gdyby ktoś rozwinął wiedzę specjalistyczną lub bibliotekę, powiedzmy, optymalizację kombinatoryczną, to gdzie można to wykorzystać jako część pracy programistycznej?
Jakieś konta osobiste?
algorithms
optimization
wysoka przepustowość
źródło
źródło
Odpowiedzi:
Niektóre rzeczy, o których mogę myśleć (większość z nich byłam mniej lub bardziej zaangażowana):
Istnieje wiele standardowych przykładów, takich jak znalezienie najkrótszej trasy, planowanie pielęgniarki itp., Ale jeśli jesteś zwolennikiem optymalizacji kombinatorycznej, wiesz o nich :)
źródło
Użyłem ograniczonego czasowo symulowanego wyżarzania do rozwiązania problemu wędrownego salemana w produkcji panelu dotykowego. Każda milisekunda, którą moglibyśmy się ogolić od czasu cyklu trawienia laserowego każdego panelu, zwiększałaby przepustowość, wykorzystanie, a tym samym rentowność maszyny, dlatego włożyłem wiele wysiłku w minimalizowanie czasu przestoju (ścieżek nie rysujących) między ścieżkami rysowania (które oczywiście nie można go zoptymalizować).
Użyłem algorytmu czasowego, aby obejść twardość NP problemu, ponieważ nie mogliśmy sobie pozwolić na ryzyko, że obliczenie optymalizacji może potrwać dłużej niż czas zaoszczędzony przez bardziej optymalną ścieżkę. Gdy maszyna przemieszczała panel z położenia ładowania do położenia, w którym głowica lasera znajdowała się za najbliższym rogiem, miałem czas na przeprowadzenie niektórych symulacji. Algorytm prawie nigdy nie dobiegł końca w ciągu kilkuset milisekund ruchu, ale prawie zawsze zwracał lepszą ścieżkę zapisu niż jakikolwiek z prostych, nieadaptacyjnych modeli, których zawsze używaliśmy wcześniej (takich jak ścieżki spiralne lub wężowe).
źródło
Pracuję (właściwie teraz) nad problemem bioinformatycznym polegającym na dopasowaniu wielu lokalnych sekwencji DNA. Chodzi o to, że jeśli wiele sekwencji genów o pewnej wspólnej właściwości (podobny profil ekspresji lub wiązanie tego samego czynnika transkrypcyjnego w eksperymencie z czipem ChIP) wyrównuje się silnie w pewnym momencie, to prawdopodobnie znalazłeś przyczynę ich wspólnej własność. Z drugiej strony jestem bardziej zainteresowany statystycznymi aspektami problemu. Mimo że jest to trudne dla NP, nie tracisz wiele, stosując heurystykę w praktyce. Interesująca część problemu, IMHO, to problem stosunku sygnału do szumu.
źródło
Naprawdę nie wiem, co oznacza NP zupełne / twarde, ale myślę, że autoplanowanie dostaw jest tego rodzaju.
Masz plan popytu na 90 dni do przodu dla 100 SKU produktów: piwo! SKU 100 produktów pochodzi z:
Dla każdej operacji istnieją „linie” maszynowe: od parzenia po pakowanie. Maszyny mogą wykonywać więcej operacji, powiedzmy, niektóre maszyny pakujące mogą produkować 6 sztuk i 3 sztuki, ale inne mogą produkować tylko 6 sztuk. Istnieją ograniczenia, np. Prędkość lub duży czajnik do zaparzania min. 6000, maksimum, 8000 l piwa (ale jeśli typ piwa jest lekki, wówczas min. To 5000 l, a maks. 7000 l). I tak dalej, na każdym poziomie.
Zadanie: jak wspomniałem, istnieje plan popytu na rodzaj 100 poziomu 5 (butelkowane, pakowane rzeczy). Stwórz optymalny plan produkcji dla wszystkich 5 poziomów, wszystkich maszyn. Zminimalizuj przełączniki maszyn (np. Butelkowanie .5, .5, .5, .3, .3, .3 jest lepsze niż .3, .5, .3, .5, .3, .5, jest mniej swithc, krótszy czas martwy dla maszyn do butelkowania). Ustal priorytet według klienta: niektórzy klienci wymagają wysyłki piwa, gdy pozostało ponad 50% czasu ważności. Itd itd.
Odkrywaj wąskie gardła (eh), twórz alternatywne plany z dodawaniem nieistniejących maszyn do tych punktów, a następnie możesz użyć najlepszego scenariusza wirtualnego, aby zasugerować zakup nowych maszyn.
Czy to jest wystarczająco trudne, czy powinienem powiedzieć, jak działa fabryka włókiennicza ?
(Uwaga osobista: sieć, bank i logistyka są trudnymi obszarami, ale są zabawkami dla dzieci w porównaniu do problemów związanych z produkcją).
Oświadczenie: liczby są zniekształcone ze względów bezpieczeństwa, rząd wielkości jest prawdziwy.
źródło