Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Open Science, Numberplay style!

27 января 2012 года в 12:06   Просмотров: 2677

LMatrix: Публикуем перевод первой части статьи.

 

На этой неделе в Science Times была размещена статья Томаса Лина об открытом научном движении, одной из идей которой является то, что ученые могут решить сложные задачи гораздо быстрее, работая сообща, чем по одиночке. Томас сразу понял, что это именно этот подход решения задач используется каждую неделю в Numberplay. В разное время подобный подход решения задач упоминали как «партнёрский» и «микрокосмос того, как наука прогрессирует». Томас предложил мне разработать задачу Numberplay, которая продемонстрировала бы это онлайн-сотрудничество.

Карта, которая показывает самое короткое расстояние между столицами штатов США и этот путь проходит через каждый город только единожды и возвращается в начальную точку.

Некоторые совместные работы (сотрудничества) появлялись на Numberplay, но задачи, которые действительно показывают этот феномен (явление) в значительной степени кажутся двух типов. Первый тип задач требует нескольких идей, которые строятся друг на друге, чтобы получить окончательное решение. Мы видели, как это произошло в задаче Turtles All The Way Down (Черепахи по дороге вниз), в которой звезда Памми Калси подал ключевую идею, на которой другие читатели построили решение задачи. Второй тип, в котором видят сотрудничество при решении открытых задач, где никто не знает лучший ответ, но чьи ответы могут быть улучшены, опираясь на предыдущие решения. Мы видели подобное сотрудничество в Shackled Communication (Скованная связь) и задаче Newton's Cradle (Колыбеле Ньютона). Поэтому, когда пришел запрос Томаса, было ясно, какие задачи мне необходимо рассмотреть.

К счастью, я читал замечательную книгу Уильяма Д. Кука «В погоне за коммивояжёрском» (“In Pursuit of the Traveling Salesman”), которая рассказывает историю, личности, задачи, приложения и методы, используемые для решения знаменитой Задачи коммивояжера и связанные с ним задачи (названные «NP-полными» или «NP-сложными»), которые не могут быть решены в разумные сроки на самых быстрых компьютерах в мире. При решении задачи коммивояжёра необходимо найти кратчайшее расстояние между городами, которые находятся на разных расстояниях друг от друга, посещая каждый город только один раз. Карта показывает решение для 50 столиц штатов. Чтобы построить ее, я взял доказанное (проверенное) лучшее решение для 48 столиц штатов, и добавил Аляску и Гавайи. Общее расстояние доходит до 16 368 миль по прямой. Наша совместная работа сегодня является одним из вариантов решения этой задачи.

Вы должны найти кратчайшее расстояние, посетив одно и только одно место в каждом штате. Любой город, деревню или поселок — пока это место находиться в выбранном штате. Все, что требуется, это, чтобы выбранное Вами место, было в списке на этом веб сайте для того, чтобы найти расстояние между ним и любым другим местом по Вашему выбору. Данные расстояния даны в милях. (Я уверен, мы сможем найти довольно безвестные места, которые расположены близко к границам штатов!)

Вы можете начать с маршрута упомянутого выше, но имейте в виду, что сейчас этот маршрут может быть не оптимальным. Поскольку мы стараемся развить сотрудничество, не пытайтесь, прилагать титанические усилия, чтобы решить эту задачу самостоятельно. Вместо этого, попытайтесь внести вклад небольшими частями оптимизации, такими как поиск городов в двух или трех штатах, так, чтобы эти города были ближе друг к другу, чем предыдущие лучшие попытки либо предложением общего маршрута. Один из методов решения Задачи коммивояжёра заключается в поиске мелких улучшений маршрута, когда при 2 оптимальных перестановках удаляется два ребра и маршрут соединяется двумя более короткими ребрами. Кроме того, может быть 3, 4 и больше перестановок. Если Вы добавляете такие перестановки, убедитесь, что при пересчете каждый раз получаете новое общее расстояние. Давайте посмотрим, как многие сотни миль можно сократить! Вы можете построить оптимизацию на предложениях других, но не забывайте ссылаться на их идеи. Это ж все-таки совместная наука!

Читатели, которые не имеют опыта работы с феноменальной сложностью чисел подобных задач, могут задаться вопросом, почему бы нам просто не использовать «грубую силу» компьютерных алгоритмов, чтобы перебрать все возможные варианты. Потому что их слишком много! Численные комбинации могут быстро опередить Закон Мура — или любой другой закон роста в физическом мире, выдавая гипер-астрономические числа. Доктор Кук считает, что самому быстому компьютеру в мире потребуется 28 триллионов лет, чтобы найти лучшее решение для 33 городов и добавляет «(это) неудобное время, учитывая, что Вселенная по оценкам просуществует только 14 миллиардов лет». Тем ни менее, люди способны находить достойные решения подобным задачам. В среднем, взрослые могут найти маршрут из 15 городов с отклонением всего в 2,7% от оптимального.

 

 

This week’s Science Times has a cover article by Thomas Lin about the open science movement, one of the whose ideas is that by collaborating over a large network, scientists can solve difficult problems much faster than they could alone. Thomas immediately realized that this is exactly the kind of problem-solving approach that happens every week on Numberplay. We have at various times referred to our unique communal problem-solving approach as a “collaboratory” and “a microcosm of how science progresses.” Thomas invited me to design a Numberplay problem that showcased this online collaboration.

 

