TSP Using Branch and Bound

Duration: 1 hr 13 min

This video lesson is available to enrolled students.

Return to /learn/NTA-UGC-NET-PAPER-2/unit-7-data-structures-and-algorithms/advanced-algorithms/branch-and-bound/asset-tsp-using-branch-and-bound after enrolling

Inside: a video lesson and guided study material.

Module outline

  1. Course Overview: About the Course
  2. Paper - 1 | Unit - 1 | Teaching Aptitude: Concept and Objectives of Teaching / शिक्षण की अवधारणा एवं उद्देश्य, Levels of Teaching / शिक्षण के स्तर, Learner's Characteristics / शिक्षार्थी की विशेषताएँ, Learning: Nature and Theories / अधिगम: प्रकृति एवं सिद्धांत, Cognition, Memory and Metacognition / संज्ञान, स्मृति एवं अधिसंज्ञान, Factors Affecting Teaching / शिक्षण को प्रभावित करने वाले कारक, Effective Teaching and the Teacher / प्रभावी शिक्षण एवं शिक्षक, Instructional Objectives and Lesson Planning / अनुदेशनात्मक उद्देश्य एवं पाठ नियोजन, Methods of Teaching / शिक्षण विधियाँ, Offline and Online Teaching Methods / ऑफ़लाइन एवं ऑनलाइन शिक्षण विधियाँ, Teaching Support System / शिक्षण सहायक प्रणाली, Evaluation Systems / मूल्यांकन प्रणाली, Sāṃkhya / सांख्य, Individual Behaviour / व्यक्तिगत व्यवहार, Human Resource Management / मानव संसाधन प्रबंधन, Domains of Child Development / बाल्यावस्था में विकास के क्षेत्र, Biological Basis of Emotion / संवेग का जैविक आधार, Upanishads and Bhagavad Gita / उपनिषद और भगवद्गीता, Central and Peripheral Nervous Systems / केन्द्रीय और परिधीय तंत्रिका तंत्र
  3. Paper - 1 | Unit - 2 | Research Aptitude: Research: Meaning, Features and Scientific Method / अनुसंधान: अर्थ, लक्षण व वैज्ञानिक विधि, Research Paradigms and Approaches / अनुसंधान के प्रतिमान एवं उपागम, Types of Research / अनुसंधान के प्रकार, Variables and Measurement / चर एवं मापन, Methods of Research / अनुसंधान की विधियाँ, Steps of Research / अनुसंधान के चरण, Sampling / प्रतिचयन, Tools and Methods of Data Collection / आँकड़ा संग्रह के उपकरण एवं विधियाँ, Data Analysis and Statistics in Research / आँकड़ा विश्लेषण एवं शोध सांख्यिकी, Thesis and Article Writing / शोध-प्रबंध एवं लेख लेखन, Application of ICT in Research / अनुसंधान में ICT का अनुप्रयोग, Research Ethics / शोध नैतिकता
  4. Paper - 1 | Unit - 3 | Comprehension: Literal Comprehension, Vocabulary and Language in Context, Inferential Comprehension, Critical Comprehension, Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions), Restoration and Eighteenth-Century Drama, Modern British Fiction, William Shakespeare, Mid-Twentieth-Century and Contemporary British Fiction, American Drama
  5. Paper - 1 | Unit - 4 | Communication: Communication: Meaning, Nature and Process / संचार: अर्थ, प्रकृति एवं प्रक्रिया, Types and Levels of Communication / संचार के प्रकार एवं स्तर, Verbal and Non-verbal Communication / मौखिक एवं अमौखिक संचार, Semiotics and Meaning / संकेत विज्ञान एवं अर्थ, Models and Theories of Communication / संचार के मॉडल एवं सिद्धांत, Effective Communication / प्रभावी संचार, Barriers to Communication / संचार की बाधाएँ, Classroom Communication / कक्षा संचार, Mass Media: Types and Evolution / जनसंचार माध्यम: प्रकार एवं विकास, Mass Media and Society / जनसंचार एवं समाज, Digital and New Media / डिजिटल एवं नव माध्यम, Static General Knowledge / स्थैतिक सामान्य ज्ञान, Morphology and Syntax, Public Health Nutrition / जन स्वास्थ्य पोषण, Newtonian Motion and Stability, GK- Current Affairs / GK- समसामयिकी, Indian Economy / भारतीय अर्थव्यवस्था, Art and Architecture / कला और स्थापत्य, India after Independence / स्वतंत्रता के बाद भारत
  6. Paper - 1 | Unit - 5 | Mathematical Reasoning and Aptitude: Number System and Simplification / संख्या पद्धति एवं सरलीकरण, Algebra and Ages / बीजगणित एवं आयु, Percentage / प्रतिशतता, Ratio, Proportion, Partnership and Mixtures / अनुपात, समानुपात, साझेदारी एवं मिश्रण, Averages / औसत, Profit, Loss and Discount / लाभ, हानि एवं बट्टा, Simple and Compound Interest / साधारण एवं चक्रवृद्धि ब्याज, Time and Work / समय एवं कार्य, Speed, Time and Distance / चाल, समय एवं दूरी, Mensuration and Geometry / क्षेत्रमिति एवं ज्यामिति, Series / श्रेणी, Coding-Decoding / कूटलेखन-कूटवाचन, Relationships, Directions and Ranking / संबंध, दिशा एवं क्रम, Arrangements, Puzzles, Clock and Calendar / व्यवस्था, पहेलियाँ, घड़ी एवं कैलेंडर, Mathematical Foundations, Polity / राजव्यवस्था, जीवनी, Deconstruction, Gender and Queer Theory, Modern British and Irish Poetry, Central Force and Scattering, Chemical thermodynamics, Microscopic techniques, Philosophy of the Constitution / संविधान का दर्शन, Waves, Optics and Charged-Particle Motion, Membrane structure and function, Analysis
  7. Paper - 1 | Unit - 6 | Logical Reasoning: Structure of Arguments / युक्ति की संरचना, Terms, Definitions and Uses of Language / पद, परिभाषा एवं भाषा के उपयोग, Categorical Propositions / निरुपाधिक प्रतिज्ञप्तियाँ, Categorical Syllogism / निरुपाधिक न्यायवाक्य, Venn Diagrams / वेन आरेख, Deduction, Induction and Analogy / निगमन, आगमन एवं सादृश्यता, Fallacies / तर्कदोष, Indian Logic: Pramanas / भारतीय तर्कशास्त्र: प्रमाण, Anumana and Vyapti / अनुमान एवं व्याप्ति, Hetvabhasa / हेत्वाभास, Non Verbal Reasoning (Spatial Aptitude) (Spatial Reasoning) (Visual Reasoning), Aristotle / अरस्तू, Western Schools of Philosophy / पाश्चात्य दर्शन की विचारधाराएँ, Kant / कांट, Sadhana Paada, Vaiśeṣika / वैशेषिक
  8. Paper - 1 | Unit - 7 | Data Interpretation: Data and Graphical Representation / आँकड़े एवं आलेखीय निरूपण, Data Interpretation: Tables / आँकड़ा निर्वचन: तालिका
  9. Paper - 1 | Unit - 8 | Information and Communication Technology: Computer Fundamentals and Hardware, Memory, Storage and Data Representation, Computer Software, Office Applications, Multimedia and File Formats, Computer Networks, Internet and World Wide Web, Email and Online Communication, Cyber Security, Digital Ethics, IPR and Society, Cloud and Distributed Computing, Emerging Technologies, ICT in Education and Governance, Cyber Threats and Malware Attacks, Role of Internet and Web Services, Electronic Data Interchange and E-Commerce, Internet Fundamentals, Web Design & Development, Web Publishing & Hosting, Emerging Technologies, Terms & Abbreviations, Society, Law & Ethics, Keyboard Shortcuts, Website, Browser & Services, Protection of Geographical Indications / भौगोलिक संकेतों का संरक्षण
  10. Paper - 1 | Unit - 9 | People Development and Environment: Ecosystems and Biodiversity / पारितंत्र और जैव विविधता, Human and Environment Interaction / मानव और पर्यावरण की अंतःक्रिया, Development and Environment / विकास और पर्यावरण, Natural Resources – Forests, Water and Soil / प्राकृतिक संसाधन: वन, जल और मृदा, Energy Resources / ऊर्जा संसाधन, Air Pollution / वायु प्रदूषण, Water Pollution and Treatment / जल प्रदूषण और उपचार, Noise Pollution / ध्वनि प्रदूषण, Waste Management / अपशिष्ट प्रबंधन, Environmental Health and Toxicology / पर्यावरणीय स्वास्थ्य और विषविज्ञान, Climate Change and Global Environmental Issues / जलवायु परिवर्तन और वैश्विक पर्यावरणीय समस्याएँ, Natural Hazards and Disaster Management / प्राकृतिक प्रकोप और आपदा प्रबंधन, Indian Environmental Laws and Policies / भारतीय पर्यावरण कानून और नीतियाँ, International Environmental Agreements / अंतर्राष्ट्रीय पर्यावरण समझौते, Environment / पर्यावरण, Geography / भूगोल, Factory and Industry Systems / कारखाना और उद्योग व्यवस्थाएँ, Earth Materials, Surface Features and Processes, Communicable Diseases and Immunization / संक्रामक रोग और प्रतिरक्षण
  11. Paper - 1 | Unit - 10 | Higher Education System: Education in Ancient India / प्राचीन भारत में शिक्षा, Ancient Centres of Higher Learning / प्राचीन भारत के उच्च शिक्षा केंद्र, Colonial Education Policies and Commissions / औपनिवेशिक काल की शिक्षा नीतियाँ और आयोग, Colonial Colleges, Universities and Reformers / औपनिवेशिक कॉलेज, विश्वविद्यालय व सुधारक, Education Commissions and Policies after Independence / स्वतंत्र भारत में शिक्षा आयोग और नीतियाँ, National Education Policy 2020 / राष्ट्रीय शिक्षा नीति 2020, Types of Higher Education Institutions / उच्च शिक्षा संस्थानों के प्रकार, Learning Programmes and Academic Credits / अधिगम कार्यक्रम और अकादमिक क्रेडिट, Professional, Technical and Skill-Based Education / व्यावसायिक, तकनीकी और कौशल आधारित शिक्षा, Value Education and Environmental Education / मूल्य शिक्षा और पर्यावरण शिक्षा, Governance, Administration and Financing / शासन, प्रशासन और वित्तपोषण, Regulation, Accreditation and Ranking / उच्च शिक्षा का नियमन, प्रत्यायन और रैंकिंग
  12. Paper 2 | Unit 1 | Discrete Structures and Optimization: Propositional and Predicate Logic, Set Theory, Relations, Functions, Permutation, Combination and Probability / क्रमचय, संचय एवं प्रायिकता, Graph Theory, Group Theory, Digital Systems & Boolean Basics, Boolean Expression, Boolean Minimization, Optimization, Markov Chains
  13. Paper 2 | Unit 2 | Computer System Architecture: Logic Gates & Hardware, Combinational Circuit, Sequential Circuits, Number System, Number Representation, Floating Point Rep, Basics of COA, Register Transfer and Microoperations, Programming the Basic Computer, Instr Formats & Modes, Control Unit Design, Pipelining, Input Output Organisation, Cache Memory Organization, Multiprocessors
  14. Paper 2 | Unit 3 | Programming Languages and Computer Graphics: Language Design, C Fundamentals, Control Flow, Functions, Arrays & Pointers, Storage Classes, Structures & Enums, DMA, Macros, Scoping & File Handling, HTML Basics, XML, JavaScript-Basics, Java, Basics of Computer Graphics, 2-D Geometrical Transforms and Viewing, 3-D Object Representation, Geometric Transformations and Viewing, OOPS with C++, Java Fundamentals, Array, String, IO & References, OOPS with Java
  15. Paper 2 | Unit 4 | Database Management Systems: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, File Organization & Indexing, Relational Algebra, SQL, Relational Calculus, Transaction Management, Concurrency Control, Database Recovery, ORDBMS, Database Security & Authorization, Query Processing & Optimization, Enhanced Data Models, Data Warehousing & Mining, Big Data Systems, NoSQL
  16. Paper 2 | Unit 5 | System Software and Operating System: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Threads & Process Creation, Deadlock, Memory Management, Virtual Memory, Disc Scheduling, File Management, Windows OS, Linux OS, Security, Distributed Systems, Virtual Machines
  17. Paper 2 | Unit 6 | Software Engineering: Fundamentals of Software Engineering, Software Requirements and Quality Assurance, Software Design, Estimation and Metrics, Software Testing, Software Maintenance and Configuration Management
  18. Paper 2 | Unit 7 | Data Structures and Algorithms: Introduction to DS, Array, Stack, Queue, Linked List, Tree, Graphs, Hashing, Algorithm Analysis, Time Complexity Analysis, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Minimum Spanning Trees, Shortest Path Algos, Advanced Algorithms
  19. Paper 2 | Unit 8 | Theory of Computation and Compilers: Introduction to TOC, Deterministic FA (DFA), Non-Deterministic FA, Regular Expressions, Grammar, Regular Language Properties, Moore & Mealy Machines, Pushdown Automata & CFG, Turing Machines, Complexity Theory, Intro to Compilers, Lexical Analysis, Grammar & CFG, Syntax Analysis: Top-Down, Syntax Analysis: Bottom-Up, Semantic Analysis & SDT, Intermediate Code Gen, Code Optimization, Run Time Environment
  20. Paper 2 | Unit 9 | Data Communication and Computer Networks: Introduction to CN, Data Communication, DLL: Access Control, DLL: Flow Control, DLL: Error Control, DLL: Framing, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Net Layer:Routing Protocol, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware basics, Network Security, Cloud Computing, Mobile Computing
  21. Paper 2 | Unit 10 | Artificial Intelligence: Approaches to AI, Search Algorithms, Game Playing, Knowledge Representation, Planning, Multi Agent Systems, Fuzzy Sets, Natural Language Processing, Artificial Neural Networks, Genetic Algorithms
  22. Live Classes: NTA UGC NET 2025 Live Class
  23. Paper 1 | Full Mock Tests:
  24. Paper 2 | Full Mock Tests:
  25. Paper 1 | Previous Year Papers:
  26. Paper 2 | Previous Year Papers:
