የፕሪምስ አልጎሪዝም ጥቅም ላይ የዋለው ለምንድ ነው?

2024 ደራሲ ደራሲ: Lynn Donovan | [email protected]. ለመጨረሻ ጊዜ የተሻሻለው: 2023-12-15 23:42

በኮምፒውተር ሳይንስ፣ ፕሪም (ጃርኒክስ በመባልም ይታወቃል) አልጎሪዝም ስግብግብ ነው። አልጎሪዝም ለክብደቱ ያልተመራ ግራፍ በትንሹ የሚዘረጋ ዛፍ የሚያገኘው። ይህ ማለት በዛፉ ውስጥ ያሉት የሁሉም ጠርዞች ክብደት የሚቀንስበት እያንዳንዱን ጫፍ የሚያካትት የዛፍ ቅርጽ ያለው የጠርዙን ንዑስ ክፍል ያገኛል።

በተጨማሪም የ Kruskal ስልተ ቀመር ለምን ጥቅም ላይ ይውላል?

የ Kruskal ስልተ ቀመር ይጠቀማል ትንሹን የተንጣለለ ዛፍን የሚከለክለው ስግብግብ አካሄድ። የ Kruskal ስልተ ቀመር ሁሉንም መስቀለኛ መንገድ እንደ ገለልተኛ ዛፍ ይቆጥረዋል እና ካሉት ሌሎች አማራጮች ጋር ሲነፃፀር ዝቅተኛው ዋጋ ካለው አንዱን ከሌላው ጋር ያገናኛል።

በሁለተኛ ደረጃ የዲጅክስታራ አልጎሪዝም ምን ያደርጋል? Dijkstra ስልተ ቀመር መስቀለኛ መንገዱ ከመጀመሪያው መስቀለኛ መንገድ ሊደረስበት እስከቻለ ድረስ በአንድ ግራፍ ውስጥ ካለው አንድ መስቀለኛ መንገድ ወደ እያንዳንዱ ሌላ መስቀለኛ መንገድ በተመሳሳይ የግራፍ መረጃ መዋቅር ውስጥ ያለውን አጭር መንገድ ለመወሰን ሊያገለግል ይችላል። Dijkstra ስልተ ቀመር አጭሩን መንገድ ለማግኘት ሊያገለግል ይችላል።

በሁለተኛ ደረጃ, የትኛው የተሻለ ፕሪምስ እና ክሩካል አልጎሪዝም ነው?

የክሩስካል አልጎሪዝም : ያከናውናል የተሻለ ቀላል የሆኑ የመረጃ አወቃቀሮችን ስለሚጠቀም መደበኛ ያልሆኑ ሁኔታዎች (የተለያዩ ግራፎች)። የፕሪም አልጎሪዝም በጣም ብዙ የጠርዝ ጫፎች ያሉት ጥቅጥቅ ያለ ግራፍ ሲኖርዎት በገደቡ ውስጥ በጣም ፈጣን ነው።

የፕሪምስ አልጎሪዝም የጊዜ ውስብስብነት ምንድነው?

ስለዚህ የአንድን ግራፍ asub-graph ፍቺ ለመወሰን ነጠላ የኢንቲጀር ይጠቀማል። የ የጊዜ ውስብስብነት O(VlogV +ElogV) = O(ElogV) ነው፣ እሱም ተመሳሳይ ያደርገዋል Kruskal'salgorithm . ሆኖም፣ የፕሪም አልጎሪዝም Fibonacci Heaps (cf Cormen) ወደ O(E + logV) ማሻሻል ይቻላል።