CSE 473 Chapter 3 Problem Solving Using Search

1y ago
25 Views
1 Downloads
2.74 MB
30 Pages
Last View : 4m ago
Last Download : 5m ago
Upload by : Bennett Almond
Transcription

CSE 473Chapter 3Problem Solving using Search“First, they do an on-line search” CSE AI FacultyExample: The 8-puzzleStartGoal1 2 3481 2 34 5 67 87 6 521

Example: Route Planning3Example: N Queens4 Queens problem(Place queens such that no queen attacks any other)42

Example: N Queens4 Queens5State-Space Search ProblemsGeneral problem:Find a path from a start state to a goal state given: A goal test: Tests if a given state is a goal state A successor function (transition model): Given a state,generates its successor statesVariants: Find any path vs. a least-cost path Goal is completely specified, task is just to find the path– Route planning Path doesn’t matter, only finding the goal state– 8 puzzle, N queens, Rubik’s cube63

Example: Simplified Pac-ManInput: State space Successor function“N”, 1.0“E”, 1.0 Start state Goal testSearch Trees“N”, 1.0“E”, 1.0A search tree: Root Start state Children successor states Edges actions and costs Path from Start to a node is a “plan” to get to that state For most problems, we can never actually build thewhole tree (why?)4

State Space Graph versus Search TreesState Space Graph(graph of states with arrows pointing to successors)GacbedSfhprqState Space Graph versus Search TreesGacbedSfhprqSedSearch Treeebcaa hp qqphrrp qffqc GacqGa5

Search Tree for 8-Puzzle11126

Searching with Search TreesSearch: Expand out possible nodes Maintain a fringe of as yet unexpanded nodes Try to expand as few tree nodes as possible147

15Handling Repeated StatesFailure to detect repeated states (e.g., in 8 puzzle) can causeinfinite loops in searchSTARTaGOALexpandexpandbGraph Search algorithm: Augment Tree-Search to storeexpanded nodes in a set called explored set (or closed set)and only add new nodes not in the explored set to the fringe168

17189

192010

212211

232412

b b2 b3 bd O(bd ) i.e. exp in d25b b2 b3 bd O(bd ) i.e. exp in dO (b d )2613

b b2 b3 bd O(bd ) i.e. exp in dO ( bd )Yes if all step costs are equal. Not optimal in general.Space and time are big problems for BFS.Example: b 10, 1000,000 nodes/sec, 1000 Bytes/noded 2 110 nodes, 0.11 millisecs, 107KBd 4 11,110 nodes, 11 millisecs, 10.6 MBd 8 108 nodes, 2 minutes, 103 GBd 16 1016 nodes, 350 years, 10 EB (1 billion GB)27What if the step costs are notequal?Can we modify BFS to handle any stepcost function?2814

g (n ) (Use priority queue)O(b C*O(b C )/ 1* )/ 1293015

313216

333417

353618

373819

394020

414221

(using “explored” set)43(using “explored” set)4422

(using “explored” set)45(using “explored” set)Space cost is a big advantage of DFS over BFS.Example: b 10, 1000 Bytes/noded 16 156 KB instead of 10 EB (1 billion GB)4623

(can handle infinite state spaces)47 DFS with increasing depth limit Finds the best depth limit Combines the benefits of DFS and BFS4824

495025

515226

535427

555628

Yes if all step costs are equal. Not optimal in general.Increasing path-cost limits instead of depth limitsThis is called Iterative lengthening search (exercise 3.17)57Forwards vs. BackwardsProblem: Find the shortest route5829

Bidirectional SearchMotivation: bd/2 bd/2 bd(E.g., 108 108 2 108 1016)Can use breadth-first search or uniform-cost searchHard for implicit goals e.g., goal “checkmate” in chess59Can we do better?All these methods are slow (because they are “blind”)Solution use problem-specific knowledge toguide search (“heuristic function”) “informed search” (next lecture)To Do Start Project #1 Read Chapter 36030

Problem Solving using Search . c e h a f r State Space Graph (graph of states with arrows pointing to successors) S a b e d p a c h e p f r q q c a q p h f r q q c G a S G d b p q c e h a f r Search Tree State Space Graph versus Search Trees G . 6 11 Search Tree for 8-Puzzle 12 . 7

Related Documents:

92 vipul sharma it 93 rishabh jain cse 94 manik arora cse 95 nishant bhardwaj cse . 96 rajit shrivastava it 97 shivansh gaur cse 98 harsh singh cse 99 shreyanshi raj cse 100 rahul bedi cse 101 pallavi anand cse 102 divya cse 103 nihal raj it 104 kanak

cse-148 kuriakose jijo george n t george cse-149 kusum joshi ramesh chandra joshi cse-150 m mithun bose n k mohandasan cse-151 madhuri yadav rajbir yadav cse-152 malini shukla r s sharma cse-153 manisha khattar sunil kumar khattar cse-154 m

Part One: Heir of Ash Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26 Chapter 27 Chapter 28 Chapter 29 Chapter 30 .

DEDICATION PART ONE Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 PART TWO Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 .

1 CSE 474 Introduction 1 CSE 474 – Introduction to Embedded Systems n Instructor: q Bruce Hemingway n CSE 464, Office Hours: 11:00-12:00 p.m., Tuesday, Thursday n or whenever the door is open n bruceh@cs.washington.edu q Teaching Assistants: q Cody Ohlsen, Kendall Lowrey and Ying-Chao (Tony) Tung CSE 474 Introduction 2

