Widzieliśmy już, jak definiowany jest problem znajdowania trasy pod kątem określonych lokalizacji i przejść wzdłuż krawędzi między nimi. Algorytmy wyszukiwania tras są używane w różnych aplikacjach. Niektóre, takie jak witryny internetowe i systemy samochodowe, które podają wskazówki dojazdu, są stosunkowo prostymi rozszerzeniami przykładu rumuńskiego. (Głównymi komplikacjami są różne koszty wynikające z opóźnień zależnych od ruchu oraz zmiany trasy z powodu zamknięcia dróg). Inne, takie jak przesyłanie strumieni wideo w sieciach komputerowych, planowanie operacji wojskowych i systemy planowania podróży lotniczych, wymagają znacznie bardziej złożonych specyfikacji. Rozważ problemy związane z podróżami lotniczymi, które muszą zostać rozwiązane przez witrynę internetową do planowania podróży:
* STANY: Każdy stan zawiera oczywiście lokalizację (np. lotnisko) i aktualny czas. Ponadto, ponieważ koszt działania (segment lotu) może zależeć od poprzednich segmentów, ich baz taryfowych oraz ich statusu jako krajowego lub międzynarodowego, państwo musi rejestrować dodatkowe informacje o tych „historycznych” aspektach.
STAN POCZĄTKOWY: Lotnisko macierzyste użytkownika.
CZYNNOŚCI: Wybierz dowolny lot z bieżącej lokalizacji, w dowolnej klasie miejsc, wylatując po aktualnym czasie, pozostawiając w razie potrzeby wystarczającą ilość czasu na transfer wewnątrz lotniska.
MODEL PRZEJŚCIOWY: Stan wynikający z odbycia lotu będzie miał miejsce docelowe lotu jako nową lokalizację, a czas przylotu jako nowy czas.
STAN CELOWY: Miasto docelowe. Czasami cel może być bardziej złożony, np. „przylot do miejsca docelowego lotem bez przesiadek”.
KOSZT DZIAŁANIA: połączenie kosztów pieniężnych, czasu oczekiwania, czasu lotu, procedur celnych i imigracyjnych, jakości miejsc, pory dnia, typu samolotu, punktów za częste loty i tak dalej.
Komercyjne systemy doradztwa turystycznego wykorzystują takie sformułowanie problemu, z wieloma dodatkowymi komplikacjami w obsłudze bizantyjskich struktur taryfowych linii lotniczych. Każdy doświadczony podróżnik wie jednak, że nie wszystkie podróże lotnicze przebiegają zgodnie z planem. Naprawdę dobry system powinien zawierać plany awaryjne – co się stanie, jeśli ten lot się opóźni i połączenie zostanie utracone?
Problemy z wycieczkami opisują zbiór lokalizacji, które należy odwiedzić, a nie jeden cel. Problem komiwojażera (TSP) to problem zwiedzania, w którym każde miasto na mapie musi zostać odwiedzone. Celem jest znalezienie wycieczki z kosztami (lub w wersji optymalizacyjnej znalezienie wycieczki z możliwie najniższym kosztem). Ogromną ilość wysiłku włożono w poprawę możliwości algorytmów TSP. Algorytmy można również rozszerzyć, aby obsługiwać floty pojazdów. Na przykład algorytm wyszukiwania i optymalizacji wyznaczania tras autobusów szkolnych w Bostonie zaoszczędził 5 milionów dolarów, ograniczył ruch uliczny i zanieczyszczenie powietrza oraz zaoszczędził czas kierowców i studentów (Bertsimas i in., 2019). Oprócz planowania podróży, algorytmy wyszukiwania były wykorzystywane do zadań takich jak planowanie ruchów automatycznych wiertarek do płytek drukowanych i maszyn magazynujących na halach produkcyjnych.
Problem z układem VLSI wymaga umieszczenia milionów komponentów i połączeń na chipie, aby zminimalizować obszar, zminimalizować opóźnienia obwodów, zminimalizować zbędne pojemności i zmaksymalizować wydajność produkcji. Problem z układem pojawia się po logicznej fazie projektowania i zwykle dzieli się na dwie części: układ komórek i routing kanałów. W układzie komórki prymitywne komponenty obwodu są pogrupowane w komórki, z których każda pełni pewną rozpoznaną funkcję. Każda komórka ma stały ślad (rozmiar i kształt) i wymaga określonej liczby połączeń z każdą z pozostałych komórek. Celem jest umieszczenie ogniw na chipie tak, aby nie zachodziły na siebie i aby było miejsce na umieszczenie przewodów łączących między ogniwami. Routing kanałów znajduje określoną trasę dla każdego przewodu przez szczeliny między komórkami. Te problemy wyszukiwania są niezwykle złożone, ale zdecydowanie warte rozwiązania.
Nawigacja robotem jest uogólnieniem opisanego wcześniej problemu wyszukiwania tras. Zamiast podążać odrębnymi ścieżkami (takimi jak drogi w Rumunii), robot może wędrować dookoła, w efekcie tworząc własne ścieżki. W przypadku okrągłego robota poruszającego się po płaskiej powierzchni przestrzeń jest zasadniczo dwuwymiarowa. Kiedy robot ma ręce i nogi, które również muszą być kontrolowane, przestrzeń wyszukiwania staje się wielowymiarowa — jeden wymiar dla każdego kąta stawu. Zaawansowane techniki są wymagane tylko po to, aby zasadniczo ciągła przestrzeń poszukiwań była skończona (patrz Rozdział 26). Oprócz złożoności problemu, prawdziwe roboty muszą również radzić sobie z błędami w odczytach czujników i sterowania silnikami, z częściową obserwowalnością oraz z innymi czynnikami, które mogą zmieniać środowisko.
Automatyczne sekwencjonowanie złożonych obiektów (takich jak silniki elektryczne) przez robota jest standardową praktyką przemysłową od lat 70. XX wieku. Algorytmy najpierw znajdują wykonalną sekwencję montażu, a następnie pracują nad optymalizacją procesu. Minimalizacja ilości ręcznej pracy ludzkiej na linii montażowej może przynieść znaczne oszczędności czasu i kosztów. W problemach montażowych celem jest znalezienie kolejności, w jakiej należy składać części jakiegoś obiektu. Jeśli zostanie wybrana niewłaściwa kolejność, nie będzie możliwości dodania części w dalszej kolejności bez cofnięcia części już wykonanej pracy. Sprawdzanie wykonalności działania w sekwencji jest trudnym problemem geometrycznym ściśle związanym z nawigacją robota. Tak więc generowanie czynności prawnych jest kosztowną częścią sekwencjonowania montażu. Każdy praktyczny algorytm musi unikać eksploracji całej przestrzeni stanów z wyjątkiem niewielkiej części. Jednym z ważnych problemów związanych z montażem jest projektowanie białek, którego celem jest znalezienie sekwencji aminokwasów, które sfałdują się w trójwymiarowe białko o odpowiednich właściwościach, aby wyleczyć niektóre choroby.