{"id":33894,"date":"2024-11-01T09:21:43","date_gmt":"2024-11-01T09:21:43","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33894"},"modified":"2024-11-01T10:55:23","modified_gmt":"2024-11-01T10:55:23","slug":"c-coding-test-course-tsp-traveling-salesman-problem-pathfinding","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33894\/","title":{"rendered":"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding"},"content":{"rendered":"<article>\n<p>One of the frequently asked problems in coding tests is the &#8216;Traveling Salesman Problem&#8217;. This problem involves finding the minimum cost route that visits a given set of cities and returns to the starting city. It belongs to the class of NP-complete problems, making it very difficult to find an optimal solution. Therefore, it is common to use various search algorithms to find an approximate solution or to use dynamic programming (DP) to find the optimal solution.<\/p>\n<h2>Problem Definition<\/h2>\n<p>Assume there are n cities and each city is connected to different other cities. Given the travel costs between each pair of cities, output the minimum cost journey that visits all cities exactly once and returns to the starting city.<\/p>\n<h3>Input<\/h3>\n<ul>\n<li>The first line contains the number of cities n (1 \u2264 n \u2264 10).<\/li>\n<li>The next n lines contain an n x n adjacency matrix. Each element of the matrix represents the travel cost between two cities. If there is no travel cost, 0 is given.<\/li>\n<\/ul>\n<h3>Output<\/h3>\n<p>Output the minimum cost of visiting all cities exactly once and returning to the starting point.<\/p>\n<h2>Example<\/h2>\n<pre>\n        Input:\n        4\n        0 10 15 20\n        10 0 35 25\n        15 35 0 30\n        20 25 30 0\n\n        Output:\n        80\n    <\/pre>\n<h2>Problem Solving Process<\/h2>\n<h3>1. Problem Analysis<\/h3>\n<p>According to the literature, this problem is known to be NP-complete, and can be approached using a brute-force method that tries all possible routes. However, when the number of cities is less than or equal to 10, it can be shown that this method is practical. The number of cases that visit each city exactly once is (n-1)!, which is a computable range when n is 10 (9! = 362880).<\/p>\n<h3>2. Algorithm Selection<\/h3>\n<p>Here, we will choose an algorithm that explores all paths using a backtracking technique to calculate the minimum cost. This algorithm recursively explores possible paths based on the current city, and if it can no longer proceed, it goes back to the previous step to try a different path. This allows for consideration of all possible cases to find the minimum cost.<\/p>\n<h3>3. C# Code Implementation<\/h3>\n<pre>\n        <code>\n        using System;\n\n        class Program\n        {\n            static int n; \/\/ number of cities\n            static int[,] cost; \/\/ travel cost matrix\n            static bool[] visited; \/\/ visited city check\n            static int minCost = int.MaxValue; \/\/ minimum cost\n\n            static void Main(string[] args)\n            {\n                n = int.Parse(Console.ReadLine());\n                cost = new int[n, n];\n                visited = new bool[n];\n\n                for (int i = 0; i &lt; n; i++)\n                {\n                    var line = Console.ReadLine().Split();\n                    for (int j = 0; j &lt; n; j++)\n                    {\n                        cost[i, j] = int.Parse(line[j]);\n                    }\n                }\n\n                visited[0] = true; \/\/ mark the starting city as visited\n                FindPath(0, 0, 1); \/\/ current city(0), current cost(0), number of visited cities(1)\n                Console.WriteLine(minCost);\n            }\n\n            static void FindPath(int currentCity, int currentCost, int count)\n            {\n                if (count == n &amp;&amp; cost[currentCity, 0] != 0) \/\/ if all cities have been visited\n                {\n                    minCost = Math.Min(minCost, currentCost + cost[currentCity, 0]);\n                    return;\n                }\n\n                for (int nextCity = 0; nextCity &lt; n; nextCity++)\n                {\n                    if (!visited[nextCity] &amp;&amp; cost[currentCity, nextCity] != 0)\n                    {\n                        visited[nextCity] = true;\n                        FindPath(nextCity, currentCost + cost[currentCity, nextCity], count + 1);\n                        visited[nextCity] = false; \/\/ backtracking\n                    }\n                }\n            }\n        }\n        <\/code>\n        <\/pre>\n<h3>4. Code Explanation<\/h3>\n<p>The above code takes the number of cities as input and generates the given adjacency matrix. Then, it uses the <code>FindPath<\/code> function to explore all paths. The main parameters of this function are as follows:<\/p>\n<ul>\n<li><strong>currentCity:<\/strong> the city currently being visited<\/li>\n<li><strong>currentCost:<\/strong> the travel cost so far<\/li>\n<li><strong>count:<\/strong> the number of visited cities so far<\/li>\n<\/ul>\n<p>Basically, the starting city is marked as visited, and when all cities are visited, the cost to return to the starting city is calculated and compared to the minimum cost. If it can be reduced further, the <code>minCost<\/code> is updated.<\/p>\n<h3>5. Time Complexity<\/h3>\n<p>The time complexity of this problem is O(n!). Since it explores all combinations of visiting the cities, the computation increases exponentially as the number of cities increases.<\/p>\n<h2>Conclusion<\/h2>\n<p>In this lecture, we covered how to solve the problem of finding the minimum cost of the Traveling Salesman Problem using C#. This problem can be solved using basic backtracking algorithms, and various optimization techniques and dynamic programming can also be applied for better efficiency. In the future, we will also cover these techniques.<\/p>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>One of the frequently asked problems in coding tests is the &#8216;Traveling Salesman Problem&#8217;. This problem involves finding the minimum cost route that visits a given set of cities and returns to the starting city. It belongs to the class of NP-complete problems, making it very difficult to find an optimal solution. Therefore, it is &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33894\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[90],"tags":[],"class_list":["post-33894","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33894\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"One of the frequently asked problems in coding tests is the &#8216;Traveling Salesman Problem&#8217;. This problem involves finding the minimum cost route that visits a given set of cities and returns to the starting city. It belongs to the class of NP-complete problems, making it very difficult to find an optimal solution. Therefore, it is &hellip; \ub354 \ubcf4\uae30 &quot;C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33894\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:21:43+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:55:23+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33894\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33894\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding\",\"datePublished\":\"2024-11-01T09:21:43+00:00\",\"dateModified\":\"2024-11-01T10:55:23+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33894\/\"},\"wordCount\":505,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C# Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33894\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33894\/\",\"name\":\"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:21:43+00:00\",\"dateModified\":\"2024-11-01T10:55:23+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33894\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33894\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33894\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33894\/","og_locale":"ko_KR","og_type":"article","og_title":"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"One of the frequently asked problems in coding tests is the &#8216;Traveling Salesman Problem&#8217;. This problem involves finding the minimum cost route that visits a given set of cities and returns to the starting city. It belongs to the class of NP-complete problems, making it very difficult to find an optimal solution. Therefore, it is &hellip; \ub354 \ubcf4\uae30 \"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding\"","og_url":"https:\/\/atmokpo.com\/w\/33894\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:21:43+00:00","article_modified_time":"2024-11-01T10:55:23+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33894\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33894\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding","datePublished":"2024-11-01T09:21:43+00:00","dateModified":"2024-11-01T10:55:23+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33894\/"},"wordCount":505,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C# Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33894\/","url":"https:\/\/atmokpo.com\/w\/33894\/","name":"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:21:43+00:00","dateModified":"2024-11-01T10:55:23+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33894\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33894\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33894\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C# Coding Test Course, TSP (Traveling Salesman Problem) Pathfinding"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33894","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33894"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33894\/revisions"}],"predecessor-version":[{"id":33895,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33894\/revisions\/33895"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33894"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33894"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33894"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}