9/19/2023 0 Comments Timetable generator algorithmThe subalgorithms form a search tree in a natural way, with the original problem at the root and with level k containing each subalgorithm that corresponds to k chosen rows.īacktracking is the process of traversing the tree in preorder, depth first.Īny systematic rule for choosing column c in this procedure will find all solutions, but some rules work much better than others. If column c is entirely zero, there are no subalgorithms and the process terminates unsuccessfully. The nondeterministic choice of r means that the algorithm recurses over independent subalgorithms each subalgorithm inherits the current matrix A, but reduces it with respect to a different row r. Repeat this algorithm recursively on the reduced matrix A.For each column j such that A r, j = 1,ĭelete row i from matrix A.Choose a row r such that A r, c = 1 ( nondeterministically). Otherwise choose a column c ( deterministically). # If the matrix A has no columns, the current partial solution is a valid solution terminate successfully.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |