HSM

Information about HSM

Published on March 19, 2009

Author: ankush85

Source: authorstream.com

Content

Heuristic Search Methods : Heuristic Search Methods Methods that use a heuristic function to provide specific knowledge about the problem: Heuristic Functions Hill climbing Beam search Hill climbing (2) Greedy search Heuristic Functions : 2 Heuristic Functions To further improve the quality of the previous methods, we need to include problem-specific knowledge on the problem. How to do this in such a way that the algorithms remain generally applicable ??? Examples (1): : 3 Examples (1): Imagine the problem of finding a route on a road map and that the NET below is the road map: Examples (2): 8-puzzle : 4 Examples (2): 8-puzzle f1(T) = the number correctly placed tiles on the board: Most often, ‘distance to goal’ heuristics are more useful ! Examples (3):Manhattan distance : 5 Examples (3):Manhattan distance f3(T) = the sum of ( the horizontal + vertical distance that each tile is away from its final destination): gives a better estimate of distance from the goal node = 1 + 4 + 2 + 3 = 10 Examples (4):Chess: : 6 Examples (4):Chess: F(T) = (Value count of black pieces) - (Value count of white pieces) f Hill climbing : Hill climbing A basic heuristic search method: depth-first + heuristic Hill climbing_1 : 8 Hill climbing_1 Perform depth-first, BUT: instead of left-to-right selection, FIRST select the child with the best heuristic value Example: using the straight-line distance: 8.9 10.4 10.4 6.9 6.7 3.0 Hill climbing_1 algorithm: : 9 Hill climbing_1 algorithm: 1. QUEUE <-- path only containing the root; 2. WHILE QUEUE is not empty AND goal is not reached DO remove the first path from the QUEUE; create new paths (to all children); reject the new paths with loops; sort new paths (HEURISTIC) ; add the new paths to front of QUEUE; 3. IF goal reached THEN success; ELSE failure; Beam search : Beam search Narrowing the width of the breadth-first search Beam search (1): : 11 Beam search (1): Assume a pre-fixed WIDTH (example : 2 ) Perform breadth-first, BUT: Only keep the WIDTH best new nodes depending on heuristic at each new level. Beam search (2): : 12 Beam search (2): Optimi-zation: ignore leafs that are not goal nodes (see C) Beam search algorithm: : 13 Beam search algorithm: See exercises! Properties: Completeness: Hill climbing: YES (backtracking), Beam search: NO Speed/Memory: Hill climbing: same as Depth-first (in worst case) Beam search: QUEUE always has length WIDTH, so memory usage is constant = WIDTH, time is of the order of WIDTH*m*b or WIDTH*d*b if no solution is found Hill climbing_2 : 14 Hill climbing_2 == Beam search with a width of 1. Inspiring Example: climbing a hill in the fog. Heuristic function: check the change in altitude in 4 directions: the strongest increase is the direction in which to move next. Is identical to Hill climbing_1, except for dropping the backtracking. Produces a number of classical problems: Problems with Hill climbing_2: : 15 Problems with Hill climbing_2: Comments: : 16 Comments: Foothills are local minima: hill climbing_2 can’t detect the difference. Plateaus don’t allow you to progress in any direction. Foothills and plateaus require random jumps to be combined with the hill climbing algorithm. Ridges neither: the directions you have fixed in advance all move downwards for this surface. Ridges require new rules, more directly targeted to the goal, to be introduced (new directions to move) . Local search : 17 Local search Hill climbing_2 is an example of local search. In local search, we only keep track of 1 path and use it to compute a new path in the next step. QUEUE is always of the form: ( p) Another example: MINIMAL COST search: If p is the current path: the next path extends p by adding the node with the smallest cost from the endpoint of p Greedy search : Greedy search Always expand the heuristically best nodes first. Greedy search, orHeuristic best-first search: : 19 Greedy search, orHeuristic best-first search: At each step, select the node with the best (in this case: lowest) heuristic value. Greedy search algorithm: : 20 Greedy search algorithm: 1. QUEUE <-- path only containing the root; 2. WHILE QUEUE is not empty AND goal is not reached DO remove the first path from the QUEUE; create new paths (to all children); reject the new paths with loops; add the new paths and sort the entire QUEUE; 3. IF goal reached THEN success; ELSE failure;

Related presentations


Other presentations created by ankush85

Nanotechnology
03. 04. 2009
0 views

Nanotechnology

Human Resource Management System
06. 03. 2009
0 views

Human Resource Management System

Nanotechnology
27. 03. 2009
0 views

Nanotechnology

INTRODUCTION TO NANOTECHNOLOGY
20. 11. 2009
0 views

INTRODUCTION TO NANOTECHNOLOGY

Nanotechnology in Sports
22. 11. 2009
0 views

Nanotechnology in Sports

Computer Architecture
14. 07. 2009
0 views

Computer Architecture

HR
18. 03. 2009
0 views

HR

Hospital Management System
08. 04. 2009
0 views

Hospital Management System

