Localizando formas na matriz 2D e otimizando

11

Acabei de receber uma imagem ... A imagem abaixo do meu jogo mostra alguns blocos escuros, que foram reconhecidos como parte de uma forma de "T". Como pode ser visto, o código escureceu os blocos com as manchas vermelhas e não viu as formas "T" com os contornos verdes.

Encontrados padrões desejados, mas ainda não otimizados

Meu código percorre x / y, marca os blocos como usados, gira a forma, repete, muda de cor, repete.

Comecei a tentar corrigir essa verificação com grande apreensão. A ideia atual é:

  • faça um loop pela grade e anote todas as ocorrências de padrão (NÃO marcando os blocos conforme usados) e colocando-os em uma matriz
  • faça um loop pela grade novamente, dessa vez observando quais blocos são ocupados por quais padrões e, portanto, quais são ocupados por vários padrões.
  • circulando pela grade novamente, desta vez observando quais padrões obstruem quais padrões

Isso parece certo ... O que eu faço agora?

Eu acho que teria que

  • tente várias combinações de formas conflitantes, começando pelas que obstruem a maioria dos outros padrões primeiro. Como abordar este?
  • use o racional que diz que tenho 3 formas conflitantes, ocupando 8 blocos, e as formas são 4 blocos cada, portanto, só posso ter no máximo duas formas.

(Também pretendo incorporar outras formas, e provavelmente haverá uma ponderação de pontuação que precisará ser considerada ao passar pelas formas conflitantes, mas isso pode ser outro dia)

Não acho que seja um problema de empacotamento de lixeira, mas não sei ao certo o que procurar. Espero que faça sentido, obrigado por sua ajuda

EDIT Apesar da clareza da pergunta, todos parecem ter entendido, sim,

Quero encontrar o máximo de formas "T" em cada cor

(porque se eu lhe desse pontos por dois e você fizesse três, você ficaria um pouco irritado)

Montador
fonte
Um algoritmo ganancioso pode ser o de dividir a placa em coleções de blocos unidos. Em seguida, para cada coleção, você pode tentar preencher formas e atribuir ao preenchimento uma pontuação dependente da quantidade de blocos restantes que não seriam escurecidos. Meio que me faz pensar no en.wikipedia.org/wiki/Knapsack_problem .
Jonathan Connell
2
Eu acho que há algo faltando na pergunta. Deseja criar um algoritmo que encontre o maior número possível de grupos em forma de "T"?
Markus von Broady
Se eu entendo você, você está seguindo o caminho certo. Você não é muito claro e eu adoraria se você pudesse elaborar.
AturSams

Respostas:

3

Deixe-me ver se eu entendi direito, os blocos marcados em vermelho eram azuis e o algoritmo encontrou uma forma de T e os marcou em vermelho, está correto? Seu objetivo é encontrar o maior número possível de formas em T com os mesmos blocos coloridos, correto até agora, espero. Atualmente, você os marca depois de encontrá-los e isso diminui a utilidade do algoritmo (já que você pode estar perdendo a solução ideal). Você planeja procurar todas as formas e depois escolher quais usar e qual não usar. Estou correto até agora? Porque você deseja maximizar a quantidade de blocos contidos nas formas T quando o algoritmo é concluído.

Se eu estiver correto, a seguir, é a solução ideal para sua situação na minha opinião.

Usaremos a Programação Linear Inteira.

Acredito que usei este no passado:

http://sourceforge.net/projects/lpsolve/

http://lpsolve.sourceforge.net/5.5/Java/README.html

(Você pode fazê-lo funcionar com muitas linguagens, eu usei com PHP, Java e C)

O que faremos é registrar todas as formas possíveis de T no quadro e usar o ILP para maximizar a quantidade de blocos cobertos. ILP é exponencialmente complexo. Considerando o tamanho da sua placa, isso não será um problema. Fiz perguntas min / max muito mais complicadas em gráficos com ILP e demorou apenas uma fração de segundo para concluir e de 30 a 90 segundos com centenas de vértices (no seu caso, cai na fração de segundo).

O que eu recomendaria fazer:

  1. Encontre todas as formas de linha possíveis
  2. Encontre todas as interseções entre formas de linha da mesma cor
  3. Encontre todas as formas possíveis de T, pesquisando todas as interseções.
  4. Defina uma variável booleana no Problema Linear para cada forma de T ( 0 <= Bi <= 1) Como os valores são números inteiros, isso deixa 0 ou 1.
  5. Faça as condições para cada par de formas T que se cruzam ( Bi + Bj <= 1)
  6. A função objetivo será (soma dos blocos no formato "T" (i) * Bi)
  7. Execute o solucionador e obscureça as formas T onde os Booleanos correspondentes do solucionador estão 1 na solução ideal.

Este é um conhecimento valioso, usei resolvedores lineares frequentemente para projetos de trabalho.

O ILP é basicamente uma maneira de resolver problemas de seleção nos quais você deseja atingir um máximo ou um mínimo para alguma função linear.

Você pode ler mais aqui, usando Programação Linear Inteira e Programação Linear é a mesma para o programador, apenas que Integer é muito mais complexo para o computador, o que pode resultar em longos tempos de execução. Não no seu caso, é muito simples e, no pior dos casos, leva apenas menos de milissegundos.

