Dempster´s rule for evidence ordered in a directed acyclic graph

Dempster-Shaferteorien, vilken är ett sätt att hantera osäker information, baserar sig på att man har evidenser för och/eller emot en eller flera olika utsagor. Dempster-Shaferteorin innehåller en regel för hur dessa evidenser skall vägas samman, Dempsters regel. Denna rapport presenterar en ny algoritm med lägre beräkningskomplexitet för Dempsters regel i fallet med evidenser ordnade i en riktad acyklisk graf än för den klassiska steg for steg användningen av Dempsters regel. Detta är problemet när vi för varje par av evidenser har en evidens emot den samtidiga tron på båda utsagorna. De ursprungliga evidenserna är belägna på noderna och de nya på mellanliggande kanter. Den nya algoritmen vilken uttalar sig om hela färdvägar genom grafen är O(n.4n), jämfört med O(2n2) för den klassiska algoritmen. Efter att ha gjort en detaljerad presentation av tankarna bakom den nya algoritmen drar vi slutsatsen att det är möjligt att uttala sig utan approximation om hela färdvägar genom en riktad acyklisk graf inte endast för de minsta problemen.