(store, vertices, valid_head_fn, stats_fn=Performance.get_statistics, prune=True, greedy=False, **kwargs)
| 102 | return effort_orders |
| 103 | |
| 104 | def dynamic_programming(store, vertices, valid_head_fn, stats_fn=Performance.get_statistics, prune=True, greedy=False, **kwargs): |
| 105 | # TODO: include context here as a weak constraint |
| 106 | # TODO: works in the absence of partial orders |
| 107 | # TODO: can also more manually reorder |
| 108 | # 2^N rather than N! |
| 109 | start_time = time.time() |
| 110 | effort_orders = set() # 1 cheaper than 2 |
| 111 | if prune: |
| 112 | effort_orders.update(compute_pruning_orders(vertices, stats_fn=stats_fn, **kwargs)) |
| 113 | _, out_priority_orders = neighbors_from_orders(effort_orders) # more expensive |
| 114 | priority_ordering = topological_sort(vertices, effort_orders)[::-1] # most expensive to cheapest |
| 115 | # TODO: can break ties with index on action plan to prioritize doing the temporally first things |
| 116 | |
| 117 | # TODO: could the greedy strategy lead to premature choices |
| 118 | # TODO: this starts to blow up - group together similar streams (e.g. collision streams) to decrease size |
| 119 | # TODO: key grouping concern are partial orders and ensuring feasibility (isomorphism) |
| 120 | # TODO: flood-fill cheapest as soon as something that has no future dependencies has been found |
| 121 | # TODO: do the forward version to take advantage of sink vertices |
| 122 | subset = frozenset() |
| 123 | queue = deque([subset]) # Acyclic because subsets |
| 124 | subproblems = {subset: Subproblem(cost=0, head=None, subset=None)} |
| 125 | while queue: # searches backward from last to first |
| 126 | if store.is_terminated(): |
| 127 | return vertices |
| 128 | subset = queue.popleft() # TODO: greedy/weighted A* version of this (heuristic is next cheapest stream) |
| 129 | applied = set() |
| 130 | # TODO: roll-out more than one step to cut the horizon |
| 131 | # TODO: compute a heuristic that's the best case affordances from subsequent streams |
| 132 | for v in priority_ordering: # most expensive first |
| 133 | if greedy and applied: |
| 134 | break |
| 135 | if (v not in subset) and valid_head_fn(v, subset) and not (out_priority_orders[v] & applied): |
| 136 | applied.add(v) |
| 137 | new_subset = frozenset([v]) | subset |
| 138 | p_success, overhead = stats_fn(v) |
| 139 | new_cost = overhead + p_success*subproblems[subset].cost |
| 140 | subproblem = Subproblem(cost=new_cost, head=v, subset=subset) # Adds new element to the front |
| 141 | if new_subset not in subproblems: |
| 142 | queue.append(new_subset) |
| 143 | subproblems[new_subset] = subproblem |
| 144 | elif new_cost < subproblems[new_subset].cost: |
| 145 | subproblems[new_subset] = subproblem |
| 146 | |
| 147 | ordering = [] |
| 148 | subset = frozenset(vertices) |
| 149 | while True: |
| 150 | if subset not in subproblems: |
| 151 | print(vertices) |
| 152 | # TODO: some sort of bug where the problem isn't solved? |
| 153 | subproblem = subproblems[subset] |
| 154 | if subproblem.head is None: |
| 155 | break |
| 156 | ordering.append(subproblem.head) |
| 157 | subset = subproblem.subset |
| 158 | #print('Streams: {} | Expected cost: {:.3f} | Time: {:.3f}'.format( |
| 159 | # len(ordering), compute_expected_cost(ordering, stats_fn=stats_fn), elapsed_time(start_time))) |
| 160 | return ordering |
| 161 |
no test coverage detected