Eu acho que você poderia ler mais aqui:

http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns

Isso explica bem:

http://fisher.osu.edu/~croxton_4/tutorial/

É basicamente um solucionador de problemas de decisão, como tomar decisões que maximizam o resultado desejado. Isso assume que a função que julga o resultado é linear e, no seu caso atual específico, é. A função que avalia o resultado nesse caso resume os blocos de todas as formas em T que você decidiu escurecer.

Matematicamente, como definir as variáveis: no nosso caso atual, os booleanos (escureci a forma de T com o índice i ou não) com os valores ótimos para maximizar o resultado que queremos: escurecendo o máximo de blocos possível sem escurecer as formas de interseção em T. Contanto que o resultado desejado possa ser calculado com uma função linear quando você tiver todas as variáveis ​​definidas, ele o resolverá. No nosso caso, verificamos quais formas T escurecemos e somamos os blocos que cobrem.

insira a descrição da imagem aqui

Sei que isso não é trivial, portanto, se você optar por dar o salto, fique à vontade para comentar e eu o elaborarei.

AturSams
fonte
Obrigado Arthur por sua ajuda. Pode demorar algumas leituras para digerir. E sim, você entendeu o problema corretamente. Eu ficaria muito interessado se você elaborasse (não, não, não é trivial), mas isso deve me ajudar a chegar aonde estou indo!
Assembler
Qual idioma você está usando para a implementação?
AturSams
actionscript 3! todo mundo é favorito!
Montador
o mesmo aqui. Vou escrever uma implementação em AS3 e carregá-lo em um github para download com comentários, passo a passo trabalhando - eu posso fazê-lo mais tarde hoje
AturSams
Você tem áreas específicas de 1 a 7 nas quais gostaria que eu adicionasse mais comentários ou elabore? Bem, boas notícias para os amantes do AS3, a Adobe lançou o FlasCC, que suporta C ++, para que possamos usar os solucionadores lineares existentes com facilidade. :)
AturSams
4

Depois de ter uma lista de todas as formas em T (possivelmente sobrepostas) ocorrendo em sua grade, o que resta é um problema de empacotamento máximo definido .

Em geral, esse é um problema completo do NP. No entanto, sua grade é pequena o suficiente (e normalmente se divide em subproblemas independentes ainda menores), para que seja possível obter soluções exatas.


Adendo: Aqui está um algoritmo de pesquisa de retrocesso básico que pode fazer o truque:

function max_packing_recursive ( set A, set S, set M ):
    if |M| < |S| then let M = S;
    for each shape X in A do:
        remove X from A;
        let B = A;
        remove all shapes that intersect with X from B;
        if |M| < |B| + |S| + 1 then:        // upper bound
            let M = max_packing_recursive( B, S + {X}, M );
        end if
        if |M| >= |A| + |S| then return M;  // shortcut
    end for
    return M;
end function

function max_packing( set A ):
    return max_packing_recursive( A, {}, {} );
end function

Aqui, {X, Y, Z}indica o conjunto contendo os elementos X, Ye Z(com {}sendo o conjunto vazio), e |Q|indica o tamanho do conjunto Q.

Na função recursiva, o conjunto Acontém as formas disponíveis para a solução restante, Sas formas no candidato atual à solução e Mé a solução máxima até o momento (que você pode armazenar como uma variável global em vez de retorná-la ao backup). cadeia de chamadas). A importante otimização está na linha marcada com // upper bound, que remove galhos da árvore de pesquisa que possivelmente não podem retornar uma solução melhor que M.

(Na verdade, como sabemos que cada forma de T contém exatamente quatro locais, um limite superior muito melhor pode ser obtido substituindo |B|-se pelo número de locais distintos cobertos pelas formas B, dividido por quatro e arredondado para baixo (e da mesma forma para |A|o linha marcada com // shortcut). Contudo, o algoritmo conforme indicado acima funciona para coleções arbitrárias de formas.)

Uma possível otimização adicional, que eu não implementei acima, seria verificar no início da função recursiva se Adivide em vários subconjuntos independentes, no sentido de que nenhuma forma em subconjuntos diferentes se sobreponha e, em caso afirmativo, aplique o algoritmo para cada um dos subconjuntos separadamente. (De qualquer forma, você definitivamente desejará fazer isso pelo menos uma vez no nível superior antes de chamar o algoritmo recursivo.) Classificar as formas Aadequadamente antes de fazer um loop sobre elas, por exemplo, em ordem crescente pelo número de formas sobrepostas, também pode ajudar .

Ilmari Karonen
fonte
Sim, acho que ele poderia usar um ILP para resolvê-lo de forma relativamente indolor por causa do tamanho do problema. 2 ^ 20 ~ = 1.000.000 então, como só pode haver tantas formas T, ele deve usar um solucionador linear para isso. . É claramente exponencialmente complexo (pelo menos até que alguém consiga provar que p = np). O tamanho permite evitar heurísticas neste caso relativamente simples.
AturSams
Ilmari, muito obrigado. Esta resposta também levará algumas tentativas para entender. O bit de formas arbitrárias pode muito bem ser útil em iterações futuras.
Assembler