Explain the term Decision problem with the help of an example. Define the following problems and identify if they are decision problem or optimisation problem? Give reasons in support of your answer.
(i) Travelling Salesman Problem
(ii) Graph Colouring Problem
(iii) 0-1 Knapsack Problem
A decision problem is a problem where the answer is either "yes" or "no." It asks whether a specific condition or set of conditions holds for a given problem instance. In the context of algorithms, decision problems often involve checking whether a solution exists that satisfies certain criteria.
Example of a Decision Problem:
Consider the problem of determining whether there exists a subset of a given set of integers such that their sum is exactly equal to a given number. This is a decision problem because the answer is either "yes" (such a subset exists) or "no" (such a subset does not exist).
Now, let's define the following problems and identify whether they are decision problems or optimization problems:
(i) Travelling Salesman Problem (TSP):
-
Definition: The Traveling Salesman Problem asks for the shortest possible route that visits a given set of cities and returns to the starting point, such that each city is visited exactly once.
-
Type of Problem: Optimization Problem. The objective
_____ ______ ________ _____ ______ _______ __________.
_______ ________ _______ ______ _____ _________ ____ _____ ______ _________ _______.
___ __________ __________ ____ _______ _______ ___ ____ ________ __________.
_______ _________ ______ __________ _____ _______ _______ ____ _______ _______ _______.
_________ ______ ________ _______ __________ ____ ____ __________ _______.
______ ______ ______ ______ ______ _________ _________.
_____ _______ ____ _______ ___ _____.
____ __________ _________ ____ _______ ___ ______ _____ ____ ___.
__________ _________ ___ ___ ____ ____ __________ _________.
____ ____ _____ _________ ________ _____ ___.
__________ ________ _____ ______ ___ __________ ___ _______ ___.
___ _______ ______ _________ ____ _________ ___ _______ ______ ________.
________ ____ ________ ______ _________ _______ _________ __________ ___ ______ _________.
_________ _________ ___ __________ ____ __________ _____ __________ ___ ___ _________ _____.
___ _________ _______ ________ _________ ___ _________ ______ ____.
___ _____ ____ ______ _____.
______ ____ _________ _____ _________ ______ ___ ________ _______ ____ __________ _____.
________ _________ _____ _________ _______ ________ _________.
____ _______ ______ ____ ____ _________ ______ _______ _____ __________ __________ _______.
______ _______ _____ ___ ____ _______.
__________ ______ __________ _______ ___.
_________ __________ ______ __________ ______ _______ _________ _______ _______ ________ _____.
____ ______ ______ ________ ______ __________ ____.
_______ _____ _______ ________ __________ _________ _________ ___ ____ ___ _______ __________.
__________ ____ ____ _________ ___ _________.
____ _____ ______ ________ __________ ____ ________ ____.
____ ___ ____ ____ ______ ______.
______ ___ __________ ____ ______ __________ _________ ________ ___ _________.
____ ______ _______ ___ ____.
_______ _________ ____ ______ ______.
_____ __________ ______ ____ ___ __________ ______.
_________ _______ _______ _____ _____ ____ ________ ___ ______ _______ _________ ____.
_________ ____ _______ ______ ____ ______.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
✓ Unlock up to 60% of the answer
✓ No payment required