I detta dokument presenteras en allmän ram för konstruktionen av Monte-Carlo-algoritmer för att lösa uppräkningsproblem. Som en tillämpning av det allmänna ramverket konstrueras en Monte-Carlo-metod för att uppskatta sannolikheten för ett multiterminalt planarnätverk vars kanter är föremål för oberoende slumpmässiga fel. Metoden är garanterat effektiv när felsannolikheten för kanterna är tillräckligt liten. 0 1985 Academic Fms, Inc. I detta dokument undersöks ett klassiskt problem i tillförlitlighetsteorin: beräkning av felsannolikheten för ett nätverk vars kanter är föremål för slumpmässiga fel. Effektiva lösningsmetoder för detta problem har utformats endast i specialfall (Satyanarayana och Wood, 1982; Wood, 1982) och det finns starka indikationer från beräkningskomplex teori att det allmänna problemet är intractable (Provan och Ball, 1981; Valiant, 1979). Baserat på vårt tidigare arbete med Monte-Carlo algoritmer för räkning och tillförlitlighet problem (Karp och Luby, 1983,19&T; Luby, 1983), presenterar vi en Monte-Carlo metod för den ungefärliga lösningen av detta problem när nätverket är planar. Vår metod är garanterat effektiv när felsannolikheten för kanterna är tillräckligt liten. I det multiterminala nätets tillförlitlighetsproblem får man en oriktad graf, inom vilken vissa hörn betecknas som terminaler.
I REF ges en Monte Carlo-metod för att uppskatta sannolikheten för fel med slumpmässiga nätverkslänktillstånd.
Monte-Carlo algorithms for the planar multiterminal network reliability problem
{'venue': 'J. Complex.', 'journal': 'J. Complex.', 'mag_field_of_study': ['Computer Science']}