Ciao Lich, nel caso tu voglia proprio fare la porca figura matematica ti posto di seguito l'algoritmo che permette di calcolare tutti i percorsi possibili con cui puoi affrontare un librogame. Come tutti gli algoritmi è impensabile mettersi a computarlo a mano, ma deve essere eseguito come software da un PC. Se ti può essere utile puoi inserirlo nella tua tesina.



ALGORITMO DI COMPUTAZIONE DI TUTTI I POSSIBILI PERCORSI DI UN LIBROGAME


Definizione 1:
Un librogame (LG) è un oggetto informativo assimilabile ad un albero logico. (un albero logico è un grafo costituito da un nodo di partenza, detto radice, dei nodi conclusivi, detti foglie, dei nodi intermedi che interconnetono radice e foglie, detti rami)


Definizione 2:
I nodi dell'albero logico LG sono chiamati Paragrafi. Ogni Paragrafo è caratterizzato da un numero identificativo x e da un insieme finito U di nodi di uscita (i paragrafi raggiungibili da un dato paragrafo).
Questo in logica puoi scriverlo come:
Paragrafo = {x, U = {a, b, c, ..., n} }


Così definiti tutti i paragrafi del Librogame, è necessario usare la seguente:


Funzione Ricorsiva TROVA_PERCORSI

TROVA_PERCORSI (paragrafo P, Percorso_Attuale, Percorsi){

SE nel paragrafo P, U è vuoto:
Aggiungi Percorso_Attuale a Percorsi
ALTRIMENTI
Per ogni paragrafo Y dentro U:
TROVA_PERCORSI(Y, Percorso_Attuale+Y, Percorsi)
}



Esecuzione:

LISTA_DI_TUTTI_I_POSSIBILI_PERCORSI = TROVA_PERCORSI (1, 1, { });


Alla fine dell'esecuzione dell'algoritmo, LISTA_DI_TUTTI_I_POSSIBILI_PERCORSI conterrà l'insieme di tutte le possibili sequenze di paragrafi con cui è affrontabile il librogame.


-------------------------------------------------


Tutto qui! sembra difficile ma in realtà è molto banale

Se volessi eseguirlo su un PC ti metto anche l'algoritmo scritto in Python (è un linguaggio di programmazione). E' la stessa cosa scritta sopra, tradotta dal linguaggio logico ad uno di programmazione


# **********************************************************************
#

class Node:
def __init__(self,key):
self.key = key
self.children = []


def visit(root,curPath,paths):
if root.children == []:
paths += [curPath]
for x in root.children:
visit(x,curPath + [x.key],paths)

# ************************************************************************
#

grazie mille!

EDIT: ho provato a farlo andare con un programma sul pc, ma mi da errore come se fosse incompleto… non ho capito quindi se devo aggiungere qualcosa io, o se ciò che mi hai scritto tu è incompleto…
inoltre un'altra cosa non ho capito: una volta eseguito cos'è che mi dovrebbe venire fuori?

scusa per la mia ignuranza programmatica e comunque grazie mille!!

Citazione:


Il calcolo dei percorsi va bene, ma così è troppo semplice e non applicabile in linea generale (cioè per ogni librogame devi fare il calcolo).

Sarebbe invece interessante, dal punto di vista algoritmico, capire se è possibile dare una stima del numero di percorsi in funzione di N (numero di nodi del grafo, o albero).

Ci ho pensato un po' e non sono riuscito a trovare una soluzione esatta, ma sicuramente mi viene in mente che, dati N nodi in un grafo aciclico e orientato con un nodo di partenza e uno di fine, il numero di percorsi è sicuramente esponenziale in N.
Però è molto difficile farne una stima di valor medio, un limite estremo è sicuramente la produttoria (prodotti consecutivi) di tutti i gradi di uscita dei nodi... ma anche qui ha molto poco senso dare un limite superiore così alto.

C'è da pensarci ancora un po' su, ma credo che forse questo problema (stima) sia piuttosto difficile da risolvere.

scusate ancora mi è venut in mente che probabilente è più o meno impossibile farne uno generale per tutto i librigame perchè appunto ci sono troppe variabili (una su tutte il numero di bivi rispetto ai paragrafi che da un librogame ad un altro può variare in modo casuale), ma tenendo fissi i dati, e quindi facendolo partendo da un diagramma già fatto (ad esempio partendo dal diagramma di LS) non dovrebbe essere tutto più facile e fattibile?

Ciao, per farlo funzionare devi scaricare il compilatore di Python e soprattutto devi definire il contenuto dell'albero, ovvero descrivere il librogame in termini di nodi di un albero.

Ti faccio un esempio di un ipotetico librogame di 7 paragrafi; questo programma in Python ti stamperà tutti i possibili percorsi effettuabili
(ovviamente devi prima inserire la parte di codice che ti ho già postato)

//*****************

root = Node("1")
v1 = Node("2")
v2 = Node("3")
v3 = Node("4")
v4 = Node("5")
v5 = Node("6")
v6 = Node("7")
root.children += [v1]
root.children += [v2]
v1.children += [v3]
v1.children += [v4]
v2.children += [v5]
v2.children += [v6]
paths = []
visit(root,[root.key],paths)
print paths

/***************

Citazione:

Si, se tu schematizzi un librogame con la struttura dati ad albero (ovviamente è un grande sbattimento!) questo algoritmo ti restituirà tutti e soli i percorsi fattibili all'interno del librogame. L'ho provato su esempi semplici (20 paragrafi) e pare funzionare...

Se invece vuoi stime ottenibili senza schemattizare tutto il libro in un albero credo che bisognerebbe sviluppare una formula che tenga conto di questi elementi:

1) numero di paragrafi P
2) numero medio di uscite da ogni paragrafo U
3) numero di paragrafi-foglia F

il caso base è con U=1, in questo caso il numero di storie possibili è sempre 1 indipendentemente da P, e F deve essere necessariamente 1


... e adesso vado a farmi birra e salsicce ...

Citazione:

mhh… non capisco perchè mi dice

File "", line 5
def __init__(self,key):
^
IndentationError: expected an indented block

p.s. buona birra è salsiccie!

ma questo se ho ben capito è un argomento che porti per la maturità o sbaglio?

nel prossimo post ti scrivo direttamente il file da dare in pasto al Python.

devi fare copia e incolla del tutto in un file di testo che chiamerai ad esempio percorsiLG.py

l'estensione deve essere .py ma il file lo chiami com vuoi tu

Se hai ancora problemi dimmi la versione di PY che usi e da dove l'hai presa.

class Node:
def __init__(self,key):
self.key = key
self.children = []


def visit(root,curPath,paths):
if root.children == []:
paths += [curPath]
for x in root.children:
visit(x,curPath + [x.key],paths)

# ********************************************************************
# Test
# ********************************************************************

root = Node("a")
v1 = Node("b")
v2 = Node("c")
v3 = Node("d")
v4 = Node("e")
v5 = Node("f")
v6 = Node("g")
root.children += [v1]
root.children += [v2]
v1.children += [v3]
v1.children += [v4]
v2.children += [v5]
v2.children += [v6]
paths = []
visit(root,[root.key],paths)
print paths