Quale algoritmo può essere utilizzato per una versione più complessa del problema del contenitore?

3

Al momento sto sviluppando un plugin per World of Warcraft in LUA per ottimizzare una parte del gioco introdotta di recente, ovvero le missioni di Garrison.

A Warcraft Garrison (fondamentalmente una strongzza per giocatore) ha un posto dove puoi assegnare i tuoi follower per andare in missione per te. Se queste missioni avranno successo, i tuoi follower avranno una certa esperienza e otterrai una piccola ricompensa, che spazia da un po 'di soldi a un equipaggiamento potente per te o per i tuoi follower. Una guarnigione ha 20-25 follower e ha circa 25-30 missioni tra cui scegliere al giorno.

Una missione ha i seguenti attributi:

  1. Un livello compreso tra 90 e 100, incluso.
  2. (per le missioni di livello 100) Un livello di equipaggiamento tra 615 e 645, a intervalli di 15.
  3. tra 1 e 3 slot per inviare follower con.
  4. tra 0 e 6 minacce di missione. Esistono circa 10 categorie di minacce, i cui nomi sono irrilevanti. Ciò che è rilevante è che un follower può avere 1 o 2 abilità in grado di contrastare queste minacce. Una missione può avere la stessa minaccia due volte.
  5. Un tipo di zona in cui si verifica questa missione.
  6. un tipo nemico a cui sta combattendo questa missione.
  7. Una durata.

Un follower ha i seguenti attributi:

  1. la razza del follower.
  2. Un livello compreso tra 90 e 100, inclusi. i seguaci di livello uguale o superiore contribuiscono maggiormente al successo della missione. Un follower che è di un livello al di sotto del livello della missione è meno efficace, ma ha comunque un effetto. Un follower di 2 o più livelli sotto il livello della missione non ha influenza sul successo della missione e non può contrastare alcuna minaccia.
  3. (A partire dal livello 100) Un livello di equipaggiamento tra 600 e 655 inclusi. Come il livello normale, i follower con livello di equipaggiamento uguale o superiore sono più efficaci.
  4. 1 o 2 abilità che sono segnalini per le minacce alla missione. Una minaccia contraria aumenta la possibilità di successo. se tutte le minacce vengono neutralizzate con follower di livello superiore, una missione ha una probabilità del 100% di successo. Un follower può avere 2 abilità che contrastano la stessa minaccia.
  5. 1, 2 o 3 tratti che possono dare minori possibilità di successo in determinate condizioni di missione. Questi non danno più possibilità di bonus di un contatore completo, ma sono utili per ottimizzare. Un tratto può contrastare una zona, una durata o un tipo nemico. Possono anche dare un bonus per avere un tipo specifico di follower nella stessa missione, o anche dare un bonus di successo sempre attivo.

Quello che capisco da alcuni breve chat con Gamedev.SE , questo è fondamentalmente il Problema di imballaggio del contenitore , con le missioni come pacchetti e i follower come contenitori. Tuttavia, in questo caso, i raccoglitori possono combinare e sono di diverse dimensioni.

L'algoritmo che sto cercando ha lo scopo di fare quanto segue nel minor tempo possibile:

  1. Massimizza la quantità di missioni con il 100% di possibilità di successo;
  2. Massimizza le possibilità individuali di successo di ogni missione che non ha il 100% di possibilità;

Probabilmente potrei rafforzarla, ma spero in una soluzione un po 'più sofisticata.

Quale algoritmo dovrei usare per questo?

    
posta Nzall 15.01.2015 - 21:53
fonte

1 risposta

4

La cosa su questo tipo di problemi è che la soluzione non deve essere perfetta. Spesso la differenza tra una euristica ragionevole e la soluzione ottimale è molto minima.

Quindi inizia con un algoritmo avido. Ordina prima le missioni per miglior risultato, e assegna il miglior gruppo possibile di seguaci alla prima missione, quindi il miglior set possibile di seguaci rimanenti alla seconda missione, e così via. Con "migliore" intendo né sovraffollato né sottratto. Questo è fondamentalmente il modo in cui la maggior parte dei giocatori eseguirà i compiti manualmente.

Quindi torna indietro e assegna il secondo miglior set alla prima missione e vedi se ciò migliora il punteggio complessivo, quindi il secondo migliore impostato per la seconda missione, e così via. Quindi il secondo miglior set a diverse combinazioni di due missioni, quindi tre missioni e così via. Quindi ripetere con il terzo set migliore. Fondamentalmente una ricerca in ampiezza di possibili incarichi.

Quello che dovresti scoprire è che dopo pochi strati nella struttura di ricerca, i miglioramenti iniziano a diventare sempre più piccoli. Lo tagli fuori dopo aver superato una certa soglia nel punteggio assoluto, dopo essere sceso al di sotto di una certa soglia nella differenza di punteggio tra le iterazioni o dopo un certo limite di tempo.

    
risposta data 15.01.2015 - 23:43
fonte

Leggi altre domande sui tag