Ho riscontrato un problema che ritengo sia piuttosto adatto per essere risolto utilizzando un algoritmo con problemi di soddisfazione dei vincoli. Tuttavia, non sono del tutto certo che questo sia l'approccio migliore, poiché le specifiche sembrano deviare un po 'dai classici problemi CSP.
Il problema:
Ho una lista di entità che ho bisogno di combinare insieme in base a un euristico, che è stato calcolato utilizzando una funzione di distanza.
L'elenco potrebbe essere simile a questo:
Entity A
- H(euristic): 0.1 -> Entity B
- H: 0.25 -> Entity D
Entity B
- H: 0.1 -> Entity A
- H: 0.4 -> Entity C
Entity C
- H: 0.4 -> Entity B
Entity D
- H: 0.25 -> Entity A
Ora, ciò che desidero realizzare è abbinare queste entità insieme 1 a 1, dove l'unico vincolo del problema è che ogni entità può essere abbinata solo a 1 entità. Che nel caso precedente, ovviamente significa che la soluzione sarebbe costituita da 2 insiemi di entità collegate tra loro.
Ora questo potrebbe essere un compito facile, ma è qui che il mio problema si discosta dai problemi CSP che ho incontrato in passato.
Desidero trovare una soluzione basata sui seguenti criteri:
- 1. Most amount of matches (Some entities might not know of more than 1 other entity, if the heuristic is too high, it will not be included in the list of possible relationships).
- 2. Lowest overall cost of matching entities.
Un'altra caratteristica principale di questo problema è che non deve essere risolto alla perfezione. Non tutte le Entità devono avere una corrispondenza. Se lasciare fuori una singola entità per la corrispondenza comporterà altre 2 partite lungo la strada, allora sarebbe preferibile.
E a proposito, una soluzione per l'esempio precedente basata sui criteri citati potrebbe essere la seguente:
- Entity A <--> Entity D
- Entity B <--> Entity C
Se la lista delle entità fosse più grande e dovessero esserci due soluzioni con lo stesso ammontare di partite, vorrei ovviamente confrontarle sul costo euristico e scegliere la più bassa di queste.
Ora la domanda è quale tipo di algoritmo sarebbe la soluzione migliore per questo tipo di problema? Se CSP è la scelta, come farei per consentire di restituire un set di dati (non risolto), ma scegliere la migliore soluzione parziale con il minor numero di iterazioni?
Modifica
Esempio di set di dati che è stato eseguito attraverso l'algoritmo dan1111 fornito.
Ho dimenticato di dire che più alto è l'euristico, meglio è in questo caso. Avrei dovuto fare un 1-h, prima di prendere lo screenshot.
