Detta dokument presenterar en ny algoritm för att hitta alla lösningar med objektiva funktionsvärden i grannskapet av den optimala för vissa dynamiska programmeringsmodeller, inklusive kortaste vägen problem. Den nya algoritmen kombinerar djup-först sökning med stapling tekniker av teoretisk datavetenskap och principer från dynamisk programmering för att ändra den vanliga backtracking rutin och lista alla nära optimal politik. Det resulterande förfarandet är den första praktiska algoritmen för en mängd stora problem som är av intresse. HAN ALgorITM som presenteras i denna uppsats motiverades av en studie T om det evolutionära distansproblemet i molekylärbiologi. I detta sammanhang används dynamiska programmeringsmetoder för att undersöka evolutionära relationer mellan två DNA-sekvenser (Smith et al. [1981]........................................................................................................... De specifika sekvenser som studerades innebar ett nätverk av cirka 2.200 noder och 110.OOO bågar så att analys av Kth kortaste väg metoder var inte praktiskt. Närmare uppgifter om denna studie har publicerats på annat håll (Waterman [1983]). Betrakta ett riktat acykliskt nätverk eller, mer allmänt, ett nätverk utan cykel vars längd är icke-positiv. En enkel metod presenteras för att hitta alla vägar från nod 1 till nod N vars längder ligger inom ett förskrivet avstånd e(e 2 0) av längden på de kortaste sökvägarna från nod 1 till nod N. Algoritmen använder en push-down (last-in, first-out) stack och har blygsamma minneskrav. Denna nya metod är lätt att förstå och koda, vilket, med minneskraven, ger den en särskild fördel jämfört med Kth kortaste vägen beräkningar. Se Dreyfus [ 19691 för en genomgång av kortast möjliga algoritmer. För att beskriva den nya metoden låt t(x, y) betecknar längden på båge (x, y) i nätverket. Med f ( N ) = 0, låt f ( x ) betecknar längden på den kortaste ämne klrssificatbn: 111 nära optimal politik.
I det förra är målet att identifiera de vägar vars längd ligger inom en faktor på (1 + ε) av den kortaste vägens längd, för en användarspecificerad ε ≥ 0. Ref var bland de första verken som handlade om nära-SP och antog idéer från dynamisk programplanering.
Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming
{'venue': 'Operations Research', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}