{"id":2224,"date":"2025-06-17T00:00:00","date_gmt":"2025-06-17T00:00:00","guid":{"rendered":"urn:uuid:9e5f8ba5-b762-43d2-8196-0d65bc43e26b"},"modified":"2025-06-17T00:00:00","modified_gmt":"2025-06-17T00:00:00","slug":"xun-hui-serusumanwen-ti","status":"publish","type":"post","link":"https:\/\/www.sekaiken.com\/?p=2224","title":{"rendered":"\u5de1\u56de\u30bb\u30fc\u30eb\u30b9\u30de\u30f3\u554f\u984c"},"content":{"rendered":"<p>\u6628\u65e5\u306e\u79d8\u66f8\u554f\u984c\u306b\u306f\u6700\u9069\u89e3\u304c\u3042\u308a\u307e\u3057\u305f\u304c\u3001\u6700\u9069\u89e3\u304c\u307e\u3060\u898b\u3064\u304b\u3063\u3066\u3044\u306a\u3044\u554f\u984c\u3082\u305f\u304f\u3055\u3093\u3042\u308a\u307e\u3059\u3002\u6709\u540d\u306a\u3082\u306e\u306e\u3072\u3068\u3064\u304c\u300c\u5de1\u56de\u30bb\u30fc\u30eb\u30b9\u30de\u30f3\u554f\u984c\u300d\u3067\u3059\u3002\u6700\u521d\u306b\u8003\u3048\u305f\u30cf\u30df\u30eb\u30c8\u30f3\u306f\u56db\u5143\u6570\u3084\u884c\u5217\u306e\u5b9a\u7406\u3067\u6709\u540d\u306a\u30a2\u30a4\u30eb\u30e9\u30f3\u30c9\u306e\u6570\u5b66\u8005\u3067\u3059\u3002\u8272\u3005\u306a\u3053\u3068\u3092\u3084\u3063\u3066\u3044\u307e\u3059\u306d\u3002<br \/>\nhttps:\/\/www.msi.co.jp\/solution\/nuopt\/docs\/designs\/articles\/traveling-salesman-problem.html<\/p>\n<p>AI\u306b\u3088\u308b\u6982\u8981\u300c\u4e0e\u3048\u3089\u308c\u305f\u8907\u6570\u306e\u90fd\u5e02\u3092\u3059\u3079\u3066\u4e00\u5ea6\u305a\u3064\u5de1\u308a\u3001\u51fa\u767a\u5730\u306b\u623b\u308b\u969b\u306e\u6700\u77ed\u7d4c\u8def\u3092\u6c42\u3081\u308b\u554f\u984c\u3067\u3059\u3002\u3053\u306e\u554f\u984c\u306f\u3001\u7d44\u5408\u305b\u6700\u9069\u5316\u554f\u984c\u306e\u4e2d\u3067\u3082\u7279\u306b\u6709\u540d\u3067\u3001\u7269\u6d41\u3001\u914d\u9001\u30eb\u30fc\u30c8\u306e\u6700\u9069\u5316\u3001\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u8a2d\u8a08\u306a\u3069\u3001\u69d8\u3005\u306a\u5206\u91ce\u3067\u5fdc\u7528\u3055\u308c\u3066\u3044\u307e\u3059\u300d\u3060\u305d\u3046\u3067\u3059\u3002<br \/>\n\u4e0e\u3048\u3089\u308c\u305f\u90fd\u5e02\u9593\u306e\u8ddd\u96e2\u306e\u4e00\u89a7\u304b\u3089\u6700\u77ed\u7d4c\u8def\u3092\u6c42\u3081\u308b\u65b9\u6cd5\u3092\u63a2\u3059\u969b\u3001\u51fa\u6765\u308b\u3060\u3051\u6700\u77ed\u306b\u8fd1\u3044\u3082\u306e\u3092\u63a2\u3059\u304b\u3001\u8a08\u7b97\u6642\u9593\u3092\u77ed\u304f\u3059\u308b\u304b\u306e\u517c\u306d\u5408\u3044\u3067\u3059\u3002\u8a08\u7b97\u91cf\u306e\u8b70\u8ad6\u306b\u3064\u306a\u304c\u308a\u307e\u3059\u3002\u3059\u306a\u308f\u3061\u3001\u90fd\u5e02\u304cn\u500b\u3042\u308b\u6642\u306b&rdquo;\u5358\u7d14\u306a\u8a08\u7b97\u6a5f&rdquo;\u3092\u4f7f\u3063\u3066\u3001n\u304c\u5897\u3048\u305f\u3068\u304d\u306bn\u306e\u591a\u9805\u5f0f\u3067\u5897\u3048\u308b\u6642\u9593\u3067\u89e3\u3051\u308b\u304b\u3069\u3046\u304b(P)\u3001&rdquo;\u63a2\u7d22\u3067\u304d\u308b\u8a08\u7b97\u6a5f&rdquo;\u3092\u4f7f\u3063\u3066n\u306e\u591a\u9805\u5f0f\u3067\u5897\u3048\u308b\u6642\u9593\u3067\u89e3\u3051\u308b\u304b\u3069\u3046\u304b(NP)\u3001\u305d\u308c\u304c\u3067\u304d\u306a\u3044\u304b(NP\u56f0\u96e3\uff09\u306a\u3069\u3001\u982d\u304c\u75db\u304f\u306a\u308a\u305d\u3046\u306a\u672a\u89e3\u6c7a\u9818\u57df\u304c\u3042\u308a\u307e\u3059\u3002\u89e3\u8aac\u3068\u3057\u3066\u306f\u4e0b\u8a18\u304c\u7c21\u6f54\u3067\u308f\u304b\u308a\u3084\u3059\u3044\u3067\u3059\u3002<br \/>\n<iframe class=\"wp-embedded-content\" sandbox=\"allow-scripts\" security=\"restricted\" title=\"\u521d\u5fc3\u8005\u304c\u5b66\u3076P,NP,NP\u56f0\u96e3(Hard),NP\u5b8c\u5168(Complete)\u3068\u306f\uff08\u308f\u304b\u308a\u3084\u3059\u304f\u89e3\u8aac\uff09 - MotoJapan&#039;s Tech-Memo\" src=\"https:\/\/hatenablog-parts.com\/embed?url=https%3A%2F%2Fmotojapan.hateblo.jp%2Fentry%2F2017%2F11%2F15%2F082738#?secret=cXrHiRvGkI\" data-secret=\"cXrHiRvGkI\" scrolling=\"no\" frameborder=\"0\"><\/iframe><br \/>\n\u73fe\u5b9f\u554f\u984c\u3068\u3057\u3066\u306f\u30bb\u30fc\u30eb\u30b9\u30de\u30f3\u306f\u5de1\u56de\u3057\u306a\u3051\u308c\u3070\u4ed5\u4e8b\u306b\u306a\u3089\u306a\u3044\u306e\u3067\u3001\u826f\u3055\u305d\u3046\u306a\u7d4c\u8def\u3092\u63a2\u3059\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u3044\u308d\u3044\u308d\u3042\u308a\u307e\u3059\u3002\u9762\u767d\u305d\u3046\u306a\u306e\u3092\uff12\u3064\u7d39\u4ecb\u3057\u307e\u3059\u3002<br \/>\n\uff11\u3064\u306f2-opt\u6cd5\u3067\u3001\u77ed\u304f\u306a\u308b\u5834\u5408\u306b\uff12\u3064\u306e\u90fd\u5e02\u3092\u7d50\u3076\u7d4c\u8def\u3092\u4ea4\u63db\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u3059\u3002\u3053\u308c\u306f\u9577\u3055\u306e\u5909\u5316\u306e\u8a08\u7b97\u304cn\u306b\u3088\u3089\u305a\u77ed\u6642\u9593\u3067\u7d42\u308f\u308b\u3053\u3068\u3092\u5229\u7528\u3057\u307e\u3059\u3002\u6c7a\u3081\u305f\u56de\u6570\u7e70\u308a\u8fd4\u3057\u3066\u7b54\u3068\u3059\u308b\u306e\u3060\u3068\u601d\u3044\u307e\u3059\u3002\u3053\u308c\u306f\u5c40\u6240\u7684\u306b\u3057\u304b\u898b\u306a\u3044\u65b9\u6cd5\u3068\u8a00\u3048\u308b\u3067\u3057\u3087\u3046\u3002<br \/>\nhttps:\/\/ja.wikipedia.org\/wiki\/2-opt<br \/>\n\u3082\u3046\u4e00\u3064\u306f\u713c\u304d\u306a\u307e\u3057\u6cd5(Simulated annealing)\u3067\u3059\u3002<br \/>\n\u73fe\u5728\u306e\u7d4c\u8def\u304b\u3089\uff12\u90fd\u5e02\u3092\u4ea4\u63db\u3057\u305f\u7d4c\u8def\u3092\u4f5c\u308a\u3001\u6bd4\u3079\u3066\u307f\u3066\u77ed\u304f\u306a\u3063\u3066\u3044\u308c\u3070\u63a1\u7528\u3001\u9577\u304f\u306a\u3063\u3066\u3044\u3066\u3082\u300c\u3042\u308b\u9577\u3055\u300d\u307e\u3067\u306a\u3089\u3070\u8a31\u5bb9\u3057\u63a1\u7528\u3001\u305d\u3046\u3067\u306a\u3051\u308c\u3070\u5909\u66f4\u3092\u5374\u4e0b\u3001\u3068\u3044\u3046\u306e\u3092\u7e70\u308a\u8fd4\u3057\u307e\u3059\u3002\u8a31\u5bb9\u3055\u308c\u308b\u5897\u52a0\u5206\u306f\u6700\u521d\u306f\u5927\u304d\u3044\u5024\u306b\u3057\u3066\u3001\u3060\u3093\u3060\u3093\u5c0f\u3055\u304f\u3057\u3066\u3044\u304d\u307e\u3059\u3002\u305d\u306e\u69d8\u5b50\u304c\u91d1\u5c5e\u306e\u713c\u304d\u306a\u307e\u3057\u306b\u4f3c\u3066\u3044\u308b\u3068\u3044\u3046\u306e\u3067\u3053\u306e\u540d\u524d\u304c\u3042\u308a\u307e\u3059\u3002\u9577\u304f\u306a\u3063\u3066\u3044\u3066\u3082\u8a31\u5bb9\u3055\u308c\u308b\u5834\u5408\u304c\u3042\u308b\u305f\u3081\u3001\u5c40\u6240\u7684\u306a\u6700\u9069\u5024\uff08\u6975\u5c0f\u70b9\uff09\u3067\u6b62\u307e\u3063\u3066\u3057\u307e\u3046\u306e\u3092\u9632\u3050\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002<br \/>\nhttps:\/\/ja.wikipedia.org\/wiki\/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95<br \/>\n\u713c\u304d\u306a\u307e\u3057\u6cd5\u306f\u3001\u4e00\u7a2e\u306e\u91cf\u5b50\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u3067\u9ad8\u901f\u306b\u884c\u3048\u308b\u3053\u3068\u304c\u5206\u304b\u3063\u305f\u306e\u3067\u30ab\u30ca\u30c0-\u7c73\u56fd\u306e\u30d9\u30f3\u30c1\u30e3\u30fcD-wave\u793e\u304c\u6d3b\u52d5\u3057\u3066\u3044\u307e\u3059\u3002\u6765\u9031\u7d30\u304b\u304f\u898b\u3066\u307f\u307e\u3057\u3087\u3046\u304b\u3002<\/p>\n<p>\u82f1\u8a9e\u306f\u3000https:\/\/en.wikipedia.org\/wiki\/Travelling_salesman_problem\u3000\u304b\u3089\u3002<br \/>\n\u201dIn the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: &ldquo;Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?&rdquo; It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.\u201d<br \/>\nGiven a list of&hellip; \uff5e\u304c\u4e0e\u3048\u3089\u308c\u305f\u3068\u304d  (if you are given a list of &hellip;)<br \/>\ncombinatorial optimization \u7d44\u307f\u5408\u308f\u305b\u6700\u9069\u5316<br \/>\n\u201dEven though the problem is computationally difficult, many heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely, and even problems with millions of cities can be approximated within a small fraction of 1%.\u201d<br \/>\nheuristics \u30d2\u30e5\u30fc\u30ea\u30b9\u30c6\u30a3\u30c3\u30af\u30b9\u3000\u767a\u898b\u7684\u624b\u6cd5\u3001\u7d4c\u9a13\u5247\u306b\u3088\u308b\u65b9\u6cd5<br \/>\na small fraction of 1%  1%\u306e\u5c0f\u3055\u3044\u4e00\u90e8\u3067\uff1b\u30001%\u3088\u308a\u3082\u305a\u3063\u3068\u5c0f\u3055\uff08\u6642\u9593\uff09\u3067<br \/>\n\u201dThe TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. \u201d<br \/>\nlogistics \u5175\u7ad9\uff08\u3078\u3044\u305f\u3093\uff09\u3001\u88dc\u7d66<br \/>\nmanufacture of microchips \u30de\u30a4\u30af\u30ed\u30c1\u30c3\u30d7\u306e\u88fd\u9020\u3000\uff08\u914d\u7dda\u304c\u77ed\u304f\u306a\u308b\u3088\u3046\u306b)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6628\u65e5\u306e\u79d8\u66f8\u554f\u984c\u306b\u306f\u6700\u9069\u89e3\u304c\u3042\u308a\u307e\u3057\u305f\u304c\u3001\u6700\u9069\u89e3\u304c\u307e\u3060\u898b\u3064\u304b\u3063\u3066\u3044\u306a\u3044\u554f\u984c\u3082\u305f\u304f\u3055\u3093\u3042\u308a\u307e\u3059\u3002\u6709\u540d\u306a\u3082\u306e\u306e\u3072\u3068\u3064\u304c\u300c\u5de1\u56de\u30bb\u30fc\u30eb\u30b9\u30de\u30f3\u554f\u984c\u300d\u3067\u3059\u3002\u6700\u521d\u306b\u8003\u3048\u305f\u30cf\u30df\u30eb\u30c8\u30f3\u306f\u56db\u5143\u6570\u3084\u884c\u5217\u306e\u5b9a\u7406\u3067\u6709\u540d\u306a\u30a2\u30a4\u30eb\u30e9\u30f3\u30c9\u306e\u6570\u5b66\u8005\u3067\u3059\u3002\u8272\u3005\u306a\u3053\u3068\u3092\u3084\u3063\u3066\u3044\u307e\u3059\u306d\u3002 https:\/\/www.msi.co.jp\/solution\/nuopt\/docs\/designs\/articles\/traveling-salesman-problem.html AI\u306b\u3088\u308b\u6982\u8981\u300c\u4e0e\u3048\u3089\u308c\u305f\u8907\u6570\u306e\u90fd\u5e02\u3092\u3059\u3079\u3066\u4e00\u5ea6\u305a\u3064\u5de1\u308a\u3001\u51fa\u767a\u5730\u306b\u623b\u308b\u969b\u306e\u6700\u77ed\u7d4c\u8def\u3092\u6c42\u3081\u308b\u554f\u984c\u3067\u3059\u3002\u3053\u306e\u554f\u984c\u306f\u3001\u7d44\u5408\u305b\u6700\u9069\u5316\u554f\u984c\u306e\u4e2d\u3067\u3082\u7279\u306b\u6709\u540d\u3067\u3001\u7269\u6d41\u3001\u914d\u9001\u30eb\u30fc\u30c8\u306e\u6700\u9069&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[60,52],"tags":[23,15],"class_list":["post-2224","post","type-post","status-publish","format-standard","hentry","category-computer","category-economics","tag-computer","tag-economics"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=\/wp\/v2\/posts\/2224","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2224"}],"version-history":[{"count":0,"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=\/wp\/v2\/posts\/2224\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sekaiken.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}