Welcome to Visual Basic
06. 03. 2009
0 views

Welcome to Visual Basic

HTML
20. 04. 2009
0 views

HTML

Computer Languages
03. 06. 2013
0 views

Computer Languages

Taking Care of Computer
03. 06. 2013
0 views

Taking Care of Computer

Understanding Camera
16. 10. 2012
0 views

Understanding Camera

Photography Technical Terms
25. 09. 2012
0 views

Photography Technical Terms

Basics of Photography
25. 09. 2012
0 views

Basics of Photography

AIR MUSCLES
03. 01. 2012
0 views

AIR MUSCLES

Molecular Nanotechnology
24. 11. 2009
0 views

Molecular Nanotechnology

Nanotech Innovation
22. 11. 2009
0 views

Nanotech Innovation

FINANCIAL  MARKET
16. 05. 2009
0 views

FINANCIAL MARKET

Operating System
19. 04. 2009
0 views

Operating System

Management Control
10. 07. 2009
0 views

Management Control

Accounting Principles
01. 07. 2009
0 views

Accounting Principles

Balance Sheet
21. 07. 2009
0 views

Balance Sheet

Balance Sheet Auditing
01. 07. 2009
0 views

Balance Sheet Auditing

BRANCH AND BOUND
05. 03. 2009
0 views

BRANCH AND BOUND

THE  THREE  BRANCHES  OF GOVERNMENT
13. 06. 2009
0 views

THE THREE BRANCHES OF GOVERNMENT

Structure of Atom
11. 05. 2009
0 views

Structure of Atom

Compression Techniques
05. 03. 2009
0 views

Compression Techniques

DYNAMIC PROGRAMMING
06. 03. 2009
0 views

DYNAMIC PROGRAMMING

Quantum Mechanics
25. 08. 2009
0 views

Quantum Mechanics

Marketing Plan
19. 06. 2009
0 views

Marketing Plan

Book Keeping
24. 06. 2009
0 views

Book Keeping

DFDS
02. 10. 2008
0 views

DFDS

Semiconductors
25. 04. 2009
0 views

Semiconductors

Organic  Chemistry
28. 04. 2009
0 views

Organic Chemistry

Atoms Molecules and Ions
17. 06. 2009
0 views

Atoms Molecules and Ions

Covalent Bond
25. 04. 2009
0 views

Covalent Bond

Cost Accounting Standards
25. 06. 2009
0 views

Cost Accounting Standards

Crisis Management
19. 06. 2009
0 views

Crisis Management

Marketing
18. 03. 2009
0 views

Marketing

Business Strategy
27. 04. 2009
0 views

Business Strategy

Time Management
23. 03. 2009
0 views

Time Management

Networking Protocols
23. 05. 2009
0 views

Networking Protocols

Network Layer
23. 05. 2009
0 views

Network Layer

Final Accounts
24. 06. 2009
0 views

Final Accounts

ARTIFICIAL  INTELLIGENCE
03. 04. 2009
0 views

ARTIFICIAL INTELLIGENCE

Play with C
08. 04. 2009
0 views

Play with C

Software Development Cycle
23. 03. 2009
0 views

Software Development Cycle

THE GREEDY METHOD
06. 03. 2009
0 views

THE GREEDY METHOD

JOB SEQUENCING
06. 03. 2009
0 views

JOB SEQUENCING

Electricity and Magnetism
29. 04. 2009
0 views

Electricity and Magnetism

Optical Fiber
24. 05. 2009
0 views

Optical Fiber

Quality Assurance
06. 03. 2009
0 views

Quality Assurance

Object-oriented Design
11. 04. 2009
0 views

Object-oriented Design

A.R. Rahman
08. 03. 2009
0 views

A.R. Rahman

Hollywood Female Celebrities
13. 03. 2009
0 views

Hollywood Female Celebrities

Flow nets
04. 09. 2009
0 views

Flow nets

Energy and Nanotechnology
22. 11. 2009
0 views

Energy and Nanotechnology

LOGIC  DESIGN
06. 03. 2009
0 views

LOGIC DESIGN

VB-IDE
06. 03. 2009
0 views

VB-IDE

DLF IPL FINAL
25. 05. 2009
0 views

DLF IPL FINAL

MINIMUM SPANNING TREES
06. 03. 2009
0 views

MINIMUM SPANNING TREES

CPU Scheduling
05. 03. 2009
0 views

CPU Scheduling

Virtual Memory
05. 03. 2009
0 views

Virtual Memory

POK
09. 05. 2009
0 views

POK

2D Transformations
05. 03. 2009
0 views

2D Transformations

Greedy Algorithms
05. 03. 2009
0 views

Greedy Algorithms

BACKTRACKING
05. 03. 2009
0 views

BACKTRACKING

DIVIDE And CONQUER
06. 03. 2009
0 views

DIVIDE And CONQUER

ELEMENTARY DATA STRUCTURES
06. 03. 2009
0 views

ELEMENTARY DATA STRUCTURES

JPEG Compression
06. 03. 2009
0 views