AI summary & chapters

AI Summary

An AI-generated summary of this video lecture.

This lecture provides a comprehensive tutorial on solving the Travelling Salesman Problem (TSP) using the Branch and Bound algorithm with cost matrix reduction. The instructor begins by defining TSP as finding a minimum cost Hamiltonian cycle that visits each city exactly once and returns to the start. Using a 5-city example (A-E), he demonstrates how to represent the problem as a weighted graph and convert it into an adjacency cost matrix. The core of the lecture focuses on the step-by-step execution of Branch and Bound: calculating initial lower bounds via row and column reductions, branching by selecting edges (e.g., 1->2), setting forbidden transitions to infinity to prevent cycles, and recursively computing lower bounds for child nodes. The instructor illustrates how to prune branches where the cost exceeds the current best solution, ultimately identifying the optimal tour with a minimum total cost of 28.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The instructor introduces the Travelling Salesman Problem (TSP) using Branch and Bound, defining it as finding a minimum cost tour that visits each city exactly once and returns to the start. He begins illustrating the problem by drawing a graph with nodes representing cities (A, B, C, D, E) and labeling the edge between A and B with a cost of 10. On-screen text specifies 'Input: n cities, Cost matrix C[i][j]' and 'Output: Minimum cost Hamiltonian Cycle'. The instructor points to specific edges while explaining how distances are stored in a cost matrix, emphasizing the goal of finding a minimum cost Hamiltonian cycle.

  2. 2:00 – 5:00 02:00-05:00

    The instructor explains the mapping of a directed graph with weighted edges to an adjacency cost matrix. He points out specific distances between cities (nodes A, B, C, D, E) and fills in the corresponding values in the matrix. The visual evidence shows the progression of filling the first row of the cost matrix based on the graph's edge weights. He writes 'n=5' indicating the number of cities and draws a large bracket for the cost matrix. Text on screen notes 'Diagonal entries = infinity (a city cannot be visited again immediately)' and 'C[i][j] = cost of travelling from city i to city j'.

  3. 5:00 – 10:00 05:00-10:00

    The instructor works through a Traveling Salesperson Problem (TSP) example using a 5x5 cost matrix. He begins by pointing to the original matrix displayed on the screen, which contains infinity symbols representing non-existent paths. He then proceeds to manually copy this matrix onto the whiteboard, likely as part of a step-by-step solution process such as row or column reduction. The instructor writes '5x5' to indicate matrix dimensions and starts the initial setup for calculation, preparing to perform row reduction on the copied matrix.

  4. 10:00 – 15:00 10:00-15:00

    The instructor demonstrates the solution steps for a Traveling Salesperson Problem (TSP) using a cost matrix. He begins by performing row reduction on the initial 5x5 matrix, subtracting the minimum element of each row from all elements in that row. Subsequently, he proceeds to column reduction on the resulting matrix to further minimize costs. The visual evidence shows 'Step 1 Row reduction' and 'Step 2 Column reduction' written on the board. The final reduced matrix is displayed with zeros in both rows and columns, representing potential assignments with zero additional cost.

  5. 15:00 – 20:00 15:00-20:00

    The instructor demonstrates the Branch and Bound algorithm for solving TSP. He performs row reduction on a cost matrix to calculate an initial lower bound, then proceeds with column reduction. The process involves creating nodes in a search tree by fixing specific paths (e.g., 1->2) and recalculating the reduced cost matrix for subsequent steps. Text on screen shows 'Sum of row reduction + Sum of Column reduction = 31 + 4 = 35' and 'Node 2 Path (1->2)'. The instructor explains how to apply row and column reduction again for the new node.

  6. 20:00 – 25:00 20:00-25:00

    The instructor demonstrates the Branch and Bound algorithm for solving TSP. The lesson progresses through calculating lower bounds by performing row and column reductions on cost matrices. Specific steps involve generating child nodes, setting selected edges to infinity to prevent cycles, and computing new lower bounds for branching. The instructor writes 'Step 5: Generate child nodes by selecting the next city (Branching)' and 'Set all elements of row i to infinity'. He explains calculating the total cost as sum of reductions and shows 'LB = Sum of Row Reductions + Sum of Column Reductions'.

  7. 25:00 – 30:00 25:00-30:00

    The instructor explains the TSP using Branch and Bound with cost matrix reduction. He demonstrates how to calculate the lower bound (cost) for a root node by summing row and column reductions. The process involves creating a reduced cost matrix where infinity symbols represent forbidden self-loops, and then branching to create sub-nodes (like Node 4 and Node 5) by eliminating specific paths. Text on screen shows 'Root Node Cost = Sum of row reduction + Sum of column reduction' and '= 21 + 4 = 25'. He marks 'Path (1->4) elimination' and 'Path (1->5) elimination'.

  8. 30:00 – 35:00 30:00-35:00

    The instructor is solving a Traveling Salesperson Problem (TSP) using the Branch and Bound method with Cost Matrix Reduction. He is working on Node 6, where he has established a path starting from node 1 to node 4. He is now extending this path by adding the transition from node 4 to node 2, creating a partial tour (1 -> 4 -> 2). The instructor writes 'Node 6' and '(1 -> 4)' on the board. He marks infinite costs for invalid transitions, such as '(2 -> 1) = infinity', and shows cost matrix reduction steps.

  9. 35:00 – 40:00 35:00-40:00

    The instructor is solving a Traveling Salesperson Problem (TSP) using the Branch and Bound method. He calculates the cost of a specific path, specifically focusing on Node 6 where the path is (1->4->3). He computes a lower bound by summing elements from the reduced cost matrix, resulting in a value of 28. The process involves reducing rows and columns to find the minimum cost path. Text on screen shows 'Node (6)' and '(1->4->3)', with a calculation '= 25 + 3 + 0 = 28'. He demonstrates cost calculation formula and uses infinity for non-existent edges.

  10. 40:00 – 45:00 40:00-45:00

    The instructor is solving a Traveling Salesperson Problem (TSP) using the Branch and Bound method. He calculates lower bounds for different nodes by summing row reduction costs, column reduction costs, and the cost of the selected edge. The process involves creating a reduced cost matrix for each node to determine the next best path. He calculates lower bound for Node 4 and draws the reduced cost matrix for Node 5. Text on screen shows '= 25 + 12 + 13' and '= 50'. He traces paths like '(1->4->5)' and identifies infinity values in the matrix.

  11. 45:00 – 50:00 45:00-50:00

    The instructor is solving a Traveling Salesperson Problem (TSP) using the Branch and Bound method with cost matrix reduction. He calculates a total cost of 52 by summing reduction values (28 + 11 + 13). The lesson progresses to defining a complete path (1 -> 4 -> 2 -> 5) and setting up the next node in the branch and bound tree, specifically handling the constraint that city 5 cannot go to itself (infinity cost). Text on screen shows '= 28 + 11 + 13 = 52' and 'Node 10 Complete Path (1->4->2->5)'. He marks '(5,5) = infinity'.

  12. 50:00 – 55:00 50:00-55:00

    The instructor is solving a Traveling Salesperson Problem (TSP) using the Branch and Bound method. He calculates the cost of a specific path (1->4->2->5->3) by summing edge weights from the cost matrix, resulting in a total cost of 28. He then updates the current best cost and discusses pruning branches where the path cost exceeds this limit. Text on screen shows '1->4->2->5->3' and '= 28 + 0 + 0'. He marks invalid edges with infinity, such as '(5,3) = infinity' and '(5,4) = infinity', while updating 'Current Best Cost = 28'.

  13. 55:00 – 60:00 55:00-60:00

    The instructor continues to refine the solution by checking validity of edges in the matrix. He calculates total cost for path 1->4->2->5->3, confirming the result of 28. He updates current best cost to 28 and discusses pruning branches where the path cost exceeds this limit. The instructor marks invalid edges with infinity, such as '(5,3) = infinity' and '(5,4) = infinity', while updating 'Current Best Cost = 28'. He ensures all constraints are met for the optimal tour.

  14. 60:00 – 65:00 60:00-65:00

    The instructor continues to refine the solution by checking validity of edges in the matrix. He calculates total cost for path 1->4->2->5->3, confirming the result of 28. He updates current best cost to 28 and discusses pruning branches where the path cost exceeds this limit. The instructor marks invalid edges with infinity, such as '(5,3) = infinity' and '(5,4) = infinity', while updating 'Current Best Cost = 28'. He ensures all constraints are met for the optimal tour.

  15. 65:00 – 70:00 65:00-70:00

    The instructor continues to refine the solution by checking validity of edges in the matrix. He calculates total cost for path 1->4->2->5->3, confirming the result of 28. He updates current best cost to 28 and discusses pruning branches where the path cost exceeds this limit. The instructor marks invalid edges with infinity, such as '(5,3) = infinity' and '(5,4) = infinity', while updating 'Current Best Cost = 28'. He ensures all constraints are met for the optimal tour.

  16. 70:00 – 72:40 70:00-72:40

    The instructor concludes the lecture by summarizing the Branch and Bound method for TSP. He reviews the final optimal path (1->4->2->5->3) with a total cost of 28. He emphasizes the importance of pruning branches where costs exceed the current best solution to optimize efficiency. The instructor reiterates how setting infinity values prevents cycles and ensures a valid Hamiltonian cycle is found. He wraps up by confirming the minimum cost tour for the given 5-city problem.

The lecture systematically guides students through the Branch and Bound algorithm for solving the Travelling Salesman Problem (TSP). It begins with foundational concepts, defining TSP as finding a minimum cost Hamiltonian cycle and representing it via a weighted graph and adjacency cost matrix. The instructor then transitions to the algorithmic solution, starting with row and column reductions to establish an initial lower bound. The core of the lesson involves branching: selecting edges, setting forbidden transitions to infinity to prevent cycles, and recursively computing lower bounds for child nodes. Key techniques include calculating the sum of reductions plus path costs to determine node costs, and pruning branches where costs exceed the current best solution. The example progresses through multiple nodes (Node 1 to Node 10), demonstrating how partial tours are extended and validated. The final result identifies the optimal path (1->4->2->5->3) with a minimum cost of 28, illustrating the effectiveness of Branch and Bound in finding optimal solutions for combinatorial optimization problems.

Loading lesson…