CSE Citation Style – Quick Guide 7th Edition 1 This guide outlines how to cite some of the more common information sources in the Council of Science Editor’s (CSE) Style Name-Year system. For a comprehensive listing, please consult: Scientific Style and Format: The CSE Manual for Authors, Editors, and Publishers, 7th edition

F14 CSE550 45 Combinatorial Algorithms and Intractability S14 CSE 555 46 Advanced Theory of Computation S14 CSE591/MAT591 40 Combinatorial Design Theory F13 CSE 355 82 Intro Theory of Computation F13 CSE 552 32 Randomized and Approximation Algorithms S13 CSE 555 30 Advanced Theory of Computation S1

PowerPoint presentation CSE Training Handbook Contains the WAC 296-809-100 Outlines what you must do CSE Training Resource Tools for setting up your CSE program Confined Space Entry Program Resources Four Major Sections: WAC 296-809 –Confined Spaces Identify and Control permit-requi

Sehgal ADGITM 1st Shift IT 07915603120 9.95 5186 0.9576 CSE 1st shift ALLOTED CSE 6 Mansi Gupta Mr. Rajesh . 36 Md. Areeb Inam Mr. Inam Mohammad ADGITM 1st Shift IT 07315603120 9.85 5055 0.932 CSE 1st shift . 46 Rohit Mr. Ranjit Prasad Sah ADGITM 1st Shift IT 10615603120 9.8 4962 0.9168 CSE 1st shift NO VACANCY 47 Kritika

JCIDS Manual added Cyber Survivability Endorsement (CSE) to SS -KPP o. Jan 2017: JS formally approved CSE Implementation Guide (IG) o. Feb 2017: DoD-CIO published CSE -IG companion document o. Feb 2018: DAU RQM-310, Adv Requirements Mgmt curriculum includes CSE o. Apr 2018: OUSD(R&E) and DOT&E DoD Cybersecurity Test and Evaluation Guidebook .

About the husband’s secret. Dedication Epigraph Pandora Monday Chapter One Chapter Two Chapter Three Chapter Four Chapter Five Tuesday Chapter Six Chapter Seven. Chapter Eight Chapter Nine Chapter Ten Chapter Eleven Chapter Twelve Chapter Thirteen Chapter Fourteen Chapter Fifteen Chapter Sixteen Chapter Seventeen Chapter Eighteen

18.4 35 18.5 35 I Solutions to Applying the Concepts Questions II Answers to End-of-chapter Conceptual Questions Chapter 1 37 Chapter 2 38 Chapter 3 39 Chapter 4 40 Chapter 5 43 Chapter 6 45 Chapter 7 46 Chapter 8 47 Chapter 9 50 Chapter 10 52 Chapter 11 55 Chapter 12 56 Chapter 13 57 Chapter 14 61 Chapter 15 62 Chapter 16 63 Chapter 17 65 .

HUNTER. Special thanks to Kate Cary. Contents Cover Title Page Prologue Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter

Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 . Within was a room as familiar to her as her home back in Oparium. A large desk was situated i

The Hunger Games Book 2 Suzanne Collins Table of Contents PART 1 – THE SPARK Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8. Chapter 9 PART 2 – THE QUELL Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapt

California Code of Civil Procedure (CCP) §§ 473(b), 473(d), 473.5 and Civil Code (Civ) § 1788.61 specify the most common grounds upon which you can base a motion for relief from default or default judgment. These grounds include: Inadvertence, Surprise, Mistake, or Excusable Neglect

Mary Barton A Tale of Manchester Life by Elizabeth Cleghorn Gaskell Styled byLimpidSoft. Contents PREFACE1 CHAPTER I6 CHAPTER II32 CHAPTER III51 CHAPTER IV77 CHAPTER V109 CHAPTER VI166 CHAPTER VII218 i. CHAPTER VIII243 CHAPTER IX291 CHAPTER X341 CHAPTER XI381 CHAPTER XII423 CHAPTER XIII450 CHAPTER XIV479 CHAPTER XV513 CHAPTER XVI551

May 15, 2008 · CHAPTER THREE CHAPTER FOUR CHAPTER FIVE CHAPTER SIX CHAPTER SEVEN CHAPTER EIGHT CHAPTER NINE CHAPTER TEN CHAPTER ELEVEN . It is suggested that there is a one-word key to the answer among the four lofty qualities which are cited on every man's commission. . CHAPTER TWO. CHAPTER THREE.

Book II Chapter I Chapter II Chapter III Chapter IV Chapter V Chapter VI Chapter VII Chapter VIII Chapter IX Chapter X Chapter XI Chapter XII Chapter XIII Chapter XIV Book III . The Storm and Stress period in German literature had been succeeded by the Romantic movement, but Goethe's classicism rendered him unsympathetic to it. Nevertheless .

J. Chil. Chem. Soc., 59, N 4 (2014) 2747 EXPERIMENTAL ACTIVITIES IN THE LABORATORY OF ANALYTICAL CHEMISTRY UNDER AN INQUIRY APPROACH HELEN ARIAS 1, LEONTINA LAZO1*, FRANCISCO CAÑAS2 1Intituto de Química, Facultad de Ciencias, Pontificia Universidad Católica de Valparaíso, Avenida Universidad 330, Curauma, Valparaíso, Chile. 2Universidad Andres Bello, Departamento de Química, Facultad de .