[Dúvidas] Algoritmo de Associação

[MORINGA]

O caso é o seguinte:

Tenho:

-2 tabelas, cada uma representando um conjunto de aldeias. Chamo uma de "Farms" e a outra de "Aldeias" (ou "Atacantes"), com diversos dados, entre os quais, as coordenadas cartesianas das mesmas. São mutuamente exclusivas, ou seja, a mesma aldeia não pode aparecer mais de uma vez numa tabela, nem pode se repetir na outra;
-Nessas tabelas, constam também alguns dados que, trabalhados, permitem calcular a capacidade de saque¹ das aldeias atacantes, e a capacidade de recursos² das aldeias atacadas.

Preciso:

-Associar cada "Farm" a uma única "Aldeia", de tal maneira que:
    -o uso das tropas de cada "Aldeia" seja otimizado, tanto na quantidade (fácil) quanto no tempo decorrido (médio);
    -o menor tempo decorrido prevaleça sobre a menor distância (só complica mais ainda), e;
    -a relação de "Farms" de cada "Aldeia" seja limitada, primeiro, pela capacidade de saques, e, em segundo lugar, pelo tempo decorrido;

Inicialmente, pensei no seguinte esquema (esquema, não é fluxograma, ainda...é um "rabiscunho") Mas tem um porém: se acabar a capacidade de saque de uma determinada "Aldeia", antes de acabar a Lista de "Farms", já que a referência, neste esquema, é a "Farm", corre o risco de haver alguma "Farm" mais próxima da "Aldeia", mais adiante na lista de "Farms". Então, deve-se fazer o inverso: ordenar as distâncias calculadas de uma "Aldeia" até cada "Farm", passando então para a "Aldeia" seguinte, e assim por diante. Cria-se a necessidade de uma tabela temporária, com os dados de distâncias entre uma "Aldeia" e todas as "Farms". Fiz um roteirinho que pode ajudar. Sei que não é nada assim simples, como "copia e imprime", mas não é impossível:

0) Calcular a capacidade de recursos de cada "Farm". Isso só precisa ser feito uma única vez (uma única tabela pra isso);
1) Calcular a capacidade de saque de uma "Aldeia". Isso precisa ser feito para cada "Aldeia" "da vez" (pode haver uma única tabela com capacidade de saque de todas as aldeias);
2) Calcular as distâncias entre a "Aldeia" "da vez" e todas as "Farms". Incluir na distância correspondente a capacidade de recursos de cada "Farm" (aqui, se for criada uma tabela, ela deverá ser de caráter temporário. Ver mais adiante);
3) Ordenar essas distâncias, a partir da menor;
4) Somar as capacidades de recursos de cada "Farm" (na ordem de distância disposta), até que esta soma alcance o limite (que é a capacidade de saque da "Aldeia");
5) Associar as unidades suficientes³ de cada "Aldeia", a partir da mais lenta (correspondente à "Farm" mais próxima), até a mais rápida. NÃO eliminar as "Farms" consideradas, visto que a(s) próxima(s) "Aldeia(s)" pode(m) ter distância(s) menor(es);
6) Tratar as intersecções, ou seja, "Farms" relacionadas a diferentes "Aldeias", observando as limitações de menor tempo decorrido sobre menor distância. Em caso de empate, fica a primeira associação. A regra geral diria que a menor distância corresponde ao menor tempo decorrido.

Um exemplo básico de tratamento de intersecção (formato das coordenadas: X|Y):

Duas "Aldeias", 500|500 e 501|500, disputam a mesma "Farm" (500|498).

Mas:

500|500 <-> 500|498 Lanceiros (36min)

501|500 <-> 500|498 CL (30min) <---

Logo, como o saque da 2ª é mais rápido que o da 1ª, descarta-se esta e considera-se aquela.

Em caso de empate:

500|500 <-> 501|502 Lanceiros (40,24min) <---

502|500 <-> 501|502 Lanceiros (40,24min)

Considera-se a primeira associação (500|500).

Agora vêm as tarefas que eu considero as mais difíceis de todas:

-no descarte de associação, alguma(s) "Aldeias" terão nova capacidade de saque, uma vez que a "Farm" original foi retirada num tratamento de intersecção. Isso implica em desperdício (vai contra a otimização). Esse desperdício deve ser minimizado;

-a tabela-exemplo de "Farms" tem 20.000 linhas, e a tabela-exemplo de "Aldeias" tem 2.000 linhas. O programa tem que terminar essa associação RAPIDAMENTE.

¹Esses dados são o tipo e a quantidade de unidade(s).

²Isso é calculado com base em dados de outras tabelas.

³Cada tipo de unidade tem sua própria velocidade e capacidade de saque.

Bem, eu sei que o conceito é meio difícil de entender, mas...pelo menos uma - aparente - contradição eu eliminei (texto tachado).

Ah, desisti de trabalhar com diversos arquivos, e passei a trabalhar com um único .MDB (Access), assim as consultas ficaram mais rápidas. Não devo/posso fazer isso num BD local ou remoto, por questões de simplicidade para o usuário final.

Fico grato se me ajudarem na parte 6, que é a mais difícil, no momento, e se há realmente contradição no texto tachado, ou se as unidades que ficam paradas na aldeia assim o ficariam, de qualquer jeito.

Editado Maio 29, 2008 por MORINGA