Steepest Hill climbing/Best first search/A* Algorithm

-
Steepest Hill climbing differs from simple hill climbing by choosing the Best Successor rather than the first one.This indicates that it has elements of breadth first  search algorithm

The Algorithm in a simplified manner is here 

1.Evaluate the initial State.
2.If it is goal state than Quit otherwise make Initial state as the current state and proceed.
3 Repeat  
   set target to be the State that any Successor of the Current state can be better.
4.For (in a loop)  Each operator that can be applied in the Current State Apply new operator to new       state.if it is a goal state than Quit otherwise Compare with the Target state if better than set Current state to target state.

Best First Search   
We had BFS and DFS in DFS solution can be found without Computing the nodes and in BFS is good because it does not get trapped in dead ends.

But for Best first search it takes the benefit of both the steps (DFS and BFS) takes the most step to be chosen . For example if one of the nodes chosen generates nodes that are less promising it is possible to choose the same level other node (So same level is the word means we can assume it to be BFS)So it means it has switched form DFS to BFS.

A* Algorithm
A* algorithm combines the features of uniform cost search and + pure heuristic to efficiently compute the optimal search.A* is the best First search algorithm in which cost  associated with the Node is f(n)=g(n)+h(n).

where g(n)⟶ cost from initial node to node n.
where h(n)⟶heuristic estimate or cost or path from node n to goal.

f(n) estimates the lowest solution path going through node n .At each node choose the lowest f to expand.And if modes have the same f value than choose the least h value that is the heuristic cost estimated to reach the goal.The algorithm terminates when the goal is chosen for expansion.
  

Comments

Post a Comment

Popular posts from this blog

State space search / blocks world problem by heuristic approach /TIC TAC TOE

-
A lot of AI is about SEARCH. The "state space" is the set of states of the problem we can get to by applying operators to a state of the problem to get a new state. A  state  contains  all of the information necessary to predict the effects of an action and to determine if it is a goal state. State-space searching assumes that the agent has perfect knowledge of the state space and can observe what state it is in (i.e., there is full observability); the agent has a set of actions that have known deterministic effects;some states are goal states, the agent wants to reach one of these goal states, and the agent can recognize a goal state. a solution is a sequence of actions that will get the agent from its current state to a goal state. Define the Problem as State Space Search Consider the problem of “Playing Chess” . to build a program that could play chess, we have to specify the starting position of the chess board, the rules that define legal moves. And the
Read more

Navigation in Vaadin.

-
Plain Vaadin applications do not have normal web page navigation as they usually run on a single page, as all Ajax applications do. Quite commonly, however, applications have different views between which the user should be able to navigate. The  Navigator  in Vaadin can be used for most cases of navigation. Views managed by the navigator automatically get a distinct URI fragment, which can be used to be able to bookmark the views and their states and to go back and forward in the browser history. The  Navigator  class manages a collection of  views  that implement the  View  interface. SO the class in which you are defining Navigation must implement with a  View  interface. addView() i s the method by which you can register Your View . You can add your view at any point ,Your View must have   name identifier and be added to a  View . Once registered, you can navigate to them with  navigateTo() . Navigator  manages navigation in a component container, which can be
Read more

Drag and drop items from one Grid to another

-
Following is a short example to drag and drop similar type of items from one Grid to another Grid in Vaadin 8 . package com . example . demo ; import java . util . ArrayList ; import java . util . List ; import java . util . Optional ; import com . vaadin . data . provider . ListDataProvider ; import com . vaadin . shared . ui . dnd . DropEffect ; import com . vaadin . shared . ui . dnd . EffectAllowed ; import com . vaadin . shared . ui . grid . DropMode ; import com . vaadin . ui . CustomComponent ; import com . vaadin . ui . Grid ; import com . vaadin . ui . HorizontalLayout ; import com . vaadin . ui . components . grid . GridDragSource ; import com . vaadin . ui . components . grid . GridDropTarget ; import com . vaadin . ui . renderers . ButtonRenderer ; public class DragAndDropFromGrid extends CustomComponent { /**       *      */ private static final long serialVersionUID = 1 L ; private HorizontalLayout hlytbase ;
Read more