Answered step by step
Verified Expert Solution
Question
1 Approved Answer
The Best Independent Set problem is defined as follows: Input: An undirected graph G, in which each vertex is marked by a positive value ;
The "Best Independent Set" problem is defined as follows: Input: An undirected graph G, in which each vertex is marked by a positive value ; and a target value T. Goal: A set of vertices S such that (a) no two vertices in S are connected by an edge in G; and (b) the total value of the vertices in S is at least T. For instance, in Graph 1 below, with T=16, there are three solutions: { C,D },{ A,E }, and {B,E} In Graph 2, with T=21 the only solution is {G,H,K} The N-Queens problem is actually a special case of this, with the vertices being the squares on the chess board, an edge between two vertices if the squares attack, all vertices have value 1 , and the target value is N. Problem 1 Consider the following state space for systematically solving the problem: State: A set of vertices, no two of which are connected by an edge. Successor to state S : Add some vertex V to S such that (a) V is alphabetically later than the vertices in S (to guarantee systematic search); (b) V is not connected to any vertex in S. Start state: The empty set. Goal state: A state that attains the target value. Show the part of the state space that would be generated if you use depth-first search in this state space to find the solution to graph 2 with T=21. You should show this as a tree. I recommend drawing trees for assignments left-to-right typewriter format like this: If you want to use graphics software to make a nice looking tree, that's even better, though more work for you. If you want to draw it out and photograph it, that's OK, though less preferred
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started