Grammatikproblemet, en generalisering av det kortaste problemet med en enda källa som infördes av Knuth, är att beräkna minimikostnaden för härledning av en terminalsträng från en eller flera icke-terminaler av en given kontextfri grammatik, med kostnaden för en härledning definieras på lämpligt sätt. I denna artikel presenterar vi en inkrementell algoritm för en version av grammatikproblemet. Som ett specialfall av denna algoritm får vi en effektiv inkrementell algoritm för singlesource kortaste-pat problem med positiva kantlängder. Den aspekt av vår inkrementella algoritm som skiljer den från allt annat arbete på den dynamiska kortaste vägen problemet är dess förmåga att hantera "multipel heterogena modifieringar": mellan uppdateringar, är inmatningskurvan tillåtet att omstruktureras genom en godtycklig blandning av kantinsättningar, kantraderingar, och kant-längd förändringar.
REF ger en inkrementell algoritm för en version av grammatikproblemet och som korollärer få inkrementella algoritmer för en källa kortaste sökväg problem med positiva kantvikter.
An Incremental Algorithm for a Generalization of the Shortest-Path Problem
{'venue': 'Journal of Algorithms', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}