{"id":689,"date":"2016-02-22T05:50:16","date_gmt":"2016-02-22T04:50:16","guid":{"rendered":"https:\/\/launix.de\/launix\/?p=689"},"modified":"2016-02-22T15:56:51","modified_gmt":"2016-02-22T14:56:51","slug":"warum-der-handlungsreisende-nicht-die-beste-route-findet","status":"publish","type":"post","link":"https:\/\/launix.de\/launix\/warum-der-handlungsreisende-nicht-die-beste-route-findet\/","title":{"rendered":"Warum der Handlungsreisende nicht die beste Route findet"},"content":{"rendered":"<p>Kennen Sie das <a href=\"https:\/\/de.wikipedia.org\/wiki\/Problem_des_Handlungsreisenden\" target=\"_blank\">Problem des Handlungsreisenden<\/a>? Der Handlungsreisende soll die k\u00fcrzeste Route finden, mit der er alle gr\u00f6\u00dften 15 deutschen St\u00e4dte besuchen kann. Das Problem dabei: durch die 15 St\u00e4dte gibt es 43.589.145.600 m\u00f6gliche Routen. Und in der Informatik wurde momentan noch kein allgemeiner L\u00f6sungsweg gefunden, keine 43.589.145.600 M\u00f6glichkeiten durchzuprobieren.<\/p>\n<h2>Es gibt dutzende solcher schweren Probleme in der Informatik<\/h2>\n<p>Die Handlungsreisenden sind nicht allen. Derart hohen Rechenaufwand zur Probleml\u00f6sung m\u00fcssen auch f\u00fcr andere Probleme aufgewandt werden:<\/p>\n<ul>\n<li>Das Rucksackproblem: Ein Rucksack mit definiertem Volumen soll mit Gegenst\u00e4nden von gewissem Wert und Volumen gef\u00fcllt werden, sodass man den maximalen Wert erreicht.<\/li>\n<li>Cliquenproblem: Finde die gr\u00f6\u00dfte Clique, bei der jeder mit jedem vernetzt ist (z.B. auf Facebook Personen, die alle paarweise miteinander vernetzt sind)<\/li>\n<li>Job-Sequencing-Problem: Finde die optimale Auswahl und zeitliche Eintaktung von m\u00f6glichen Auftr\u00e4gen f\u00fcr eine Maschine, von denen die Abarbeitungs-Zeit, Deadline und der Profit bekannt sind.<\/li>\n<li>Terminkalender: Finden Sie f\u00fcr eine Woche mit 20 Terminen, die jeweils 2-4 Terminvorschl\u00e4ge haben eine Wochenbelegung.<\/li>\n<li>Verschl\u00fcsselung knacken: Die NSA bei\u00dft sich die Z\u00e4hne daran aus, Verbindungen zu simplen Online-Shops zu belauschen, da diese verschl\u00fcsselt sind.<\/li>\n<\/ul>\n<h2>Alle diese Probleme stellen dasselbe Problem dar<\/h2>\n<p>All diesen harten Probleme haben eins gemeinsam: Sie stellen ein- und dasselbe Problem dar und lassen sich ineinander umwandeln. So l\u00e4sst sich beispielsweise das Problem des Handlungsreisenden auch als Rucksackproblem darstellen, indem das Gewicht der St\u00fccke f\u00fcr den Rucksack die 15 zu erreichenden St\u00e4dte darstellt und der Wert der St\u00fccke die negierte Entfernung der St\u00e4dte zueinander.<\/p>\n<h2>Symbolisches Rechnen<\/h2>\n<p>Eines dieser harten Probleme (auch <a href=\"https:\/\/de.wikipedia.org\/wiki\/NP-Schwere\" target=\"_blank\">NP-Hart<\/a> genannt) ist das sogenannte <a href=\"https:\/\/de.wikipedia.org\/wiki\/Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik\" target=\"_blank\">SAT-Problem<\/a>: Gegeben eine logische Formel ist zu pr\u00fcfen, ob diese l\u00f6sbar ist.<\/p>\n<p>Genialerweise l\u00e4sst sich jedes dieser Optimierungs- und Suchprobleme als eine logische Formel darstellen, die als SAT-Problem gel\u00f6st werden kann. Zudem ist SAT durch die einfache <a href=\"https:\/\/de.wikipedia.org\/wiki\/3-SAT\" target=\"_blank\">3-SAT<\/a>-Schreibweise sehr handlich. Ein Programm, das SAT-Probleme l\u00f6sen kann, nennt man <b>SAT-Solver<\/b>.<\/p>\n<p>Das Grundprinzip eines SAT-Solvers ist einfach: Die gegebene logische Formel wird so lange umgestellt, bis die L\u00f6sung aus der Formel ablesbar ist. Jedoch muss ein SAT-Solver bei unbekannten Werten (entweder 1 oder 0) beide Varianten durchprobieren, um die L\u00f6sung zu finden. Das sind bei zwei unbekannten Werten schon 4 Varianten, bei 10 Unbekannten 1024 M\u00f6glichkeiten und bei 20 Unbekannten schon eine Million.<\/p>\n<h2>Anbindung an eine Datenbasis<\/h2>\n<p>Die Kunst, SAT praktisch anzuwenden liegt darin, Probleme als SAT-Probleme zu definieren. So k\u00f6nnen beispielsweise Fakten aus einer Datenbank als Formeln kodiert werden, um sp\u00e4ter Schlussfolgerungen aus den Daten zu ziehen.<\/p>\n<p>Wir bei Launix k\u00f6nnen Ihnen helfen, Daten digital zu verwalten, sowie f\u00fcr SAT-Solver aufzubereiten. Mit unseren Datenbanken er\u00f6ffnen sich neue Wege f\u00fcrs Planen und Optimieren.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Kennen Sie das Problem des Handlungsreisenden? Der Handlungsreisende soll die k\u00fcrzeste Route finden, mit der er alle gr\u00f6\u00dften 15 deutschen St\u00e4dte besuchen kann. Das Problem dabei: durch die 15 St\u00e4dte gibt es 43.589.145.600 m\u00f6gliche Routen. Und in der Informatik wurde momentan noch kein allgemeiner L\u00f6sungsweg gefunden, keine 43.589.145.600 M\u00f6glichkeiten durchzuprobieren. Es gibt dutzende solcher schweren&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_editorskit_title_hidden":false,"_editorskit_reading_time":0,"_editorskit_is_block_options_detached":false,"_editorskit_block_options_position":"{}","_uag_custom_page_level_css":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-689","post","type-post","status-publish","format-standard","hentry","category-allgemein","single-item"],"featured_image_urls_v2":{"full":"","thumbnail":"","medium":"","medium_large":"","large":"","1536x1536":"","2048x2048":"","trp-custom-language-flag":"","xs-thumb":"","appku-shop-single":""},"post_excerpt_stackable_v2":"<p>Kennen Sie das Problem des Handlungsreisenden? Der Handlungsreisende soll die k\u00fcrzeste Route finden, mit der er alle gr\u00f6\u00dften 15 deutschen St\u00e4dte besuchen kann. Das Problem dabei: durch die 15 St\u00e4dte gibt es 43.589.145.600 m\u00f6gliche Routen. Und in der Informatik wurde momentan noch kein allgemeiner L\u00f6sungsweg gefunden, keine 43.589.145.600 M\u00f6glichkeiten durchzuprobieren. Es gibt dutzende solcher schweren Probleme in der Informatik Die Handlungsreisenden sind nicht allen. Derart hohen Rechenaufwand zur Probleml\u00f6sung m\u00fcssen auch f\u00fcr andere Probleme aufgewandt werden: Das Rucksackproblem: Ein Rucksack mit definiertem Volumen soll mit Gegenst\u00e4nden von gewissem Wert und Volumen gef\u00fcllt werden, sodass man den maximalen Wert erreicht. Cliquenproblem:&hellip;<\/p>\n","category_list_v2":"<a href=\"https:\/\/launix.de\/launix\/category\/allgemein\/\" rel=\"category tag\">Allgemein<\/a>","author_info_v2":{"name":"Carl-Philip H\u00e4nsch","url":"https:\/\/launix.de\/launix\/author\/carli\/"},"comments_num_v2":"0 comments","uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false,"trp-custom-language-flag":false,"xs-thumb":false,"appku-shop-single":false},"uagb_author_info":{"display_name":"Carl-Philip H\u00e4nsch","author_link":"https:\/\/launix.de\/launix\/author\/carli\/"},"uagb_comment_info":0,"uagb_excerpt":"Kennen Sie das Problem des Handlungsreisenden? Der Handlungsreisende soll die k\u00fcrzeste Route finden, mit der er alle gr\u00f6\u00dften 15 deutschen St\u00e4dte besuchen kann. Das Problem dabei: durch die 15 St\u00e4dte gibt es 43.589.145.600 m\u00f6gliche Routen. Und in der Informatik wurde momentan noch kein allgemeiner L\u00f6sungsweg gefunden, keine 43.589.145.600 M\u00f6glichkeiten durchzuprobieren. Es gibt dutzende solcher schweren...","_links":{"self":[{"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/posts\/689","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/comments?post=689"}],"version-history":[{"count":8,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/posts\/689\/revisions"}],"predecessor-version":[{"id":697,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/posts\/689\/revisions\/697"}],"wp:attachment":[{"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/media?parent=689"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/categories?post=689"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/tags?post=689"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}