Para que servem os gráficos infinitos?

20

Acabei de ler na Wikipedia alemã que um gráfico infinito é um gráfico com um número infinito de nós ou um número infinito de arestas. Eu só conheço aplicativos e algoritmos para gráficos finitos.

Para que servem os gráficos infinitos?

Quais são as aplicações desses? Não consigo imaginar algoritmos que funcionariam em gráficos infinitos, pois você não pode armazenar um gráfico infinito. Então você não pode operar nele.

Martin Thoma
fonte
um algoritmo ganancioso que funciona movendo-se entre vértices com arestas finitas pode percorrer o gráfico e encontrar um novo vértice "preferido" ou "melhor" com base em uma função de custo ou adequação avaliada em cada vértice. muito trabalho em heurísticas de otimização, por exemplo, algoritmos genéticos, pode ser considerado como atravessando gráficos infinitos.
vzn

Respostas:

18

Muitos problemas de pesquisa em inteligência artificial (como pesquisar na árvore de jogos de um jogo de xadrez, ou procurar soluções para quebra-cabeças como o cubo de Rubik, ou mais geralmente procurar sequências de ações a serem executadas para atingir algum objetivo desejado) são: efeito, algoritmos em gráficos infinitos, mesmo que a resposta desejada seja um caminho finito. Certamente é possível executar algoritmos nesses gráficos, se eles estiverem representados implicitamente .

Mas também é verdade que a matemática pode ser útil, mesmo que não seja a matemática dos problemas que pode ser resolvida por algoritmos. Gráficos infinitos podem ser usados ​​para modelar os processos de nascimento e morte (por exemplo, como nossas regras de herança de nomes e as taxas nas quais as pessoas nascem e morrem levam a distribuições não uniformes de nomes de família entre diferentes culturas humanas?), estrutura para abordar questões sobre simetrias matemáticas (através de gráficos de Cayley , que geralmente são infinitos), para fornecer modelos de raciocínio sobre sistemas de lógica (consulte gráfico Rado e modelo saturado ), etc.

David Eppstein
fonte
5
A árvore de um jogo de xadrez é finita - embora seja inimaginável - como existe um número máximo de movimentos (devido à regra dos cinquenta movimentos e à repetição de três vezes ). Obrigado pela sua resposta, você mencionou muitas idéias em que não pensei: +1
Martin Thoma
2
Essas regras forçam o término do jogo? Ou eles apenas dão aos jogadores uma opção adicional, de pagar um empate em vez de continuarem a se mover?
David Eppstein
1
@ DavidEppstein: Eles impõem um limite máximo de movimento. Se 50 movimentos forem feitos sem que nenhum jogador mova um peão ou capture uma peça, o jogo termina automaticamente em um empate, mesmo que os jogadores desejem continuar. (Mas, claro, isso não afeta sua resposta.)
1
@ DavidEppstein: ah, desculpe, eu pensei que essas regras forçaram o término. Eles não fazem como as regras da FIDE (e a Wikipedia) afirmam. Consulte também math.stackexchange.com/q/194008/6876 para obter uma pergunta relacionada.
Martin Thoma
9

dd

De um lado do limiar, é difícil aproximar o modelo de Ising. Do outro lado do limiar, é fácil aproximar o modelo de Ising. Atualmente, a complexidade do modelo de Ising ao longo do limite de exclusividade é um problema em aberto, mas a conjectura é que ele é tratável.

O resultado mais recente nessa linha de trabalho é de Sly an Sun. Veja suas referências para outros trabalhos relacionados.

Tyson Williams
fonte
3

Para fornecer um aplicativo específico em que é útil pensar em gráficos infinitos, considere uma rede de nós distribuídos, cada um dos quais executa um algoritmo distribuído que prossegue em rodadas. Em cada rodada, um nó pode atualizar seu estado executando a computação local e se comunicando enviando / recebendo mensagens para / de seus vizinhos. A saída desse algoritmo é a saída combinada de todos os nós. Por exemplo, cada nó pode decidir localmente se faz parte de um conjunto independente.

Certos problemas de computação distribuída podem ser resolvidos em tempo constante (ou seja, número constante de rodadas até que todos os nós terminem), não importa quantos nós estejam na rede. Em particular, qualquer algoritmo desse tipo funcionará em um gráfico infinito (mas localmente finito). Dito isto, muitos problemas clássicos (como o MIS) estão sujeitos a um limite inferior deΩ(registron) e, portanto, não pode ser calculado em uma rede infinita.

Discussões adicionais sobre esse ponto podem ser encontradas aqui .

Pedro
fonte
1

gráficos universais são infinitos e uma generalização do gráfico aleatório Rado mencionado por DE. pesquisas recentes na área estão na direção de identificar gráficos universais para uma família de gráficos F: ou seja, um gráfico infinito pertencente a F que contém todos os gráficos finitos em F como subgráficos induzidos.

vzn
fonte