Complexidade da localização em redes sem fio
Deixe pontos distintos sentar em R 2 . Dizemos pontos i e j são vizinhos se | i - j | < 31...n1...nR2R2iijj , significando que cada ponto é vizinho de pontos com índices dentro de 2 , contornando.|i−j|<3(modn−2)|i−j|<3(modn−2)22
Para cada par de vizinhos, são dadas suas distâncias aos pares (e sabemos qual distância corresponde a quais pontos), e queremos reconstruir as distâncias aos pares de todos os pontos. Minhas perguntas são: qual é a complexidade desse problema de localização?
Não conheço um algoritmo de tempo polinomial.
Isso é motivado por problemas na localização em redes de sensores , onde os agentes, colocados ad-hoc, podem se comunicar sem fio com seus vizinhos lexicográficos, e queremos reconstruir suas posições.
Não sei muito sobre problemas de geometria / localização, portanto isso pode ser fácil ou conhecido. O problema mais próximo que conheço é o problema do Turnpike , apontado recentemente neste fórum por @Suresh Venkat.
bem definido? se dois pontos puderem pousar no mesmo ponto em R ^ 2, você poderá fazer dobradiças.
desculpe consertar ...
Lev, parece que o tex agora está ativado. você pode tentar editar sua postagem para usar o látex e ver se funciona?
você não esclareceu se é dada uma distância d Eu sei qual par (i, j) o fez. a diferença é crucial
@suresh - Esclarei sua pergunta - sabemos as distâncias correspondentes. também o suporte ao tex é ótimo! @Jukka - obrigado, vou verificar o seu link.
(Eu não tenho uma resposta real, mas isso foi muito longo para um comentário, portanto, poste aqui de qualquer maneira ...)
Eu suspeito que o problema é NP-difícil, por redução do problema da soma do subconjunto. Uma ideia de prova:
Redução: se o ésimo elemento na instância da soma do subconjunto for x i , a distância entre os nós 2 i - 1 e 2 i é s , distância entre 2 i - 1 e 2 i + 1 é x i , distância entre 2 i e 2 i + 2 também é x i , e a distância entre 2 i e 2 i + 1 éiixixi2i−12i−12i2iss2i−12i−12i+12i+1xixi2i2i2i+22i+2xixi2i2i2i+12i+1 .s2+x2i−−−−−−√s2+xi2
2i−12i−12i2iii2i+22i+22i2i2i2in=2kn=2k222k−12k−1112k−12k−122
ss2k2kxixi
ideia interessante - obrigado. uma pergunta rápida de esclarecimento - o que permite assumir que todas as arestas de 1 vizinho são verticais?
Só estou assumindo que as arestas 1-2, 3-4, ... são verticais. É claro que você pode escolher a orientação da aresta 1-2 arbitrariamente e definir que ela é "vertical". Depois, existem apenas duas configurações possíveis para a borda 3-4: ela é vertical ou você "virou" (espelhado) ao longo da borda 2-3. Gostaríamos de evitar a segunda possibilidade que complica a prova; veja a parte "até agora tudo bem ..." para uma possível idéia de como lidar com isso.
Entendo - boa idéia
Thm 4.1 (pág. 50) de cs.yale.edu/homes/dkg6/papers/thesis.pdf esta tese diz que o quadrado de qualquer gráfico com 2 conexões tem uma localização única. Como você apresentou uma localização global que é encontrada ao resolver a soma de subconjuntos, sabemos que não há mais respostas (e não precisamos nos preocupar com desvios na diagonal). Eu acho que isso termina a prova!
Na verdade, é NP-difícil. Veja o documento a seguir para referências.
Sriram V. Pemmaraju, Imran A. Pirwani: Realização virtual de boa qualidade de gráficos de esferas unitárias. SEC 2007: 311-322
As referências realmente cobrem o caso especial mencionado no OP? Ou seja, sua topologia gráfica é o quadrado de um ciclo?
Você está tão certo. Abrange apenas os casamentos no R ^ d.
Boa referência embora - obrigado
Drineas et al. escreveu o artigo Reconstrução da matriz de distância a partir de informações de distância incompletas para localização de rede de sensores . Mas o que eles alcançam provavelmente não é exatamente o que você solicita: eles calculam todo o mapa de distância de um mapa incompleto, mesmo na presença de ruído e falhas nos nós.