JPEG Compression

Mpeg-compression
06. 03. 2009
0 views

Mpeg-compression

NP - HARD
06. 03. 2009
0 views

NP - HARD

TRAVELLING SALESPERSON PROBLEM
06. 03. 2009
0 views

TRAVELLING SALESPERSON PROBLEM

VBA Introduction
06. 03. 2009
0 views

VBA Introduction

Introduction to Java
09. 03. 2009
0 views

Introduction to Java

Java  Basics
09. 03. 2009
0 views

Java Basics

Heuristic Search
13. 03. 2009
0 views

Heuristic Search

Tata's  Nano  Car
25. 03. 2009
0 views

Tata's Nano Car

Air Cranes
08. 04. 2009
0 views

Air Cranes

Newborn Care
10. 04. 2009
0 views

Newborn Care

Photosynthesis Process
10. 04. 2009
0 views

Photosynthesis Process

ActionScript
13. 04. 2009
0 views

ActionScript

Xml
15. 04. 2009
0 views

Xml

Snakes mis use
17. 04. 2009
0 views

Snakes mis use

Php Web Development
21. 04. 2009
0 views

Php Web Development

Cricket Intro
21. 04. 2009
0 views

Cricket Intro

Cricket Umpiring and Rules
21. 04. 2009
0 views

Cricket Umpiring and Rules

Arm and Forearm
23. 04. 2009
0 views

Arm and Forearm

Elements Ions Isotopes
25. 04. 2009
0 views

Elements Ions Isotopes

Chemical Bond
25. 04. 2009
0 views

Chemical Bond

Discovering Newtons Laws
29. 04. 2009
0 views

Discovering Newtons Laws

FreeFall
29. 04. 2009
0 views

FreeFall

Digital photography
26. 04. 2009
0 views

Digital photography

Health Effects of Alcohol
26. 04. 2009
0 views

Health Effects of Alcohol

Poetry Terminology
27. 04. 2009
0 views

Poetry Terminology

Indian Force
05. 05. 2009
0 views

Indian Force

Machine Intelligence
14. 05. 2009
0 views

Machine Intelligence

Data Link Layer
16. 05. 2009
0 views

Data Link Layer

Database Development Cycle
15. 05. 2009
0 views

Database Development Cycle

Queue
15. 05. 2009
0 views

Queue

Presentaion Skills
23. 04. 2009
0 views

Presentaion Skills

Network Layers
23. 05. 2009
0 views

Network Layers

Narmada Dam, India
23. 05. 2009
0 views

Narmada Dam, India

User Datagram Protocol
24. 05. 2009
0 views

User Datagram Protocol

Linear Momentum
28. 05. 2009
0 views

Linear Momentum

Stack and Queue
04. 06. 2009
0 views

Stack and Queue

Information Management
19. 06. 2009
0 views

Information Management

Role of Senior Management
19. 06. 2009
0 views

Role of Senior Management

Wake Up India
07. 06. 2009
0 views

Wake Up India

Adobe Flex 3.0
13. 06. 2009
0 views

Adobe Flex 3.0

Adobe Flex Presentation
13. 06. 2009
0 views

Adobe Flex Presentation

Introduction to Adobe Flex
13. 06. 2009
0 views

Introduction to Adobe Flex

Adobe Flash Media Server
13. 06. 2009
0 views

Adobe Flash Media Server

Dreamweaver
13. 06. 2009
0 views

Dreamweaver

Adobe Flash
13. 06. 2009
0 views

Adobe Flash

Flash CS4 Professional
13. 06. 2009
0 views

Flash CS4 Professional

Adobe Flash Lite
13. 06. 2009
0 views

Adobe Flash Lite

Digital Camera
13. 06. 2009
0 views

Digital Camera

Mozilla_Firefox
15. 06. 2009
0 views

Mozilla_Firefox

Managerial Accounting
27. 06. 2009
0 views

Managerial Accounting

Accounting  Information  System
01. 07. 2009
0 views

Accounting Information System

RETAILING AND MARKETING
06. 07. 2009
0 views

RETAILING AND MARKETING

ACCOUNTING IN BUSINESS
05. 07. 2009
0 views

ACCOUNTING IN BUSINESS

STRATEGIC RETAIL MANAGEMENT
05. 07. 2009
0 views

STRATEGIC RETAIL MANAGEMENT

Reiki
01. 08. 2009
0 views

Reiki

Using Buttons in PowerPoint
26. 04. 2009
0 views

Using Buttons in PowerPoint

Nanotechnology  for  Students
21. 08. 2009
0 views

Nanotechnology for Students

NANOSCIENCE
25. 08. 2009
0 views

NANOSCIENCE

Fundamentals of Nanoscience
27. 08. 2009
0 views

Fundamentals of Nanoscience

Nanoscience in Nature
27. 08. 2009
0 views

Nanoscience in Nature

Applied Mechanics
04. 09. 2009
0 views

Applied Mechanics

Accounts Payable Training
27. 06. 2009
0 views

Accounts Payable Training