Бағытталған ациклдік графтардағы түйіндерді реттеу (топологиялық сұрыптау) туралы мақала. Міндеттерді орындау ретін анықтауға көмектеседі. DAG үшін алгоритмдер.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бағытталған ациклді графиктерді реттеу
Node ordering for directed acyclic graphs
Компьютер ғылымында, топологиялық реттеу немесе бағытталған графиктің топологиялық сұрыпталуы – бұл оның төбелерінің сызықтық реті, мұнда әрбір бағытталған қабырға (u,v) үшін, төбе u-ден төбе v-ге, u реттеуде v-ден бұрын келеді. Мысалы, графиктің төбелері орындалуға тиіс тапсырмаларды білдіруі мүмкін, ал қабырғалары – бір тапсырманы екіншісінен бұрын орындау қажеттігін көрсететін шектеулерді білдіруі мүмкін; мұндай жағдайда топологиялық реттеу – тапсырмалардың орындалуының дұрыс тізбегі. Нақтырақ айтқанда, топологиялық реттеу – бұл графты аралау, онда әрбір төбе v оның барлық тәуелділіктері қарастырылғаннан кейін ғана қарастырылады. Топологиялық реттеу мүмкін болуы үшін графтың бағытталған циклдары болмауы керек, яғни ол бағытталған ациклді граф (DAG) болуы тиіс. Кез келген DAG кемінде бір топологиялық реттеуге ие, және кез келген DAG-тің топологиялық ретін сызықтық уақытта құруға арналған алгоритмдер белгілі. Топологиялық реттеудің көптеген қолданыс аймақтары бар, әсіресе кері байланыс доғалары сияқты рейтингілеу мәселелерінде. Топологиялық реттеу DAG-де ажыратылған компоненттер болған жағдайда да мүмкін.
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications, especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components.
Мысалдар
Топологиялық сұрыптаудың ең негізгі қолданылуы – жұмыс немесе тапсырмалардың тізбесін олардың өзара тәуелділіктеріне сәйкес жоспарлау болып табылады. Жұмыстар графтың түйіндерімен бейнеленеді, егер жұмыс x-ті аяқтамайынша, жұмыс y-ты бастау мүмкін болмаса, x-тен y-ға қарай жиек жүргізіледі (мысалы, киім жуу кезінде, киімді кептіргішке салу үшін алдымен кір жуатын машина аяқталуы керек). Осылайша, топологиялық сұрыптау жұмыстарды орындау ретін анықтайды. Топологиялық сұрыптау алгоритмдерінің тікелей байланысты қолданылуы алғаш рет 1960 жылдардың басында жобаларды басқарудағы жоспарлау үшін PERT әдісінің аясында зерттелді. Бұл қолданыста графтың түйіндері жобаның маңызды кезеңдерін, ал жиектер – бір кезеңнен екінші кезеңге өту үшін орындалуы тиіс тапсырмаларды көрсетеді. Топологиялық сұрыптау жобаның ең қиын жолын табуға арналған сызықтық уақыт алгоритмдерінің негізін құрайды, бұл жобаның жалпы кестесінің ұзақтығын анықтайтын кезеңдер мен тапсырмалардың тізбегі. Компьютер ғылымында осы типтегі қолданыстар нұсқауларды жоспарлау, электрондық кестелерде формула мәндерін қайта есептеу кезінде формула ұяшықтарын бағалау ретін анықтау, логикалық синтез, компиляция тапсырмаларын орындау ретін анықтау, деректерді сериализациялау және сілтемелердегі символ тәуелділіктерін шешу үшін қолданылады. Сондай-ақ, деректер базасында сыртқы кілттері бар кестелерді қандай ретпен жүктеу керектігін анықтау үшін де қолданылады.
The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer). Then, a topological sort gives an order in which to perform the jobs. A closely related application of topological sorting algorithms was first studied in the early 1960s in the context of the PERT technique for scheduling in project management. In this application, the vertices of a graph represent the milestones of a project, and the edges represent tasks that must be performed between one milestone and another. Topological sorting forms the basis of linear time algorithms for finding the critical path of the project, a sequence of milestones and tasks that controls the length of the overall project schedule. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers. It is also used to decide in which order to load tables with foreign keys in databases.
Бірегейлігі
Егер топологиялық ретте реттелген тізімдегі барлық жапсарлас төбелер жиектермен байланысқан болса, онда осы жиектер DAG-да бағытталған Гамильтондық жолды құрайды. Егер Гамильтондық жол болса, топологиялық реттелу тәртібі бірегей болады; ешқандай басқа тәртіп жолдың жиектерін сақтамайды. Керісінше, егер топологиялық рет Гамильтондық жолды құрамаса, DAG-да екі немесе одан көп жарамды топологиялық реттемелер болады, себебі бұл жағдайда бір-біріне жиекпен байланыспаған екі іргелес төбелерді ауыстыру арқылы екінші жарамды реттеме жасауға болады. Сондықтан, Гамильтондық жол мәселесінің жалпы бағытталған графтар үшін (яғни, циклдық бағытталған графтар үшін) NP қиындығына қарамастан, бірегей реттеме бар-жоғын және Гамильтондық жол бар-жоғын сызықтық уақытта тексеру мүмкін.
If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other. Therefore, it is possible to test in linear time whether a unique ordering exists, and whether a Hamiltonian path exists, despite the NP hardness of the Hamiltonian path problem for more general directed graphs (i. e., cyclic directed graphs).
Ішінара тапсырыстармен байланыс
Топологиялық реттеулер математикадағы ішінара реттің сызықтық кеңейтілуі тұжырымдамасымен тығыз байланысты. Ішінара реттелген жиын – бұл объектілер жиынтығы және "≤" теңсіздік қатынасының анықтамасы, рефлексивтілік (x ≤ x), антисимметрия (егер x ≤ y және y ≤ x болса, онда x = y) және транзитивтілік (егер x ≤ y және y ≤ z болса, онда x ≤ z) аксиомаларын қанағаттандырады. Толық рет – бұл жиынтықтағы кез келген екі объекті x және y үшін x ≤ y немесе y ≤ x болатын ішінара рет. Толық реттер компьютерлік ғылымда салыстыру сұрыптау алгоритмдерін орындау үшін қажетті салыстыру операторлары ретінде белгілі. Шекті жиынтықтар үшін толық реттер объектілердің сызықтық тізбектерімен сәйкес келеді, мұнда "≤" қатынасы бірінші объекті екінші объектіден бұрын келгенде дұрыс болады; салыстыру сұрыптау алгоритмі толық ретті осылайша тізбекке түрлендіру үшін қолданылуы мүмкін. Ішінара реттің сызықтық кеңейтілуі – бұл онымен үйлесімді толық рет, яғни егер x ≤ y ішінара ретте болса, онда x ≤ y толық ретте де орындалады. Кез келген бағытталған ациклдік графтан (DAG) ішінара реттеуді графтың төбелерін объектілер жиынтығы ретінде қарастырып, кез келген екі төбе x және y үшін x ≤ y қатынасын шын деп анықтауға болады, егер x-тен y-ға бағытталған жол болса; яғни, егер y, x-тен қол жетімді болса. Осы анықтамалар бойынша DAG-ның топологиялық реттелуі осы ішінара реттің сызықтық кеңейтілуімен бірдей. Керісінше, кез келген ішінара ретті DAG-дегі қол жетімділік қатынасы ретінде анықтауға болады. Мұны істеудің бір жолы – ішінара реттелген жиынтықтағы әрбір объекті үшін төбесі бар DAG-ді және x ≤ y шартын қанағаттандыратын әрбір объектілер жұбы үшін xy жиегін анықтау. Мұны істеудің баламалы тәсілі – ішінара реттің транзитивті қысқартуын пайдалану; әдетте, бұл аз жиектері бар DAG-ді тудырады, бірақ бұл DAG-дегі қол жетімділік қатынасы сол ішінара рет болып қалады. Осы құрылымдарды пайдалану арқылы топологиялық реттеу алгоритмдерін ішінара реттің сызықтық кеңейтілуін табу үшін қолдануға болады.
Topological orderings are also closely related to the concept of a linear extension of a partial order in mathematics. A partially ordered set is just a set of objects together with a definition of the "≤" inequality relation, satisfying the axioms of reflexivity (x ≤ x), antisymmetry (if x ≤ y and y ≤ x then x = y) and transitivity (if x ≤ y and y ≤ z, then x ≤ z). A total order is a partial order in which, for every two objects x and y in the set, either x ≤ y or y ≤ x. Total orders are familiar in computer science as the comparison operators needed to perform comparison sorting algorithms. For finite sets, total orders may be identified with linear sequences of objects, where the "≤" relation is true whenever the first object precedes the second object in the order; a comparison sorting algorithm may be used to convert a total order into a sequence in this way. A linear extension of a partial order is a total order that is compatible with it, in the sense that, if x ≤ y in the partial order, then x ≤ y in the total order as well. One can define a partial ordering from any DAG by letting the set of objects be the vertices of the DAG, and defining x ≤ y to be true, for any two vertices x and y, whenever there exists a directed path from x to y; that is, whenever y is reachable from x. With these definitions, a topological ordering of the DAG is the same thing as a linear extension of this partial order. Conversely, any partial ordering may be defined as the reachability relation in a DAG. One way of doing this is to define a DAG that has a vertex for every object in the partially ordered set, and an edge xy for every pair of objects for which x ≤ y. An alternative way of doing this is to use the transitive reduction of the partial ordering; in general, this produces DAGs with fewer edges, but the reachability relation in these DAGs is still the same partial order. By using these constructions, one can use topological ordering algorithms to find linear extensions of partial orders.
Жоспарлауды оңтайландыруға қатысты
Анықтама бойынша, артықшылық графы бар жоспарлау мәселесінің шешімі топологиялық сұрыптаудың жарамды шешімі болып табылады (машиналар санына қарамастан), бірақ топологиялық сұрыптаудың өзі жоспарлауды оңтайландыру мәселесін оңтайлы шешуге жеткіліксіз. Ху алгоритмі – артықшылық графы мен өңдеу уақытын қажет ететін (барлық жұмыстардың ең үлкен аяқталу уақытын азайту мақсатында) жоспарлау мәселелерін шешуге қолданылатын танымал әдіс. Топологиялық сұрыптау сияқты, Ху алгоритмі де бірегей емес және оны DFS (ең ұзын жол ұзындығын тауып, содан кейін жұмыстарды тағайындау арқылы) көмегімен шешуге болады.
By definition, the solution of a scheduling problem that includes a precedence graph is a valid solution to topological sort (irrespective of the number of machines), however, topological sort in itself is not enough to optimally solve a scheduling optimisation problem. Hu's algorithm is a popular method used to solve scheduling problems that require a precedence graph and involve processing times (where the goal is to minimise the largest completion time amongst all the jobs). Like topological sort, Hu's algorithm is not unique and can be solved using DFS (by finding the largest path length and then assigning the jobs).