Modo efficiente per trovare il valore più alto dai predicati

Question

Modo efficiente per trovare il valore più alto dai predicati

#1 da (1 voti)

0

Ho un predicato, che enumera attraverso la lista dei valori di backtracking. Voglio trovare il valore più alto da questo elenco.

Ad esempio:

ranked_move(X,Y,R) :- between(0,10,Y), between(0,10,X), rank_move(X,Y,R).
top_move(X,Y) :- % X, Y for highest R

In questo momento, l'ho risolto utilizzando findall e il predicato personalizzato che passa attraverso l'elenco e ricorda il valore più alto che incontra. Ma mi piacerebbe sapere se c'è modo di farlo senza prima trasformare le mosse in una lista. Per esempio. fai il predicato del prelievo direttamente su ranked_move .

Conosco il link . Non l'ho provato, ma presumo che Prolog non abbia intenzione di analizzare i predicati in modo efficiente.

efficiency prolog

posta Euphoric 19.04.2013 - 10:17

fonte

1 risposta

Leggi altre domande sui tag efficiency prolog

In che modo Facebook rimuove html / apostrofi per XSS ma lo visualizza anche? Algorithm Identification [String & Dictionary]

score 1 · Accepted Answer

Finché non hai modo di giudicare le tue mosse, tranne chiamare ranked_move/3 , no, non esiste un modo più efficace di chiamarlo su tutto e trovare il massimo della lista risultante.

Sarebbe possibile evitare findall scrivendo i propri predicati che generano sistematicamente i valori e ricordano il massimo finora, evitando così il sovraccarico di creare un elenco. Ma questo sovraccarico è molto probabilmente insignificante accanto al costo di giudicare le mosse (nessun valore euristico di implementazione potrebbe essere più economico di un'operazione contro).

Quindi l'unico miglioramento davvero utile sarebbe avere un'euristica diversa, più economica, più debole che influenza l'ordine in cui le mosse sono generate e iterare su di esse in un ordine che ha più probabilità di avere il massimo prima. (Anche in questo caso, naturalmente, non dovresti ancora terminare più velocemente a meno che non imposti un valore di cutoff che è "abbastanza buono" piuttosto che "ottimale".)