O caminho mais curto entre todos os pubs no Reino Unido
Traçar o maior pub crawl do mundo tinha um ponto sério e matemático
De John o 'Groats a Land's End (1) - essa frase proverbial cobre toda a ilha da Grã-Bretanha. Aqui está um novo: do Bells But & Ben em gritar com o Witchball em O Lagarto. Esse é o pub mais ao norte e ao sul da Grã-Bretanha, respectivamente. Este mapa mostra a rota mais curta entre os dois - e todos os outros pubs no Reino Unido, todos os 24.725 deles. Esse é um enorme pub crawl.
Mas por que? Matemática computacional, é por isso. Este monstro de um mapa é uma solução para um enigma cartográfico chamado de Problema do caixeiro viajante (dois) .
Suponha que você seja um vendedor que apresenta seus produtos em vários locais hoje. O problema: encontre o caminho mais curto entre todos, levando em consideração que você precisa começar de casa e chegar lá no final do dia. Para um pequeno número de locais, a solução para esse problema geralmente é evidente. Adicione locais suficientes e a solução se tornará mais difícil. Difícil o suficiente para um manual a ser publicado em 1832 chamado O caixeiro viajante , propondo uma série de rotas para vendedores que viajam pela Alemanha e Suíça.
As soluções propostas baseavam-se na experiência, mas o Problema do Caixeiro Viajante (TSP) atormentou os cientistas, que procuraram formular uma resposta universal. O primeiro a enfrentar o problema foi o 19ºmatemático irlandês do século passado W.R. Hamilton, que desenvolveu o jogo icosian , cujo objetivo é encontrar um ciclo hamiltoniano em um dodecaedro ( cf. inf. ): um circuito que começa e termina no mesmo ponto e visita todos os outros pontos apenas uma vez (3).
Outro importante teórico do TSP foi o matemático vienense Karl Menger, que na década de 1930 reconheceu que
“É claro que esse problema pode ser resolvido por um número finito de tentativas, mas as regras que empurrariam o número de tentativas abaixo do número de permutações dos pontos dados não são conhecidas. A regra de que se deve ir primeiro do ponto de partida ao ponto mais próximo, depois ao ponto mais próximo a este, etc., em geral não resulta no percurso mais curto ”.
Como afirma Menger, a solução mais fácil para o TSP é simplesmente tentar todas as opções. Mas mesmo para um número relativamente baixo de locais, o número de variáveis é enorme - para apenas 10 cidades, há mais de 180.000 combinações, por exemplo.
Mas uma solução sistemática permanece indefinida até hoje, já que os computadores atualmente são capazes de calcular soluções para milhões de pontos com uma diferença de 2% a 3% do resultado ideal (4).
O TSP tem muitas aplicações úteis, desde encontrar as rotas mais curtas do carteiro até planejar a sequência ideal para fazer furos em placas de circuito e até mesmo calcular a maneira mais fácil para o Papai Noel completar seu passeio anual de uma noite por todas as chaminés do mundo. Talvez a consequência mais importante do TSP seja que não existem algoritmos conhecidos para quebrar os códigos nos quais confiamos para manter nossos dados seguros.
Encontrar o caminho mais curto entre todos os pubs na Grã-Bretanha pode não ter figurado no topo da lista de problemas do TSP a serem resolvidos, mas agora está, graças à Faculdade de Matemática da Universidade de Waterloo, no Canadá.
Eles atacaram o TSP mapeando o passeio a pé mais curto possível pelos pubs do Reino Unido, ou como eles chamaram cientificamente o projeto: UK24727, após o número de pubs (5) envolvidos. Algumas estatísticas:
Este desenho de linha transmite a rota do passeio, que também inclui excursões de balsa fora do continente britânico para passeios de pub nas ilhas Hébridas, Orkney e Shetland, na Ilha de Man e na Irlanda do Norte.
Todo o mapa, com marcadores do Google Maps para cada um dos pubs, dá a impressão de que a maior parte da Grã-Bretanha é coberta por uma cobertura contínua de balões vermelhos - áreas mais escuras indicando uma concentração de cumes de balão, onde a maior densidade de pubs sugere a presença das grandes cidades.
Além de resolver um problema matemático, o mapa também tem um uso prático óbvio, para planejar sua próxima visita aos pubs. Tentar a rota inteira não é recomendado, mas aumente o zoom em certas áreas ou cidades listadas no menu à direita e planeje sua próxima excursão.
Como esta viagem de bebida nas Hébridas: chegue de balsa de Oban, mate sua sede no Eu tenho um politico em South Uist, molhe seu apito no Langass Lodge no Loch Eport, dê um polimento na sua cerveja em Harmersay House em Lochmaddy e obtenha um para a estrada no Carlton em Stornoway, antes de pular na balsa de volta ao continente em Ullapool (onde você pode continuar entregando-se ao Ceilidh Place )
Ou por que não encontrar os bebedouros mais próximos das outras duas extremidades do Reino Unido: faça uma sessão de Gato preto em Belleek, o pub mais ocidental do reino, e saboreie bebidas alcoólicas no Royal Falcon em Lowestoft, provavelmente o pub mais ao leste - há alguns agrupados nessa área, então talvez você precise visitar mais alguns.
Visite os lendários poços de água de Londres na sucessão para economizar tempo planejada por esses matemáticos sedentos: faça o seu caminho de De Hems para o F Rench House através do Leão dourado e então ... espere, não estávamos indo na outra direção? Não importa: graças a este ciclo hamiltoniano, acabaremos aqui novamente.
Tendo planejado o maior pub crawl do mundo, a equipe do TSP na Waterloo University está se preparando para o próximo desafio: enviar seu suposto vendedor no tour mais curto possível, passando por todos os 49.603 lugares listados no Registro Nacional de Locais Históricos dos EUA. “Este problema é uma fera”, admitem.
“Atualmente temos um percurso de 350.201.525 metros. Isso é um pouco menos que a distância até a lua. Mas não sabemos se este é realmente o passeio mais curto. É possível que haja um passeio 196 metros mais curto do que o nosso. Ai! Fechar não é bom o suficiente ”.
Encontre o mapa inteiro aqui . Aviso: carrega lentamente! Para obter mais informações sobre o pub crawl do Reino Unido e outros projetos de estrada-TSP cobrindo 120 cidades alemãs, 50 marcos dos EUA e outros, consulte o Página TSP no Universidade de Waterloo 'S Faculdade de Matemática . Muito obrigado a Joel Winten e Folkard Wohlgemuth por enviar este mapa.
Strange Maps # 81 8
Tem um mapa estranho? Me avisa em estranhosmaps@gmail.com .
(1) John o 'Groats, em gaélico escocês John O'Groats , é uma vila de 300 habitantes na ponta norte do continente escocês. É o lugar habitado mais ao norte da Grã-Bretanha. Dunnet Head, cerca de quinze milhas (24 km) ao leste, é o lugar mais ao norte per se. John o 'Groats foi batizado em homenagem a Jan de Groot, um holandês que operava uma balsa daqui para Orkney por volta do ano 1500.
Land's End, em Cornish Penn e Wlas , é um promontório e resort de férias na ponta ocidental da Grã-Bretanha (7), na península de Penwith, na Cornualha. É cerca de 33 milhas (53 km) a leste de Lizard Point, a extremidade sul da Grã-Bretanha. A viagem de 838 milhas (1.349 km) entre John o 'Groats e Land's End é a mais longa possível entre dois lugares habitados na Grã-Bretanha.
(2) Ou, neste caso, o Problema do Alesman Viajante.
(3) Relacionado ao problema das Sete Pontes de Königsberg, comprovado por Euler como insolúvel. Mais sobre isso em # 536 .
(4) Para verdadeiros caixeiros-viajantes, não os teóricos idealizados por Hamilton, Menger e.a., o TSP é ainda mais complexo, pois a distância é apenas uma das variáveis; os mais importantes são tempo e dinheiro: quanto tempo leva para chegar a qualquer lugar e quanto custa? Por exemplo, vale a pena pegar o avião em vez do carro para ir de A para B e C e voltar para A novamente? Isso depende se o valor do tempo economizado supera o valor do dinheiro extra gasto.
(5) Uma vez que o número exato de pubs flutua devido ao fechamento e abertura de vários estabelecimentos, o estudo baseou-se nos 24.727 pubs listados no Site Pubs Galore .
(6) I.c. a rota conectando os 200 supercompressores Tesla nos Estados Unidos, um problema de estrada-TSP resolvido por Mortada Meyhar . Abaixo de seu mapa do Vendedor Tesla Viajante.
(7) Na verdade, o ponto mais ocidental de Inglaterra , mas não da Grã-Bretanha. Como o leitor Kevin Jones aponta, 'o ponto mais ocidental da ilha continental da Grã-Bretanha é Grande Corrupção , apenas 0,5 grau mais a oeste do Land's End. Se você estiver na Escócia, é um lugar maravilhoso para se visitar, com suas vistas sobre as ilhas das Hébridas Interiores. A geologia é muito interessante, sendo um resquício de um complexo ígneo da divisão do Atlântico Norte há cerca de 60 milhões de anos '.
Compartilhar:
