-
-
Save zdxerr/a732fa0748d56c3cbc52 to your computer and use it in GitHub Desktop.
Given a search space S with solution candidates. A control strategy is called systematic if
a. all objects in S are considered, b. each objects in S is considered only once.
A search that employs a systematic control strategy is called systematic search. Condition (a) implies completeness, condition (b) implies efficiency.
Given a search space S with solution candidates. The information that explicitly describes the rest problem associated with a solution base S' ⊂ S is called state.
The set of all problems that can be generated by applying the operators to the database is called state-space. One obtains the state-space graph
- by connecting each parent node with its generated successors using directed links, and
- by labeling the links with the applied operator.
Let G be a state-space graph with root node s, and let γ, γ ∈ G be a goal node (a node with a trivial rest problem). Then a path P(γ) from s to γ is called solution path for s.
Consider the set of all problems that can be generated by applying either the operators or a problem decomposition to the database. One obtains the problem-reduction graph or AND-OR graph by
- connecting each parent node with its generated successors using directed links,
- labeling those links that belong to an operator with the applied operator, and
- comprising those links that belong to a problem decomposition as sibling links.
Let H be an acyclic AND-OR graph, and let n be a node in H. A finite subgraph G of H is called a solution graph for n in H iff the following conditions hold:
Gcontains the noden.- If
Gcontains an inner OR node, thenGcontains exactly one link to a successor node inH. - If
Gcontains an inner AND node, thenGcontains all links to its successor nodes inH. - The leaf nodes in
Gbelong to trivial or solved rest problems inH. Gis minimal: it contains no additional nodes and edges.
Let H be an acyclic AND-OR graph. A problem associated with a node n in H is labeled as solved, if one of the following conditions is fulfilled.
nis a leaf node (terminal node) that represents a solved rest problem.nis a nonterminal OR node, and at least one of its OR links points to a node labeled as solved.nis a nonterminal AND node, and all of its AND links point to nodes labeled as solved.
Let G be a state-space graph with root node s, and let n, n ∈ G be a node that is currently not labeled unsolvable. Then a path P(n) from s to n is called solution base for s.
Let H be an acyclic AND-OR graph, and let n be a node in H. A finite subgraph G of H is called a solution base for n in H iff the following conditions hold:
-
Gcontains the noden. -
If
Gcontains an inner OR node, thenGcontains exactly one link to a direct successor inH. -
If
Gcontains an inner AND node, thenGcontains all links to its direct successors inH. -
None of the leaf nodes in
Gis currently labeled unsolvable. -
Gis minimal: it contains no additional nodes and edges.Simply put, a subgraph of a search space graph is called solution base if it can be extended towards a solution (graph).
Let G = (V, E) be a solution graph rooted at node s, and let M be an ordered set. A function CG : V → M, which assigns each node n in G a cost value CG(n), is called a cost function.
For a solution path P(γ) from s to γ, the cost function which assigns each node n in P(γ) a cost value is denoted as CP(γ).
Let H be an acyclic AND-OR graph with root node s, let n be a node in H, and let CG denote the cost function for solution graphs G. Then the optimum solution cost for n, C∗(n), is defined as
C∗(n) = inf{CG(n) | G is solution graph}
Similarly, for a cost function CP(γ) for solution paths P(γ), the optimum solution cost for n is defined as
C∗(n) = inf{CP(γ)(n) | P(γ) is solution path}
A solution graph (path) with solution cost C∗(n) is called optimum solution graph (path) for n. The optimum solution cost for s, C∗(s), is abbreviated as C∗.
A cost function CG for a solution graph G is called recursive, if for each node n in G holds:
CG(n) = F[E(n), CG(n1), CG(n2), ..., CG(nk)], where
n1,n2, ...,nkdenote the direct successors ofninG,E(n) ∈ Edenotes a set of local properties ofn,Fis a function that prescribes how local properties ofnare accounted (better: combined) with properties of the direct successors ofn:F : E × Mk → M, whereMis an ordered set.
Similarly, a cost function CP(γ) for solution paths P(γ) is called recursive, if CP(γ)(γ) depends solely on E(γ) and for each node n != γ in P(γ) with direct successor n' in P(γ) holds:
CP(γ)(n) = F[E(n), CP(γ)(n')]
F is called cost measure.
Let G be a search space graph with Prop(G). The subgraph maintained by Algorithm A* defined by the backpointers assigned to the nodes is called traversal tree, denoted as T.
A path in the traversal tree T is called pointer-path, denoted as P_P. The unique pointer-path from s to n is denoted as P_Ps−n.
Let G be a search space graph with Prop(G), n, n1, n2 nodes in G, s the start node, and γ a goal node in G. Γ denotes the set of all goal nodes in G.
Pn1−n2denotes a path fromn1ton2inG.**P**n1−n2denotes the set of all paths fromn1ton2inG.k(n1, n2)denotes the cost of a cheapest path fromn1ton2.**P**\∗n1−n2denotes the set of cheapest cost paths fromn1ton2.**P**n−Γdenotes the set of paths fromnto a node inΓ.**P**\∗n−Γdenotes the set of cheapest paths fromnto a node inΓ.C∗ = min γ∈Γ k(s, γ)denotes the cost of a cheapest path fromsto a node inΓ.Γ∗denotes the set of goal nodes that can be reached fromswith costC∗.
Let Ps−γ be a path in **P**s−Γ and n an intermediate node on Ps−γ.
10. gPs−γ(n) denotes the path cost of the initial part of Ps−γ from s to n.
11. hPs−γ(n) denotes the path cost of following part of Ps−γ from n to γ.
12. g∗(n) denotes the cost of a cheapest path from s to n, i.e., g∗(n) = k(s, n).
13. h∗(n) = min γ∈Γ k(n, γ) denotes the cost of a cheapest path from n to Γ.
14. f∗(n) denotes the optimum cost over all solution paths constrained to go
through n, i.e., f∗(n) = g∗(n) + h∗(n).
g(n)denotes the path cost value for the pointer-pathP_Ps−n.h(n)denotes the estimated cheapest path cost of paths inPn−Γ.f(n) = g(n) + h(n).
- An algorithm is complete if it terminates with a solution if a solution exists.
- An algorithm is admissible if it terminates with an optimum solution if a solution exists.
Let G be a search space graph with Prop(G), P = (n1, n2, . . . , nl), n1 = s, be an arbitrary path in G, and let G be processed by A*. The node ni , 1 ≤ i ≤ l, is the shallowest OPEN node on P iff (↔) ni
is on OPEN and none of the nodes n1, . . . , ni−1 is on OPEN.
The shallowest OPEN node on a path P is the first OPEN node which we come
across when following P starting from s.
Let G be a search space graph with Prop(G). A heuristic function h is called admissible iff (↔) h(n) ≤ h∗(n) for all n ∈ G.
Thus an admissible heuristic function h provides an optimistic estimate of the cheapest solution cost for a node in G. Similarly, the A* evaluation function f = g + h with admissible h provides an optimistic estimate of the cheapest solution cost for s with respect to the current traversal tree.
Let H be an acyclic AND-OR graph. A problem associated with a node n in H is labeled as solved, if one of the following conditions is fulfilled.
- n is a leaf node (terminal node) that represents a solved rest problem.
- n is a nonterminal OR node, and at least one of its OR links points to a node labeled as “solved”.
- n is a nonterminal AND node, and all of its AND links point to nodes labeled as “solved”.
Return TRUE if a solution exists.
solved_labeling(H, n):
1. If n is SOLVED return TRUE
2. If n has no successors
a. If n is a goal node mark n as SOLVED and return TRUE
b. Else return FALSE
3. Node n is neither solved, nor a goal or terminal node. Apply solved_labeling() to all succesors of n.
a. If n is an OR node and there is a solution for one successor of n, mark n as solved and return TRUE
b. If n is an AND node and there is a solution for all successors of n and, mark n as solved and return TRUE
c. Else return FALSE
OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
1. Remove the best node from OPEN, call it n, add it to CLOSED.
2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
3. Create n's successors.
4. For each successor do:
a. If it is not in CLOSED and it is not in OPEN: evaluate it, add it to OPEN, and record its parent.
b. Otherwise, if this new path is better than previous one, change its recorded parent.
i. If it is not in OPEN add it to OPEN.
ii. Otherwise, adjust its priority in OPEN using this new evaluation.
done
Uses delayed termination, because when reaching a node a node for the first time it can not be detemined if the used path is optimal.
-
f1evaluates solution bases -
f2returns the most informative successor node for a solution base -
Hdenotes the currently explored part of the graphOPEN = [] CLOSED = [initial state] H = explore(successors(initial state)) repeat 1. Get the solution base G0 with minimal f1 from H 2. Apply solved_labeling(H, s) 3. Determine the most inforamtive successor node n of G0 using f2 4. Remove node n from OPEN and add to CLOSED. 5. H = explore(successors(n)) 6. For each successor n' of n do: a. If n' is a goal node, add n' to CLOSED b. If n' is a dead end, return FALSE c. Else add n' to OPEN and clean up H done
Gis locally finite.Ghas a positive lower boundδof edge costs. It holdsc(n,n') ≥ δ > 0for all edges(n, n')inG.
- There is a path
Ps-γfromstoγ. - At any point before A* terminates, there is always a shallowest OPEN node
n'onPs-γ. - M = max f(n) for all n in Ps-γ.
- A* will never expand a node n with f(n) > M.
- The set of nodes n, that are reachable with f(n) <= M is finite.
- A* will chose γ after a finitly many node expansions.
n ∈ Ps−γ ∈ P*s−Γ ⇒ f*(n) = g*(n) + h*(n) = C*
- Let
Ps−γbe an optimum solution path that containsn. - gP(n) + hP(n) = C*.
- g*(n) <= gP(n) and h*(n) <= hP(n).
- If gP(n) > g*() or hP(n) > h*(n), there would be a cheaper path from s to γ. This contradicts optimality.
- Hence, g*(n) = gP(n) and h*(n) = hP(n) ⇒ g*(n) + h*(n) = C*
An admissible heuristic function h provides an optimistic estimate of the cheapest solution cost for a node in G.
h(n) <= h*(n) for all n in G
- There is a solution path in
G. - Completeness ⇒ A* will terminate.
- Assume A* returns a non-optimum goal node
γinΓwithf(γ) = g(γ) > C*. - Since A* selected
γfrom OPEN,f(n) >= f(γ) > C*for all n in OPEN. - Contradiction: There is an OPEN node
n'withf(n') <= C*(C* bounded OPEN node).
| #!/usr/bin/python | |
| """ | |
| """ | |
| import itertools | |
| from pprint import pprint | |
| initial_left = (3, 3) | |
| def cross(state, boat): | |
| (ml, cl), pos = state | |
| if pos == 'left': | |
| new_state = ((ml - boat.count('m'), cl - boat.count('c')), 'right') | |
| else: | |
| new_state = ((ml + boat.count('m'), cl + boat.count('c')), 'left') | |
| return new_state | |
| def done(state): | |
| return state[0] == (0, 0) | |
| def invalid(state): | |
| (ml, cl), pos = state | |
| mr, cr = initial_left[0] - ml, initial_left[1] - cl | |
| return ((ml > 0 and ml < cl) or | |
| (mr > 0 and mr < cr)) | |
| def find_path(): | |
| queue = [((tuple(initial_left), 'left'), )] | |
| seen = set() | |
| counter = 0 | |
| while queue: | |
| counter +=1 | |
| if counter > 100: | |
| raise Exception('Overrun') | |
| path = queue.pop(-1) | |
| state = path[-1] | |
| (ml, cl), pos = state | |
| mr, cr = initial_left[0] - ml, initial_left[1] - cl | |
| # left[None] = 1 | |
| if pos == 'left': | |
| people = ['m'] * ml + ['c'] * cl + [None] | |
| else: | |
| people = ['m'] * mr + ['c'] * cr + [None] | |
| for c in set(itertools.combinations(people, 2)): | |
| new_state = cross(state, c) | |
| if new_state in seen: | |
| continue | |
| seen.add(new_state) | |
| new_path = path + (new_state, ) | |
| if invalid(new_state): | |
| continue #invalid state found | |
| elif done(new_state): | |
| return new_path | |
| else: | |
| queue.append(new_path) | |
| return None | |
| result = find_path() | |
| for ((m1, c1), p1), ((m2, c2), p2) in zip(result, result[1:]): | |
| print('{} -> {} [m: {}, c:{}]'.format(p1, p2, abs(m2-m1), abs(c2-c1))) |
| from queue import PriorityQueue | |
| from itertools import chain | |
| from functools import lru_cache | |
| object_weights = { | |
| 'A': 1, | |
| 'B': 4, | |
| 'C': 6, | |
| 'D': 7, | |
| 'E': 7, | |
| 'F': 9, | |
| 'G': 11, | |
| 'H': 13, | |
| 'I': 15, | |
| 'J': 16, | |
| # 'K': 5, | |
| } | |
| package_weight = 20 | |
| # package cost is redundant, since the model minimizes the number of packages | |
| package_cost = 9.9 | |
| class Packages(list): | |
| def objects_packed(self): | |
| return set(chain(*self)) | |
| def optimal_packaging(object_weights, package_weight, package_cost): | |
| # priority queue | |
| # initial state, list of packages is empty | |
| OPEN = [Packages()] | |
| CLOSED = [] | |
| SEEN = set() | |
| i = 0 | |
| while OPEN: | |
| # print('OPEN {!r}'.format(OPEN)) | |
| packages = OPEN.pop(0) | |
| CLOSED.append(packages) | |
| packages = Packages(packages) | |
| objects_packed = packages.objects_packed() | |
| if set(object_weights.keys()) == objects_packed: | |
| return packages | |
| try: | |
| current_package = packages.pop(-1) | |
| except IndexError: | |
| current_package = set() | |
| for object_name, object_weight in object_weights.items(): | |
| if object_name in objects_packed: | |
| continue | |
| new_packages = Packages(packages) | |
| package = set(current_package) | |
| w = sum(object_weights[o] for o in package) + object_weight | |
| if w > package_weight: | |
| new_packages.append(package) | |
| package = set() | |
| package.add(object_name) | |
| new_packages.append(package) | |
| new_objects_packed = new_packages.objects_packed() | |
| if new_objects_packed in SEEN: # performance hack | |
| for p in OPEN + CLOSED: | |
| if p.objects_packed() == new_objects_packed: | |
| if len(p) > len(new_packages): | |
| try: | |
| OPEN.remove(p) | |
| except ValueError: | |
| pass | |
| try: | |
| CLOSED.remove(p) | |
| except ValueError: | |
| pass | |
| OPEN.append(new_packages) | |
| break | |
| else: | |
| SEEN.add(frozenset(new_objects_packed)) | |
| OPEN.append(new_packages) | |
| OPEN.sort(key = lambda s: len(s)) | |
| packages = optimal_packaging(object_weights, package_weight, package_cost) | |
| for package in packages: | |
| print(package, sum(object_weights[o] for o in package)) |