Introduction to artificial intelligence А* Search - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Introduction to artificial intelligence А* Search, слайд №1

Introduction to artificial intelligence А* Search, слайд №2

Introduction to artificial intelligence А* Search, слайд №3

Introduction to artificial intelligence А* Search, слайд №4

Introduction to artificial intelligence А* Search, слайд №5

Introduction to artificial intelligence А* Search, слайд №6

Introduction to artificial intelligence А* Search, слайд №7

Introduction to artificial intelligence А* Search, слайд №8

Introduction to artificial intelligence А* Search, слайд №9

Introduction to artificial intelligence А* Search, слайд №10

Introduction to artificial intelligence А* Search, слайд №11

Introduction to artificial intelligence А* Search, слайд №12

Introduction to artificial intelligence А* Search, слайд №13

Introduction to artificial intelligence А* Search, слайд №14

Introduction to artificial intelligence А* Search, слайд №15

Introduction to artificial intelligence А* Search, слайд №16

Introduction to artificial intelligence А* Search, слайд №17

Introduction to artificial intelligence А* Search, слайд №18

Introduction to artificial intelligence А* Search, слайд №19

Introduction to artificial intelligence А* Search, слайд №20

Introduction to artificial intelligence А* Search, слайд №21

Introduction to artificial intelligence А* Search, слайд №22

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Introduction to artificial intelligence А* Search. Доклад-сообщение содержит 22 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Introduction to Artificial Intelligence A* Search Ruth Bergman Fall 2004

Слайд 2

Описание слайда:

Best-First Search Review Advantages Takes advantage of domain information to guide search Greedy advance to the goal Disadvantages Considers cost to the goal from the current state Some path can continue to look good according to the heuristic function

Слайд 3

Описание слайда:

The A* Algorithm

Слайд 4

Описание слайда:

The A* Algorithm A*-Search(initial-test) ;; functions cost, h, succ, and GoalTest are defined open

Слайд 5

Описание слайда:

A* Search: Example Travel: h(n) = distance(n, goal)

Слайд 6

Описание слайда:

A* Search : Example

Слайд 7

Описание слайда:

Admissible Heuristics we also require h be admissible: a heuristic h is admissible if h(n) < h*(n) for all nodes n, where h* is the actual cost of the optimal path from n to the goal Examples: travel distance straight line distance must be shorter than actual travel path tiles out of place each move can reorder at most one tile distance of each out of place tile from the correct place each move moves a tile at most one place toward correct place

Слайд 8

Описание слайда:

Optimality of A* Let us assume that f is non-decreasing along each path if not, simply use parent’s value if that’s the case, we can think of A* as expanding f contours toward the goal; better heuristics make this contour more “eccentric” Let G be an optimal goal state with path cost f* Let G2 be a suboptimal goal state with path cost g(G2) > f*. suppose A* picks G2 before G (A* is not optimal) suppose n is a leaf node on the path to G when G2 is chosen if h is admissible, then f* >= f(n) since n was not chosen, it must be the case that f(n) >= f(G2) therefore f* >= f(G2), but since G2 is a goal, h(G2)=0, so f* >= g(G2) But this is a contradiction --- G2 is a better goal node than G Thus, our supposition is false and A* is optimal.

Слайд 9

Описание слайда:

Completeness of A* Suppose there is a goal state G with path cost f* Intuitively: since A* expands nodes in order of increasing f, it must eventually expand node G If A* stops and fails Prove by contradiction that this is impossible. There exists a path from the initial state to the node state Let n be the last node expanded along the solution path n has at least one child, that child should be in the open nodes A* does not stop until there are open list is empty (unless it finds a goal state). Contradiction. A* is on an infinite path Recall that cost(s1,s2) >  Let n be the last node expanded along the solution path After f(n)/the cumulative cost of the path becomes large enough that A* will expand n. Contradiction.

Слайд 10

Описание слайда:

UCS, BFS, Best-First, and A* f = g + h => A* Search h = 0 => Uniform cost search g = 1, h = 0 => Breadth-First search g = 0 => Best-First search

Слайд 11

Описание слайда:

Road Map Problem

Слайд 12

Описание слайда:

8-queens State contains 8 queens on the board Successor function returns all states generated by moving a single queen to another square in the same column (8*7 = 56 next states) h(s) = number of queens that attack each other in state s.

Слайд 13

Описание слайда:

Heuristics : 8 Puzzle

Слайд 14

Описание слайда:

8 Puzzle Reachable state : 9!/2 = 181,440 Use of heuristics h1 : # of tiles that are in the wrong position h2 : sum of Manhattan distance

Слайд 15

Описание слайда:

Effect of Heuristic Accuracy on Performance Well-designed heuristic have its branch close to 1 h2 dominates h1 iff h2(n)  h1(n),  n It is always better to use a heuristic function with higher values, as long as it does not overestimate Inventing heuristic functions Cost of an exact solution to a relaxed problem is a good heuristic for the original problem collection of admissible heuristics h*(n) = max(h1(n), h2(n), …, hk(n))

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

A* summary Completeness provided finite branching factor and finite cost per operator Optimality provided we use an admissible heuristic Time complexity worst case is still O(bd) in some special cases we can do better for a given heuristic Space complexity worst case is still O(bd)

Слайд 18

Описание слайда:

Relax Optimality Goals: Minimizing search cost Satisficing solution, i.e. bounded error in the solution f(s) = (1-w) g(s) + w h(s) g can be thought of as the breadth first component w = 1 => Best-First search w = .5 => A* search w = 0 => Uniform search

Слайд 19

Описание слайда:

Iterative Deepening A* Goals A storage efficient algorithm that we can use in practice Still complete and optimal Modification of A* use f-cost limit as depth bound increase threshold as minimum of f(.) of previous cycle Each iteration expands all nodes inside the contour for current f-cost same order of node expansion

Слайд 20

Описание слайда:

IDA* Algorithm IDA* (state,h) returns solution f-limit

Слайд 21

Описание слайда:

IDA* Properties Complete: if shortest path fits into memory Optimal: if shortest optimal path fits into memory Time Complexity: O(b2d) Space Complexity: O(bd)

Слайд 22

Описание слайда:

Mapquest MapQuest uses a "double Dijkstra" algorithm for its driving directions, working backward from both the starting and ending points at once. MapQuest uses a "double Dijkstra" algorithm for its driving directions, working backward from both the starting and ending points at once. the algorithm uses heuristic tricks to minimize the size of the graph that must be searched.