Help Pa unlock nito boss Chegg

[SomeDay09]

You do not have permission to view the full content of this post. Log in or register now.


Sa may chegg jan Pa unlock po nito plzzzz.

 

[meteorchild]

here

 

[SomeDay09]

Thank you boss

 

[Let Leni Lead]

Boss paunlock rin po sana You do not have permission to view the full content of this post. Log in or register now.

 

[-gekyume-]

You do not have permission to view the full content of this post. Log in or register now.
Paunlock din boss

 

[xRapidoo]

[XX='Joshuacarl, c: 881653, m: 1025706'][/XX]
Random Search

• Step 1: Current node x=initial node;

• Step 2: If x=target node, stop with success;

• Step 3: Expand x, and get a set S of child nodes;

• Step 4: Select a node x’ from S at random;

• Step 5: x=x’, and return to Step 2.

Random search is not good

• At each step, the next node is determined at random.

• We cannot guarantee to reach the target node.

• Even if we can, the path so obtained can be very redundant (extremely long).

Search with a closed list

• Step 1: Current node x=initial node;

• Step 2: If x=target node, stop with success;

• Step 3: Expand x, and get a set S of child nodes. If S is empty, stop with failure. Add x to the closed list.

• Step 4: Select from S a new node x’ that is not in the closed list.

• Step 5: x=x’, and return to Step 2.

Closed list is not enough!

• Using a closed list, we can guarantee termination of search in finite steps

. • However, we may never reach the target node! Produced by Qiangfu Zhao (Since 2008),

Search with open list

• Step 1: Add the initial node to the open list.

• Step 2: Take a node x from the open list from the top. If the open list is empty, stop with failure; on the other hand, if x is the target node, stop with success.

• Step 3: Expand x to obtain a set S of child nodes, and put x into the closed list.

• Step 4: For each node x’ in S, if it is not in the closed list, add it to the open list along with the edge (x, x’).

• Step 5: Return to Step 2. Produced by Qiangfu Zhao (Since 2008), All rights reserved © AI Lec03/10 Keep all “un-visited” nodes in another list! See Algorithm 1 in the textbook

Property of Algorithm 1

• It is known that search based on the open list is complete in the sense that we can always find the solution in a finite number of steps if the search graph is finite.

• The edge (x, x’) is kept in the search process for “restoring” the search path via “back-tracking”.

Depth-first search and breadth-first search

• Algorithm I is a depth-first search if we implement the open list using a stack.

• Algorithm I becomes the breadth-first search if the open list is implemented using a queue.

• It is known the breadth-first search is better because even for an infinite search graph, we can get the solution in finite steps, if the solution exists.

Uniform-cost search:

The Dijkstra's algorithm

• Usually, the solution is not unique. It is expected to find the BEST one.

• For example, if we want to travel around the world, we may try to find the fastest route; the most economic route; or the route in which we can visit more friends.

• The uniform-cost search or Dijkstra’s algorithm is a method for solving this problem.

Uniform-cost search

• Step 1: Add the initial node x0 and its cost C(x0)=0 to the open list.

• Step 2: Get a node x from the top of the open list. If the open list is empty, stop with failure. If x is the target node, stop with success.

• Step 3: Expand x to get a set S of child nodes, and move x to the closed list.

• Step 4: For each x’ in S but not in the closed list, find its accumulated cost C(x’)=C(x)+d(x,x’); and add x’, C(x’), and (x, x’) to the open list. If x’ is already in the open list, update its cost and link if the new cost is smaller.

• Step 5: Sort the open list based on the node costs, and return to Step 2. Produced by Qiangfu Zhao (Since 200

Uniform-cost search

• During uniform-cost search, we can always find the best path from the initial node to the current node. That is, when search stops with success, the solution must be the best one.

• In the algorithm, c(x) is the cost of the node x accumulated from the initial node; and d(x,x’) is the cost for state transition (e.g. the distance between to adjacent cities).

• If we set d(x,x’)=1 for all edges, uniform-cost search is equivalent to the breadth-first search.

 

[Jechu123]

You do not have permission to view the full content of this post. Log in or register now.

Patulong boss

 

[kenkenxd11]

boss paunlock pls imsakristan
You do not have permission to view the full content of this post. Log in or register now.

 

[igopako456]

You do not have permission to view the full content of this post. Log in or register now.

Patulong din po huhu