Computer Science: An Overview (12th Edition)
12th Edition
ISBN: 9780133760064
Author: Glenn Brookshear, Dennis Brylow
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Concept explainers
Question
Chapter 11, Problem 29CRP
Program Plan Intro
Heuristic search:
- It denotes a technique to reach goal state by choosing best promising state.
- It leads to goal state and this search is identified as heuristic search.
- The heuristic values are chosen for each node.
- It denotes that node that has low heuristic value is been chosen over another nodes.
Goal:
- The objective is to find state sequence that would lead to final state.
- The numbers are been ordered from initial state that is unordered and it follows the productions.
- The count of tiles that are out of place denotes heuristic in problem.
- The algorithm is shown below:
- Step 1:
- Construct parent node by taking initial node
- Step 2:
- Check whether the node signifies a final state.
- Step 3:
- If step 2 fails, make child nodes that are possible states and could be attain by moving empty tile in parent nodes.
- Find heuristic value of states.
- Select node that has low heuristic value and move to step 2.
- Step 4:
- If step 2 is true, then algorithm constructed search tree.
- Stop construction of tree further.
- Step 1:
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solutionStudents have asked these similar questions
Minimum Spanning Trees (MST): Finding a Minimum Spanning Tree for the following graph based on each of the following algorithm. You need to show the procedures step-by-step. You could directly draw the final MST but indicate the sequence of your search by writing a series of letters, i.e. (a), (b), (c)… under the edges of the MST. This type of answer is preferred. Or else, you need to draw a graph for each step separately.
Kruskal’s algorithm.
Prim’s algorithm (start with the node ‘ORD).
The Graph Data Structure is made up of nodes and edges. (A Tree Data Structure is a special kind of a
Graph Data Structure). A Graph may be represented by an Adjacency Matrix or an Adjacency List. Through
this exercise, you should be able to have a better grasp the Adjacency Matrix concept. You are expected to
read about the Adjacency Matrix concept as well as the Adjacency List concept.
Suppose the vertices A, B, C, D, E, F, G and H of a Graph are mapped to row and column
indices(0,1,2,3,4,5,6,and 7) of a matrix (i.e. 2-dimensional array) as shown in the following table.
Vertex of Graph
Index in the 2-D Array Adjacency Matrix
Representation of Graph
A
B
2
F
6.
H
7
Suppose further, that the following is an Adjacency Matrix representing the Graph.
3
4
5.
6.
7
0.
1
1
1
1
01
1
01
1.
3
14
1
1
1
6.
1
Exercise:
Show/Draw the Graph that is represented by the above Adjacency matrix. Upload the document that contains
your result. (Filename: AdjacencyMatrixExercise.pdf)
Notes:
-The nodes of the…
Draw a tree with 14 vertices
Draw a directed acyclic graph with 6 vertices and 14
edges
Suppose that your computer only has enough memory
to store 40000 entries. Which best graph data
structure(s) – you can choose more than 1 -- should
you use to store a simple undirected graph with 200
vertices, 19900 edges, and the existence of edge(u,v)
is frequently asked?
- Adjacency Matrix
- Adjacency List
- Edge List
Chapter 11 Solutions
Computer Science: An Overview (12th Edition)
Ch. 11.1 - Prob. 1QECh. 11.1 - Prob. 2QECh. 11.1 - Prob. 3QECh. 11.1 - Prob. 4QECh. 11.1 - Prob. 5QECh. 11.2 - Prob. 1QECh. 11.2 - Prob. 2QECh. 11.2 - Prob. 3QECh. 11.2 - Prob. 4QECh. 11.2 - Identify the ambiguities involved in translating...
Ch. 11.2 - Prob. 6QECh. 11.2 - Prob. 7QECh. 11.3 - Prob. 1QECh. 11.3 - Prob. 2QECh. 11.3 - Prob. 3QECh. 11.3 - Prob. 4QECh. 11.3 - Prob. 5QECh. 11.3 - Prob. 6QECh. 11.3 - Prob. 7QECh. 11.3 - Prob. 8QECh. 11.3 - Prob. 9QECh. 11.4 - Prob. 1QECh. 11.4 - Prob. 2QECh. 11.4 - Prob. 3QECh. 11.4 - Prob. 4QECh. 11.4 - Prob. 5QECh. 11.5 - Prob. 1QECh. 11.5 - Prob. 2QECh. 11.5 - Prob. 3QECh. 11.5 - Prob. 4QECh. 11.6 - Prob. 1QECh. 11.6 - Prob. 2QECh. 11.6 - Prob. 3QECh. 11.7 - Prob. 1QECh. 11.7 - Prob. 2QECh. 11.7 - Prob. 3QECh. 11 - Prob. 1CRPCh. 11 - Prob. 2CRPCh. 11 - Identify each of the following responses as being...Ch. 11 - Prob. 4CRPCh. 11 - Prob. 5CRPCh. 11 - Prob. 6CRPCh. 11 - Which of the following activities do you expect to...Ch. 11 - Prob. 8CRPCh. 11 - Prob. 9CRPCh. 11 - Prob. 10CRPCh. 11 - Prob. 11CRPCh. 11 - Prob. 12CRPCh. 11 - Prob. 13CRPCh. 11 - Prob. 14CRPCh. 11 - Prob. 15CRPCh. 11 - Prob. 16CRPCh. 11 - Prob. 17CRPCh. 11 - Prob. 18CRPCh. 11 - Give an example in which the closed-world...Ch. 11 - Prob. 20CRPCh. 11 - Prob. 21CRPCh. 11 - Prob. 22CRPCh. 11 - Prob. 23CRPCh. 11 - Prob. 24CRPCh. 11 - Prob. 25CRPCh. 11 - Prob. 26CRPCh. 11 - Prob. 27CRPCh. 11 - Prob. 28CRPCh. 11 - Prob. 29CRPCh. 11 - Prob. 30CRPCh. 11 - Prob. 31CRPCh. 11 - Prob. 32CRPCh. 11 - Prob. 33CRPCh. 11 - What heuristic do you use when searching for a...Ch. 11 - Prob. 35CRPCh. 11 - Prob. 36CRPCh. 11 - Prob. 37CRPCh. 11 - Prob. 38CRPCh. 11 - Suppose your job is to supervise the loading of...Ch. 11 - Prob. 40CRPCh. 11 - Prob. 41CRPCh. 11 - Prob. 42CRPCh. 11 - Prob. 43CRPCh. 11 - Prob. 44CRPCh. 11 - Prob. 45CRPCh. 11 - Prob. 46CRPCh. 11 - Prob. 47CRPCh. 11 - Prob. 48CRPCh. 11 - Draw a diagram similar to Figure 11.5 representing...Ch. 11 - Prob. 50CRPCh. 11 - Prob. 51CRPCh. 11 - Prob. 52CRPCh. 11 - Prob. 53CRPCh. 11 - Prob. 54CRPCh. 11 - Prob. 55CRPCh. 11 - Prob. 56CRPCh. 11 - Prob. 57CRPCh. 11 - Prob. 1SICh. 11 - Prob. 2SICh. 11 - Prob. 3SICh. 11 - Prob. 4SICh. 11 - Prob. 5SICh. 11 - Prob. 6SICh. 11 - Prob. 7SICh. 11 - Prob. 8SICh. 11 - Prob. 9SICh. 11 - Prob. 10SICh. 11 - Prob. 11SICh. 11 - Prob. 12SICh. 11 - A GPS in an automobile provides a friendly voice...Ch. 11 - Prob. 14SI
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
- Correct answer will be upvoted else Multiple Downvoted. Computer science. Alice and Bob are playing a game. They have a tree comprising of n vertices. At first, Bob has k chips, the I-th chip is situated in the vertex computer based intelligence (every one of these vertices are extraordinary). Prior to the game beginnings, Alice will put a chip into one of the vertices of the tree. The game comprises of turns. Each turn, the accompanying occasions occur (consecutively, precisely in the accompanying request): Alice either moves her chip to a neighboring vertex or doesn't move it; for each Bob's chip, he either moves it to a neighboring vertex or doesn't move it. Note that this decision is done freely for each chip. The game closures when Alice's chip has a similar vertex with one (or numerous) of Bob's chips. Note that Bob's chips might have a similar vertex, despite the fact that they are in various vertices toward the start of the game. Alice needs to augment the number…arrow_forward3. Kleinberg, Jon. Algorithm Design (p. 519, q. 28) Consider this version of the Independent Set Problem. You are given an undirected graph G and an integer k. We will call a set of nodes I "strongly independent" if, for any two nodes v, u € I, the edge (v, u) is not present in G, and neither is there a path of two edges from u to v. That is, there is no node w such that both (v, w) and (u, w) are present. The Strongly Independent Set problem is to decide whether G has a strongly independent set of size at least k. Show that the Strongly Independent Set Problem is NP-Complete.arrow_forwardGiven a graph that is a tree (connected and acyclic). (I) Pick any vertex v.(II) Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance.(III) Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. Consider the path p from w to x. Which of the following are truea. p is the longest path in the graphb. p is the shortest path in the graphc. p can be calculated in time linear in the number of edges/verticesarrow_forward
- algorithm GenericSearch (G, s) pre-cond: G is a (directed or undirected) graph, and s is one of its nodes. post-cond: The output consists of all the nodes u that are reachable by a path in G from s.arrow_forwardQ7: Run the Ford-Fulkerson algorithm on the graph assigned to you and determine the maximum flow possible between the source (s) and destination (d) as well as determine the minimum cut of edges (set of edges with the minimum sum of the edge weights) to disconnect the source and destination. Show all the work (including the use of the residual graphs in each iteration).arrow_forwardThe graph is another structure that can be used to solve the maze problem. Every start point, dead end, goal, and decision point can be represented by node. The arcsbetween the nodes represent one possible path through the maze. A graph maze is shown in Figure Q4.1. Start A D H K Goal Figure Q4.1: Graph Maze Describe the graph as in Figure Q4.1, using the formal graph notation of V i. and E.V: set of vertices E: set of edges connecting the vertices in Varrow_forward
- BFS Now, implement the Breadth First Search (BFS) algorithm to traverse the graph—returning a lis of nodes it visited in order. Inputs: ?:?:the graph representationthe start nodearrow_forwardB1- Perform A* search on the following state space graph, starting at A and reaching G. Draw the search tree with the values of each node. What is the path to goal?arrow_forwardY3arrow_forward
- A. Use Prim’s algorithm starting at node A to compute the Minimum Spanning Tree (MST) of the following graph. In particular, write down the edges of the MST in the order in which Prim’s algorithm adds them to the MST. Use the format (node1; node2) to denote an edge B. For the same graph as above, write down the edges of the MST in the order in which Kruskal’s algorithm adds them to the MST. NB: Graph in imagearrow_forwardWrite algorithm LargestShortestWeight(G, s,t) pre-cond: G is a weighted directed (augmenting) graph. s is the sourcenode.t is the sink. post-cond: P specifies a path from s to t whose smallest edge weight is aslarge as possible. u, v is its smallest weighted edge.arrow_forwardAssume you are to write a program to analyze the social connection between students in MTSU. Each student is a node in a undirected graph. An edge is added between two nodes if these two students have close social connections, i.e., in the same club, or in the same department. Which would be a better representation for this graph? Question 45 options: adjacency matrix representation adjacency list representationarrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education