TSP для столиц штатов Америки

A map that shows the shortest path between the U.S. state capitals that goes through each city just once and returns to the starting point.

 

Some amount of collaboration occurs on most Numberplay problems, but the problems that really show this phenomenon in large measure seem to be of two types. The first is the kind of problem which requires multiple ideas that you need to build on each other to give the eventual solution. We saw this happen, for example, in Turtles All The Way Down, in which All-Star Pummy Kalsi contributed a key idea that other readers built on to reach the solution. The second type of problems that see a lot of collaboration are open-ended problems, where no one knows exactly what the best answer is, but whose answers can be improved by building on previous solutions. We saw this kind of collaboration in Shackled Communication and the Newton’s Cradle problem. So when Thomas’s request came, it was clear what kind of problem I needed.

Fortunately, I’ve been reading William J. Cook’s fascinating book “In Pursuit of the Traveling Salesman,” which describes the history, personalities, challenges, applications and techniques used to find solutions of the famous “Traveling Salesman Problem” and related problems (called “NP-complete” or “NP-hard”) that cannot be solved in reasonable time by the world’s fastest computers. The challenge in the traveling salesman problem is to find the shortest complete circuit of a bunch of cities that are different distances apart, visiting each of them only once. The map above shows a solution for the 50 state capitals. To construct it, I took the proven best solution for the capitals of the 48 contiguous states, and added Alaska and Hawaii. The total circuit comes to 16,368 miles as the crow flies. Our collaborative problem today is a variant of this one.

You have to find the shortest circuit that visits one and only one place in each of the 50 states. Any city or town or village whatsover will do — as long as it is in the chosen state. All that’s required is that the place you choose is listed on this Web site in order to find the aerial distance between it and any other place of your choosing. The distances given are to the closest mile. (I’m sure we’ll find some pretty obscure places that are close to state borders!)

You can start with the route above, but bear in mind that now this route may no longer be optimal. Since we are trying to foster a collaboration, do not try to make a herculean effort to solve the problem yourself. Instead try to contribute small pieces of optimization, such as finding cities in two or three states that are closer together than the previous best, or contributing general ideas or routes. One of the techniques to solve the traveling salesman problem is to search for small tour improvements, such as 2-opt moves, where two edges in a tour are deleted, and the tour is reconnected with two shorter edges. Similarly, there can be 3-opt moves, 4-opt moves and so on. If you contribute such moves, make sure you calculate the new total circuit each time. Let’s see how many hundreds of miles we can cut the route by! You can build on optimizations suggested by others, but don’t forget to cite their contributions. This is collaborative science, after all!

Readers who do not have experience with the phenomenal numerical complexity of these problems may wonder why we can’t just use computer “brute-force” algorithms to examine all possible cases. That’s because there are far too many of them! Numerical combinations can quickly outpace Moore’s Law — or any kind of growth law in the physical world, giving numbers that are hyper-astronomical. Dr. Cook estimates that the world’s fastest computer would take about 28 trillion years to find the best solution on just a 33-city problem, and adds, “(this is) an uncomfortable amount of time, given that the universe is estimated to be only 14 billion years old.” Yet humans are pretty good at finding decent solutions to such problems. On average, adults can find 15-city tours that are only 2.7% longer than the optimal one.

This important idea – that there are some problems that just cannot be solved using brute force computation – was brought home to me forcefully many years ago when I was trying to solve a problem posed in a Scrabble newsletter. The idea was to create the longest possible chain of unique six letter words such that the last three letters of the first word are the same as the first three letters of the next one, such as CONTRA TRAVEL VELCRO and so on. “No problem,” I thought, “I’ll just write a computer program to do it.” The lab where I worked then had five or six computers spanning three generations of computer chips. I wrote the program and set it to run on all the computers on a weekend. When I came back, I looked first at the slowest computer. The program was still chugging away, and the longest chain that it had found was 83 words long. I then looked at a computer that was an order of magnitude faster, pretty certain that it must have found a chain that was easily over a hundred words long. To my surprise, it was still chugging away too, at a chain length of 85. The very fastest computer we had was at a chain length of 86 words. The computers could have been for running for years and all they would have added to the length of the chain was one or two words. I realized then that computer brute force is limited, and sat down and used heuristic methods combining various partial chains, finally coming up with a chain that was over 400 words long! This problem, too, is a cousin of the Traveling Salesman Problem. Solving such problems will forever require a marriage of ingenious human algorithms and computer brute force, no matter how fast computers will get. Either one, by itself, will not suffice.

So for our collaborative word problem tonight, let’s do one that we’ve seen before as an analog of the de Bruijn sequence in “The Math Behind The Magic”:

You have to construct the longest possible chain of 3-letter words where the second word begins with the last two letters of the first word. I had given an 8-word example: ALAMANAG, which gives ALA, LAM, AMA, MAN, ANA, NAG, AGA and GAL. Reader Michael D. Sklaroff made a chain of length 36: ADOCABAALABOARECUDOLEAUKEATEEKEYETAM.

I’m sure we can collaboratively make the chain a lot longer, without using computers. You’ll find a list of all legal 3-letter words here. Those who are itching to write computer programs can tackle analogous problems for longer word lengths, as described above. The entire Scrabble world list is available here.

Good luck. See you later, collaborator!

By PRADEEP MUTALIK

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта