Jak częste są algorytmy czasu wykładniczego w przypadku ogólnym w oprogramowaniu produkcyjnym?

Wiem, że algorytmów wykładniczych czasu należy zasadniczo unikać, ale czasami są one konieczne. Sprawą jest Podróżujący Sprzedawca. Jak częste są takie algorytmy w oprogramowaniu produkcyjnym? Czy te przypadki są zazwyczaj konieczne, czy też są wynikiem pośpiechu? Rozumiem, że wielu można rozwiązać za pomocą dobrej heurystyki. Co zazwyczaj robi się z tymi, którzy nie mogą?

Coś, co nie w oprogramowaniu produkcyjnym, ale w oprogramowaniu produkcyjnym, jest formalną weryfikacją . Prawdopodobnie nie jest adoptowany dla większości programów klienckich, ale zyskuje kontrolę nad systemami osadzonymi i sterownikami, to znaczy w przypadku sprzętu i oprogramowania, którego poprawność jest ważna (i możliwa do rozwiązania).

Te problemy z weryfikacją, które są faktycznie obliczalne (bariera nr 1), często są WYŁĄCZNIE - twarde , w szczęśliwszych przypadkach masz problemy z ukończeniem PSPACE (bariera nr 2). Obie klasy są (podejrzewane o to) trudniejsze niż problemy z NP-zupełnością, które są łatwe do porównania. Łatwo można również uzyskać podwójne wykładnicze problemy.

W takich przypadkach heurystyka (w sensie wyniku końcowego) nie odcina jej, ponieważ potrzebne są określone wyniki; dlatego potrzebujesz dużych maszyn i czasu. Istnieją heurystyki (w sensie wyboru alternatywnego), które często prowadzą do krótszego czasu wykonywania (tj. Sprytne badanie przestrzeni wyszukiwania, gdy wyszukiwane są stany błędów), ale w najgorszym przypadku czekanie jest wszystkim, co możesz zrobić. Możesz też wykonać próbny papier i sprawdzić go przez maszyny , co jest łatwiejsze obliczeniowo.

Powszechnie stosowanym algorytmem o wykładniczej najgorszej złożoności jest metoda simpleksowa stosowana w programowaniu liniowym . Jednak złożoność tej metody w ogólnym przypadku jest kwestią otwartą. Przy niektórych konkretnych założeniach jest wielomianowy.

Tłumacze języka programowania są gorsi niż czas wykładniczy (w długości ich wkładu, tj. W długości programu, który tłumaczą) i są dość powszechni. Innym przykładem jest automatyczne sprawdzanie twierdzeń / rozwiązywanie ograniczeń / rozwiązywanie sat / programowanie liniowe liczb całkowitych. A jeszcze innym przykładem jest różnicowanie symboliczne zaimplementowane np. W Maple / Mathematica (chociaż możliwe jest różnicowanie symboliczne w czasie liniowym, jeśli można udostępniać podwyrażenia między węzłami).

Pozwólcie, że podam przykład problemu sprzedawcy podróżującego. Pracowałem nad tym kilka razy.

Kilka razy byłem w zespole, który napisał rozwiązanie problemu sprzedawcy podróżującego, ale z kilkoma dodatkowymi parametrami. Na przykład może to być sklep z flotą techników i inżynierów, każdy z unikalnym zestawem umiejętności. Miejsca docelowe pojawiają się codziennie w formie zgłoszeń serwisowych. Wszystkie programy są w produkcji, chociaż zostały zmodyfikowane i konserwowane od czasu ich pierwotnego napisania.

Tak działali. Każdy inżynier otrzymywałby listę rzeczy do serwisowania na podręcznym urządzeniu każdego dnia. Po zakończeniu każdego zadania serwisowego powinni zamknąć obudowę. Przypadki, które zostały pominięte, dołączają do spraw, które zostaną zaplanowane na następny dzień z nieco wyższym priorytetem, ponieważ do tego czasu klient wyraziłby pewne niezadowolenie. Istnieje wiele powodów, dla których inżynier nie bierze udziału w sprawie. Problemy z ruchem były najczęstsze.

Jak często są? Przynajmniej tak często jak liczba zgłoszeń serwisowych pochodzących od klientów. Na przykład bez obsługi posprzedażnej utrzymanie klientów będzie trudne, a pozyskiwanie nowych będzie trudniejsze.

Ponieważ wiele sklepów internetowych, takich jak Amazon i inne księgarnie oraz inne takie sklepy dobrze sobie radzą w biznesie, wydaje mi się, że podróżujący sprzedawca jest bardziej popularny niż kiedyś. Ponadto może istnieć wiele odmian problemu podróżnego sprzedawcy, których uczy się w podręcznikach.